A094584 Dot product of (1,2,...,n) and first n distinct Fibonacci numbers.

1, 5, 14, 34, 74, 152, 299, 571, 1066, 1956, 3540, 6336, 11237, 19777, 34582, 60134, 104062, 179320, 307855, 526775, 898706, 1529160, 2595624, 4396224, 7431049, 12537917, 21118814, 35517226, 59646386, 100034456, 167562035, 280348531, 468543802, 782277612

Offset: 1

Author

Clark Kimberling, May 13 2004

Keywords

• nonn
• easy

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

Examples

			a(4) = (1,2,3,4)*(1,2,3,5) = 1+4+9+20 = 34.
		

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

Crossrefs

Cf. A000045, A094585.

Partial sums of A023607.

Programs

GAP

List([1..40],n->(n+1)*Fibonacci(n+3)-Fibonacci(n+5)+3); # Muniru A Asiru, Apr 27 2019

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

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

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

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)