A178525 The sum of the costs of all nodes in the Fibonacci tree of order n.

0, 0, 3, 8, 22, 49, 104, 208, 403, 760, 1406, 2561, 4608, 8208, 14499, 25432, 44342, 76913, 132808, 228416, 391475, 668840, 1139518, 1936513, 3283392, 5555424, 9381699, 15815528, 26618518, 44733745, 75073256, 125827696, 210642643

Offset: 0

Author

Emeric Deutsch, Jun 15 2010

Keywords

• nonn

Comments

A Fibonacci tree of order n (n>=2) is a complete binary tree whose left subtree is the Fibonacci tree of order n-1 and whose right subtree is the Fibonacci tree of order n-2; each of the Fibonacci trees of order 0 and 1 is defined as a single node. In a Fibonacci tree the cost of a left (right) edge is defined to be 1 (2). The cost of a node in a Fibonacci tree is defined to be the sum of the costs of the edges that form the path from the root to this node.

A178525 is the 1-sequence of reduction of the odd number sequence (2n-1) by x^2 -> x+1; as such it is related to 0-sequence of this reduction, A192304. See A192232 for definition of "k-sequence of reduction of [sequence] by [substitution]". - Clark Kimberling, Jun 27 2011

References

• D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Y. Horibe, An entropy view of Fibonacci trees, Fibonacci Quarterly, 20, No. 2, 1982, 168-178.
• Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,1,1).

Crossrefs

Cf. A000045, A094584, A178521.

Programs

GAP

List([0..40], n -> 3 +(2*n-3)*Fibonacci(n-1) +(2*n-5)*Fibonacci(n)); # G. C. Greubel, Jan 30 2019

Magma

[3 +(2*n-3)*Fibonacci(n-1) +(2*n-5)*Fibonacci(n): n in [0..40]]; // G. C. Greubel, Jan 30 2019

Maple

with(combinat): seq(3+(2*n-3)*fibonacci(n-1)+(2*n-5)*fibonacci(n), n = 0 .. 32);

Mathematica

Table[3 +(2*n-3)*Fibonacci[n-1] +(2*n-5)*Fibonacci[n], {n,0,40}] (* G. C. Greubel, Jan 30 2019 *)

PARI

a(n) = 3+(2*n-3)*fibonacci(n-1) + (2*n-5)*fibonacci(n); \\ Michel Marcus, Jan 21 2019

Sage

[3 +(2*n-3)*fibonacci(n-1) +(2*n-5)*fibonacci(n) for n in range(40)] # G. C. Greubel, Jan 30 2019

Formula

a(n) = 3 + (2*n-3)*F(n-1) + (2*n-5)*F(n), where F(k)=A000045(k) are the Fibonacci numbers.

a(n) = a(n-1) + a(n-2) + 2*F(n+1) + 2*F(n-1) - 3 (n>=2), F(0)=0, F(1)=0.

G.f.: z^2*(3-z+z^2)/((1-z)*(1-z-z^2)^2).