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,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

Cf. A000045, A094585.

Partial sums of A023607.

Sequence in context: A296010 A182738 A192957 * A023515 A047860 A369887

Adjacent sequences: A094581 A094582 A094583 * A094585 A094586 A094587

Keyword

nonn,easy

Author

Clark Kimberling, May 13 2004

Status

approved