A022406 a(0)=3, a(1)=7; thereafter a(n) = a(n-1) + a(n-2) + 1.

3, 7, 11, 19, 31, 51, 83, 135, 219, 355, 575, 931, 1507, 2439, 3947, 6387, 10335, 16723, 27059, 43783, 70843, 114627, 185471, 300099, 485571, 785671, 1271243, 2056915, 3328159, 5385075, 8713235, 14098311, 22811547, 36909859, 59721407, 96631267, 156352675

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

a(n) is the minimum number of nodes required for a full binary AVL tree of height n+1 whose root node has a balance factor of 0. - Sumukh Patel, Jun 24 2022

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

Crossrefs

Cf. A000045, A022087, A122195. See A022403 for a very similar sequence.

Programs

Magma

[4*Fibonacci(n+2) - 1: n in [0..40]]; // G. C. Greubel, Mar 01 2018

Mathematica

Table[4*Fibonacci[n + 2] - 1, {n, 0, 100}] (* Vladimir Joseph Stephan Orlovsky, Jun 28 2011 *)
CoefficientList[Series[(3+x-3*x^2)/((1-x)*(1-x-x^2)), {x, 0, 50}], x] (* G. C. Greubel, Mar 01 2018 *)

PARI

a(n) = 4*fibonacci(n+2)-1; \\ G. C. Greubel, Mar 01 2018

Formula

a(n) = 4*A000045(n+2) - 1. - Ron Knott, Aug 25 2006

From R. J. Mathar, May 28 2008: (Start)

a(n) = A022403(n+1).

O.g.f.: (3+x-3*x^2)/((1-x)*(1-x-x^2)).

a(n+1) - a(n) = A022087(n+1). (End)

a(n) = (2^(-n)*(-5*2^n + (10-6*sqrt(5))*(1-sqrt(5))^n + 2*(1+sqrt(5))^n*(5+3*sqrt(5)))) / 5. - Colin Barker, Mar 02 2018

E.g.f.: 4*exp(x/2)*(5*cosh(sqrt(5)*x/2) + 3*sqrt(5)*sinh(sqrt(5)*x/2))/5 - exp(x). - Stefano Spezia, Feb 01 2025