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

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,2

Comments

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

Links

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

Formula

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.

Example

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

Mathematica

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

Prog

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

Crossrefs

Cf. A354902.

Sequence in context: A229086 A354902 A022406 * A132447 A132449 A132453

Adjacent sequences: A355285 A355286 A355287 * A355289 A355290 A355291

Keyword

nonn,easy

Author

Sumukh Patel, Jun 27 2022

Status

approved