A178521 The cost of all leaves in the Fibonacci tree of order n.

0, 0, 3, 7, 17, 35, 70, 134, 251, 461, 835, 1495, 2652, 4668, 8163, 14195, 24565, 42331, 72674, 124354, 212155, 360985, 612743, 1037807, 1754232, 2959800, 4985475, 8384479, 14080601, 23614931, 39556030, 66181310, 110608187, 184670693, 308030923, 513334855

Offset: 0

Author

Emeric Deutsch, Jun 14 2010

Keywords

• nonn
• easy

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 leaf of a Fibonacci tree is defined to be the sum of the costs of the edges that form the path from the root to this leaf.

References

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

Links

• Colin Barker, 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 (2,1,-2,-1).

Crossrefs

Cf. A000045, A136376, A354044.

Programs

Julia

# The function 'fibrec' is defined in A354044.
function A178521(n)
    n < 2 && return BigInt(0)
    a, b = fibrec(n - 1)
    a*n + (n - 1)*b
end
println([A178521(n) for n in 0:35]) # Peter Luschny, May 16 2022

Maple

with(combinat); seq(n*fibonacci(n+1)-fibonacci(n), n = 0 .. 35);

Mathematica

Table[n Fibonacci[n + 1] - Fibonacci[n], {n, 0, 40}]  (* Harvey P. Dale, Apr 21 2011 *)
Table[(n - 1) Fibonacci[n] + n Fibonacci[n - 1], {n, 0, 40}] (* Bruno Berselli, Dec 06 2013 *)

PARI

concat(vector(2), Vec(x^2*(x+3)/(x^2+x-1)^2 + O(x^50))) \\ Colin Barker, Jul 26 2017

Formula

a(n) = n*F(n+1) - F(n), where F(k) = A000045(k).

G.f.: x^2*(x+3)/(x^2+x-1)^2. - Colin Barker, Nov 11 2012

a(n) = Sum_{k=1..n-1} F(k) * L(n-k+1) where F(n) = A000045(n), L(n) = A000032(n). - Gary Detlefs, Dec 29 2012

a(n) = (n-1)*F(n) + n*F(n-1). - Bruno Berselli, Dec 06 2013

a(0) = 0, a(n) = A023607(n-1) + A099920(n-1). - Collin Berman, Dec 12 2016

a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4). - Wesley Ivan Hurt, Dec 14 2016

a(n) = (n+1)*F(n+1) - F(n+2). - Bruno Berselli, Jul 26 2017

a(n) = (2^(-1-n)*(2*sqrt(5)*((1-sqrt(5))^n - (1+sqrt(5))^n) + (-(1-sqrt(5))^n*(-5+sqrt(5)) + (1+sqrt(5))^n*(5+sqrt(5)))*n))/5. - Colin Barker, Jul 26 2017

a(n) = (-n*sin(c*(-n - 1)) - sin(c*n)*i)/((-i)^(-n)*sqrt(5/4)) where c = arccos(i/2). - Peter Luschny, May 16 2022