cp's OEIS Frontend

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

%I A178521 #47 Jan 05 2025 19:51:39
%S A178521 0,0,3,7,17,35,70,134,251,461,835,1495,2652,4668,8163,14195,24565,
%T A178521 42331,72674,124354,212155,360985,612743,1037807,1754232,2959800,
%U A178521 4985475,8384479,14080601,23614931,39556030,66181310,110608187,184670693,308030923,513334855
%N A178521 The cost of all leaves in the Fibonacci tree of order n.
%C A178521 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 A178521 D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.
%H A178521 Colin Barker, <a href="/A178521/b178521.txt">Table of n, a(n) for n = 0..1000</a>
%H A178521 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 A178521 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-2,-1).
%F A178521 a(n) = n*F(n+1) - F(n), where F(k) = A000045(k).
%F A178521 G.f.: x^2*(x+3)/(x^2+x-1)^2. - _Colin Barker_, Nov 11 2012
%F A178521 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 A178521 a(n) = (n-1)*F(n) + n*F(n-1). - _Bruno Berselli_, Dec 06 2013
%F A178521 a(0) = 0, a(n) = A023607(n-1) + A099920(n-1). - _Collin Berman_, Dec 12 2016
%F A178521 a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4). - _Wesley Ivan Hurt_, Dec 14 2016
%F A178521 a(n) = (n+1)*F(n+1) - F(n+2). - _Bruno Berselli_, Jul 26 2017
%F A178521 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 A178521 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 A178521 with(combinat); seq(n*fibonacci(n+1)-fibonacci(n), n = 0 .. 35);
%t A178521 Table[n Fibonacci[n + 1] - Fibonacci[n], {n, 0, 40}]  (* _Harvey P. Dale_, Apr 21 2011 *)
%t A178521 Table[(n - 1) Fibonacci[n] + n Fibonacci[n - 1], {n, 0, 40}] (* _Bruno Berselli_, Dec 06 2013 *)
%o A178521 (PARI) concat(vector(2), Vec(x^2*(x+3)/(x^2+x-1)^2 + O(x^50))) \\ _Colin Barker_, Jul 26 2017
%o A178521 (Julia) # The function 'fibrec' is defined in A354044.
%o A178521 function A178521(n)
%o A178521     n < 2 && return BigInt(0)
%o A178521     a, b = fibrec(n - 1)
%o A178521     a*n + (n - 1)*b
%o A178521 end
%o A178521 println([A178521(n) for n in 0:35]) # _Peter Luschny_, May 16 2022
%Y A178521 Cf. A000045, A136376, A354044.
%K A178521 nonn,easy
%O A178521 0,3
%A A178521 _Emeric Deutsch_, Jun 14 2010