OFFSET
1,2
COMMENTS
a(n) is the cost of all non-leaf nodes in the Fibonacci tree of order n+2. 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 node 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 node. - Emeric Deutsch, Jun 14 2010
REFERENCES
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 14.
D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417. [From Emeric Deutsch, Jun 14 2010]
LINKS
Muniru A Asiru, Table of n, a(n) for n = 1..2000
Y. Horibe, An entropy view of Fibonacci trees, Fibonacci Quarterly, 20, No. 2, 1982, 168-178. [From Emeric Deutsch, Jun 14 2010]
Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,1,1).
FORMULA
a(n) = F(2) + 2*F(3) + 3*F(4) + ... + n*F(n+1) = (n+1)*F(n+3) - F(n+5) + 3.
G.f.: x*(1+2*x)/((1-x)*(1-x-x^2)^2). - Colin Barker, Nov 11 2012
From Wesley Ivan Hurt, Mar 10 2015: (Start)
a(n) = 3*a(n-1) - a(n-2) - 3*a(n-3) + a(n-4) + a(n-5).
a(n) = Sum_{i=1..n+2} (n-i+1) * F(n-i+2).
a(n) = (30*(-1-sqrt(5))^n + (-15+7*sqrt(5))*2^n - (15+7*sqrt(5))*(-3-sqrt(5))^n + 2n*((5-2*sqrt(5))*2^n + (5+2*sqrt(5))*(-3-sqrt(5))^n)) / (10*(-1-sqrt(5))^n). (End)
EXAMPLE
a(4) = (1,2,3,4)*(1,2,3,5) = 1+4+9+20 = 34.
MAPLE
with(combinat): A094584:=n->(n+1)*fibonacci(n+3)-fibonacci(n+5)+3: seq(A094584(n), n=1..50); # Wesley Ivan Hurt, Mar 10 2015
MATHEMATICA
Table[Range[n].Fibonacci[Range[2, n+1]], {n, 40}] (* Harvey P. Dale, Aug 21 2011 *)
PROG
(Magma) I:=[1, 5, 14, 34, 74]; [n le 5 select I[n] else 3*Self(n-1)-Self(n-2)-3*Self(n-3)+Self(n-4)+Self(n-5): n in [1..40]]; // Vincenzo Librandi, Mar 11 2015
(Magma) [n*Fibonacci(n+3)-Fibonacci(n+4)+3: n in [1..40]]; // G. C. Greubel, Apr 28 2019
(GAP) List([1..40], n->(n+1)*Fibonacci(n+3)-Fibonacci(n+5)+3); # Muniru A Asiru, Apr 27 2019
(PARI) {a(n) = n*fibonacci(n+3) - fibonacci(n+4) +3}; \\ G. C. Greubel, Apr 28 2019
(Sage) [n*fibonacci(n+3) - fibonacci(n+4) +3 for n in (1..40)] # G. C. Greubel, Apr 28 2019
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Clark Kimberling, May 13 2004
STATUS
approved