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(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
KEYWORD
nonn,easy
AUTHOR
Emeric Deutsch, Jun 14 2010
STATUS
approved