A101220 a(n) = Sum_{k=0..n} Fibonacci(n-k)*n^k.

0, 1, 3, 14, 91, 820, 9650, 140601, 2440317, 49109632, 1123595495, 28792920872, 816742025772, 25402428294801, 859492240650847, 31427791175659690, 1234928473553777403, 51893300561135516404, 2322083099525697299278

Offset: 0

Author

Ross La Haye, Dec 14 2004

Keywords

• nonn
• easy

Comments

In what follows a(i,j,k) denotes a three-dimensional array, the terms a(n) are defined as a(n,n,n) in that array. - Joerg Arndt, Jan 03 2021

Previous name was: Three-dimensional array: a(i,j,k) = expansion of x*(1 + (i-j)*x)/((1-j*x)*(1-x-x^2)), read by a(n,n,n).

a(i,j,k) = the k-th value of the convolution of the Fibonacci numbers (A000045) with the powers of i = Sum_{m=0..k} a(i-1,j,m), both for i = j and i > 0; a(i,j,k) = a(i-1,j,k) + a(j,j,k-1), for i,k > 0; a(i,1,k) = Sum_{m=0..k} a(i-1,0,m), for i > 0. With F = Fibonacci and L = Lucas, then a(1,1,k) = F(k+2) - 1; a(2,1,k) = F(k+3) - 2; a(3,1,k) = L(k+2) - 3; a(4,1,k) = 4*F(k+1) + F(k) - 4; a(1,2,k) = 2^k - F(k+1); a(2,2,k) = 2^(k+1) - F(k+3); a(3,2,k) = 3(2^k - F(k+2)) + F(k); a(4,2,k) = 2^(k+2) - F(k+4) - F(k+2); a(1,3,k) = (3^k + L(k-1))/5, for k > 0; a(2,3,k) = (2 * 3^k - L(k)) /5, for k > 0; a(3,3,k) = (3^(k+1) - L(k+2))/5; a(4,3,k) = (4 * 3^k - L(k+2) - L(k+1))/5, etc..

Examples

			a(1,3,3) = 6 because a(1,3,0) = 0, a(1,3,1) = 1, a(1,3,2) = 2 and 4*2 - 2*1 - 3*0 = 6.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..385
• Eric Weisstein's World of Mathematics, Fibonacci Number
• Eric Weisstein's World of Mathematics, Lucas Number

Crossrefs

a(0, j, k) = A000045(k).

a(1, 2, k+1) - a(1, 2, k) = A099036(k).

a(3, 2, k+1) - a(3, 2, k) = A104004(k).

a(4, 2, k+1) - a(4, 2, k) = A027973(k).

a(1, 3, k+1) - a(1, 3, k) = A099159(k).

a(i, 0, k) = A109754(i, k).

a(i, i+1, 3) = A002522(i+1).

a(i, i+1, 4) = A071568(i+1).

a(2^i-2, 0, k+1) = A118654(i, k), for i > 0.

Sequences of the form a(n, 0, k): A000045(k+1) (n=1), A000032(k) (n=2), A000285(k-1) (n=3), A022095(k-1) (n=4), A022096(k-1) (n=5), A022097(k-1) (n=6), A022098(k-1) (n=7), A022099(k-1) (n=8), A022100(k-1) (n=9), A022101(k-1) (n=10), A022102(k-1) (n=11), A022103(k-1) (n=12), A022104(k-1) (n=13), A022105(k-1) (n=14), A022106(k-1) (n=15), A022107(k-1) (n=16), A022108(k-1) (n=17), A022109(k-1) (n=18), A022110(k-1) (n=19), A088209(k-2) (n=k-2), A007502(k) (n=k-1), A094588(k) (n=k).

Sequences of the form a(1, n, k): A000071(k+2) (n=1), A027934(k-1) (n=2), A098703(k) (n=3).

Sequences of the form a(2, n, k): A001911(k) (n=1), A008466(k+1) (n=2), A106517(k-1) (n=3).

Sequences of the form a(3, n, k): A027961(k) (n=1), A094688(k) (n=3).

Sequences of the form a(4, n, k): A053311(k-1) (n=1), A027974(k-1) (n=2).

Cf. A001622, A001891, A001924, A023537, A104161, A106517.

Programs

Magma

A101220:= func< n | (&+[n^k*Fibonacci(n-k): k in [0..n]]) >;
[A101220(n): n in [0..30]]; // G. C. Greubel, Jun 01 2025

Mathematica

Join[{0}, Table[Sum[Fibonacci[n-k]*n^k, {k, 0, n}], {n, 1, 20}]] (* Vaclav Kotesovec, Jan 03 2021 *)

PARI

a(n)=sum(k=0,n,fibonacci(n-k)*n^k) \\ Joerg Arndt, Jan 03 2021

SageMath

def A101220(n): return sum(n^k*fibonacci(n-k) for k in range(n+1))
print([A101220(n) for n in range(31)]) # G. C. Greubel, Jun 01 2025

Formula

a(i, j, 0) = 0, a(i, j, 1) = 1, a(i, j, 2) = i+1; a(i, j, k) = ((j+1)*a(i, j, k-1)) - ((j-1)*a(i, j, k-2)) - (j*a(i, j, k-3)), for k > 2.

a(i, j, k) = Fibonacci(k) + i*a(j, j, k-1), for i, k > 0.

a(i, j, k) = (Phi^k - (-Phi)^-k + i(((j^k - Phi^k) / (j - Phi)) - ((j^k - (-Phi)^-k) / (j - (-Phi)^-1)))) / sqrt(5), where Phi denotes the golden mean/ratio (A001622).

i^k = a(i-1, i, k) + a(i-2, i, k+1).

A104161(k) = Sum_{m=0..k} a(k-m, 0, m).

a(i, j, 0) = 0, a(i, j, 1) = 1, a(i, j, 2) = i+1, a(i, j, 3) = i*(j+1) + 2; a(i, j, k) = (j+2)*a(i, j, k-1) - 2*j*a(i, j, k-2) - a(i, j, k-3) + j*a(i, j, k-4), for k > 3. a(i, j, 0) = 0, a(i, j, 1) = 1; a(i, j, k) = a(i, j, k-1) + a(i, j, k-2) + i * j^(k-2), for k > 1.

G.f.: x*(1 + (i-j)*x)/((1-j*x)*(1-x-x^2)).

a(n, n, n) = Sum_{k=0..n} Fibonacci(n-k) * n^k. - Ross La Haye, Jan 14 2006

Sum_{m=0..k} binomial(k,m)*(i-1)^m = a(i-1,i,k) + a(i-2,i,k+1), for i > 1. - Ross La Haye, May 29 2006

From Ross La Haye, Jun 03 2006: (Start)

a(3, 3, k+1) - a(3, 3, k) = A106517(k).

a(1, 1, k) = A001924(k) - A001924(k-1), for k > 0.

a(2, 1, k) = A001891(k) - A001891(k-1), for k > 0.

a(3, 1, k) = A023537(k) - A023537(k-1), for k > 0.

Sum_{j=0..i+1} a(i-j+1, 0, j) - Sum_{j=0..i} a(i-j, 0, j) = A001595(i). (End)

a(i,j,k) = a(j,j,k) + (i-j)*a(j,j,k-1), for k > 0.

a(n) ~ n^(n-1). - Vaclav Kotesovec, Jan 03 2021

Extensions

New name from Joerg Arndt, Jan 03 2021