A022403 -id:A022403 - cp's OEIS frontend

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

N. J. A. Sloane

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

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

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

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

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 *)

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

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

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

Original entry on oeis.org

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, 252983943, 409336619, 662320563

Offset: 0

Sumukh Patel, Jun 27 2022

a(n) is the minimum number of nodes required for a full binary tree of height n with every node height-balanced, and the root node has a balance factor of 0.
Full binary tree: A binary tree is called a full binary tree if each node has exactly two or no children.
Essentially the same as A022403. - R. J. Mathar, Sep 23 2022

			The diagrams below illustrate the terms a(3)=11 and a(4)=19.
           R                         R
          / \                       / \
         /   \                     /   \
        /     \                   /     \
       o       o                 /       \
      / \     / \               /         \
     o   N   N   o             /           \
    / \         / \           /             \
   N   N       N   N         o               o
                            / \             / \
                           /   \           /   \
                          /     \         /     \
                         o       o       o       o
                        / \     / \     / \     / \
                       o   N   N   N   N   o   N   N
                      / \                 / \
                     N   N               N   N

Sumukh Patel, Table of n, a(n) for n = 0..1000
Lecture Notes for Computer Science 2530, Height-balanced trees
NIST, Root node
Wikipedia, Full binary tree
Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

Cf. A354902.

[n eq 0 select 1 else 4*Fibonacci(n+1) - 1: n in [0..40]];

Join[{1},Table[4*Fibonacci[n + 1] - 1, {n, 1, 40}]]

a(0)=1, a(1)=3, a(2)=7; thereafter a(n) = a(n-1) + a(n-2) + 1.
From Stefano Spezia, Jun 27 2022: (Start)
G.f.: (1 + x + x^2 - 2*x^3)/((1 - x)*(1 - x - x^2)).
a(n) = 2*a(n-1) - a(n-3) for n > 3.
a(n) = 2^(1-n)*((1 + sqrt(5))^(n+1) - (1 - sqrt(5))^(n+1))/sqrt(5) - 1 for n > 0.
E.g.f.: 4*exp(x/2)*(5*cosh(sqrt(5)*x/2) + sqrt(5)*sinh(sqrt(5)*x/2))/5 - exp(x) - 2. (End)
a(n) = 4*A000045(n+1) - 1, for n >= 1.
a(n) = 2*A001595(n) + 1, for n >= 1.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula