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

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

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

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

Prog

(PARI) concat(vector(2), Vec(x^2*(x+3)/(x^2+x-1)^2 + O(x^50))) \\ Colin Barker, Jul 26 2017
(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

Crossrefs

Cf. A000045, A136376, A354044.

Sequence in context: A192958 A351405 A219293 * A034482 A114100 A260677

Adjacent sequences: A178518 A178519 A178520 * A178522 A178523 A178524

Keyword

nonn,easy

Author

Emeric Deutsch, Jun 14 2010

Status

approved