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

%I #27 Sep 23 2022 14:42:02

%S 1,3,7,11,19,31,51,83,135,219,355,575,931,1507,2439,3947,6387,10335,

%T 16723,27059,43783,70843,114627,185471,300099,485571,785671,1271243,

%U 2056915,3328159,5385075,8713235,14098311,22811547,36909859,59721407,96631267,156352675,252983943,409336619,662320563

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

%C 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.

%C Full binary tree: A binary tree is called a full binary tree if each node has exactly two or no children.

%C Essentially the same as A022403. - _R. J. Mathar_, Sep 23 2022

%H Sumukh Patel, <a href="/A355288/b355288.txt">Table of n, a(n) for n = 0..1000</a>

%H Lecture Notes for Computer Science 2530, <a href="http://www.cs.ecu.edu/karl/2530/spr18/Notes/lec37+38.html#:~:text=A%20node%20in%20a%20tree%20is%20height%2Dbalanced%20if%20the,height%2Dbalanced%20by%20definition.)">Height-balanced trees</a>

%H NIST, <a href="https://xlinux.nist.gov/dads/HTML/root.html">Root node</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees">Full binary tree</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-1).

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

%F From _Stefano Spezia_, Jun 27 2022: (Start)

%F G.f.: (1 + x + x^2 - 2*x^3)/((1 - x)*(1 - x - x^2)).

%F a(n) = 2*a(n-1) - a(n-3) for n > 3.

%F a(n) = 2^(1-n)*((1 + sqrt(5))^(n+1) - (1 - sqrt(5))^(n+1))/sqrt(5) - 1 for n > 0.

%F 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)

%F a(n) = 4*A000045(n+1) - 1, for n >= 1.

%F a(n) = 2*A001595(n) + 1, for n >= 1.

%e The diagrams below illustrate the terms a(3)=11 and a(4)=19.

%e R R

%e / \ / \

%e / \ / \

%e / \ / \

%e o o / \

%e / \ / \ / \

%e o N N o / \

%e / \ / \ / \

%e N N N N o o

%e / \ / \

%e / \ / \

%e / \ / \

%e o o o o

%e / \ / \ / \ / \

%e o N N N N o N N

%e / \ / \

%e N N N N

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

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

%Y Cf. A354902.

%K nonn,easy

%O 0,2

%A _Sumukh Patel_, Jun 27 2022