A178521 - OEIS

%I #47 Jan 05 2025 19:51:39

%S 0,0,3,7,17,35,70,134,251,461,835,1495,2652,4668,8163,14195,24565,

%T 42331,72674,124354,212155,360985,612743,1037807,1754232,2959800,

%U 4985475,8384479,14080601,23614931,39556030,66181310,110608187,184670693,308030923,513334855

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

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

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

%H Colin Barker, <a href="/A178521/b178521.txt">Table of n, a(n) for n = 0..1000</a>

%H Y. Horibe, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/20-2/horibe.pdf">An entropy view of Fibonacci trees</a>, Fibonacci Quarterly, 20, No. 2, 1982, 168-178.

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

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

%F G.f.: x^2*(x+3)/(x^2+x-1)^2. - _Colin Barker_, Nov 11 2012

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

%F a(n) = (n-1)*F(n) + n*F(n-1). - _Bruno Berselli_, Dec 06 2013

%F a(0) = 0, a(n) = A023607(n-1) + A099920(n-1). - _Collin Berman_, Dec 12 2016

%F a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4). - _Wesley Ivan Hurt_, Dec 14 2016

%F a(n) = (n+1)*F(n+1) - F(n+2). - _Bruno Berselli_, Jul 26 2017

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

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

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

%t Table[n Fibonacci[n + 1] - Fibonacci[n], {n, 0, 40}]  (* _Harvey P. Dale_, Apr 21 2011 *)

%t Table[(n - 1) Fibonacci[n] + n Fibonacci[n - 1], {n, 0, 40}] (* _Bruno Berselli_, Dec 06 2013 *)

%o (PARI) concat(vector(2), Vec(x^2*(x+3)/(x^2+x-1)^2 + O(x^50))) \\ _Colin Barker_, Jul 26 2017

%o (Julia) # The function 'fibrec' is defined in A354044.

%o function A178521(n)

%o     n < 2 && return BigInt(0)

%o     a, b = fibrec(n - 1)

%o     a*n + (n - 1)*b

%o end

%o println([A178521(n) for n in 0:35]) # _Peter Luschny_, May 16 2022

%Y Cf. A000045, A136376, A354044.

%K nonn,easy

%O 0,3

%A _Emeric Deutsch_, Jun 14 2010