A098703 -id:A098703 - cp's OEIS frontend

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

Ross La Haye, Dec 14 2004

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

			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.

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

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.

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

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

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

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

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

New name from Joerg Arndt, Jan 03 2021

A090888 Matrix defined by a(n,k) = 3^nFibonacci(k) - 2^nFibonacci(k-2), read by antidiagonals.

Original entry on oeis.org

1, 2, 0, 4, 1, 1, 8, 5, 3, 1, 16, 19, 9, 4, 2, 32, 65, 27, 14, 7, 3, 64, 211, 81, 46, 23, 11, 5, 128, 665, 243, 146, 73, 37, 18, 8, 256, 2059, 729, 454, 227, 119, 60, 29, 13, 512, 6305, 2187, 1394, 697, 373, 192, 97, 47, 21, 1024, 19171, 6561, 4246, 2123, 1151, 600, 311

Offset: 0

Ross La Haye, Feb 12 2004; revised Sep 24 2004, Sep 10 2005

a(0,k) = A000045(k-1); a(1,k) = A000032(k); a(2,k) = A000285(k+1).
a(n,1) = a(n-1,1) + a(n-1,3) for n > 0; a(n,1) = A001047(n) = 2^(2n) - A083324(n); a(n,2) = A000244(n) = 2^(2n) - A005061(n); a(n,3) = 2a(n-1,4) for n > 0; a(n,3) = A027649(n); a(n,4) = A083313(n+1); a(n,5) = A084171(n+1).
Sum[a(n-k,k), {k,0,n}] = A098703(n+1), antidiagonal sums.
Let R, S and T be binary relations on the power set P(A) of a set A having n = |A| elements such that for every element x, y of P(A), xRy if x is a subset of y or y is a subset of x, xSy if x is a subset of y and xTy if x is a proper subset of y. Then a(n,3) = |R|, a(n,2) = |S| and a(n,1) = |T|. Note that a binary relation W on P(A) can be defined also such that for every element x, y of P(A) xWy if x is a proper subset of y and there are no z in P(A) such that x is a proper subset of z and z is a proper subset of y. A090802(n,1) = |W|. Also, a(n,0) = |P(A)|.

			   1    0    1    1    2    3    5    8    13    21    34
   2    1    3    4    7   11   18   29    47    76   123
   4    5    9   14   23   37   60   97   157   254   411
   8   19   27   46   73  119  192  311   503   814  1317
  16   65   81  146  227  373  600  973  1573  2546  4119
  32  211  243  454  697 1151 1848 2999  4847  7846 12693
  64  665  729 1394 2123 3517 5640 9157 14797 23954 38751
a(5,3) = 454 because Fibonacci(3) = 2, Fibonacci(1) = 1 and (2 * 3^5) - (1 * 2^5) = 454.

Michael De Vlieger, Table of n, a(n) for n = 0..10000
Ross La Haye, Binary relations on the power set of an n-element set, JIS 12 (2009) 09.2.6, table 4.
Eric Weisstein, Fibonacci Number
Eric Weisstein, Lucas Number

Table[3^(n - k) Fibonacci@ k - 2^(n - k) Fibonacci[k - 2], {n, 0, 10}, {k, 0, n}] // Flatten (* Michael De Vlieger, Nov 28 2015 *)

a(n, k) = 3^n*Fibonacci(k) - 2^n*Fibonacci(k-2).
a(n, 0) = 2^n, a(n, 1) = 3^n - 2^n, a(n, k) = a(n, k-1) + a(n, k-2) for k > 1.
a(0, k) = Fibonacci(k-1), a(1, k) = Lucas(k), a(n, k) = 5a(n-1, k) - 6a(n-2, k) for n > 1.
O.g.f. (by rows) = (-2^n + (2^(n+1) - 3^n)x)/(-1+x+x^2). - Ross La Haye, Mar 30 2006
a(n,1) - a(n,0) = A003063(n+1). - Ross La Haye, Jun 22 2007
Binomial transform (by columns) of A118654. - Ross La Haye, Jun 22 2007

More terms from Ray Chandler, Oct 27 2004

A099159 a(n) = (L(n-2)+2*3^n)/5.

Original entry on oeis.org

1, 1, 4, 11, 33, 98, 293, 877, 2628, 7879, 23629, 70874, 212601, 637769, 1913252, 5739667, 17218857, 51656338, 154968637, 464905301, 1394714916, 4184143151, 12552426869, 37657276426, 112971822513, 338915456593, 1016746352068, 3050239027547, 9150717036273

Offset: 0

Paul Barry, Oct 01 2004

Binomial transform of A052964.

Paolo Xausa, Table of n, a(n) for n = 0..1000
Amya Luo, Pattern Avoidance in Nonnesting Permutations, Undergraduate Thesis, Dartmouth College (2024). See p. 16.
Index entries for linear recurrences with constant coefficients, signature (4,-2,-3).

Cf. A000032, A052964, A098703, A101220,

A099159[n_] := (LucasL[n-2] + 2*3^n)/5; Array[A099159, 30, 0] (* or *)
LinearRecurrence[{4, -2, -3}, {1, 1, 4}, 30] (* Paolo Xausa, Jun 20 2024 *)

G.f.: (1-3*x+2*x^2)/((1-3*x)*(1-x-x^2)).
a(n) = ((1+sqrt(5))/2)^n*(3/10-sqrt(5)/10) + ((1-sqrt(5))/2)^n*(3/10+sqrt(5)/10) + 3^n*2/5.
a(n) = Sum_{k=0..n} (-2*0^k-Fib(k-4)) * 3^(n-k).
a(n) = A098703(n+1) - A098703(n). - Ross La Haye, Sep 11 2005

A095930 Number of walks of length 2n between two nodes at distance 2 in the cycle graph C_10.

Original entry on oeis.org

1, 4, 15, 57, 220, 859, 3381, 13380, 53143, 211585, 843756, 3368259, 13455325, 53774932, 214978335, 859595529, 3437550076, 13748021995, 54986385093, 219930610020, 879683351911, 3518631073489, 14074256379660, 56296324109907, 225183460127725, 900729032983924

Offset: 1

Herbert Kociemba, Jul 12 2004

In general (2^n/m)*Sum_{r=0..m-1} cos(2*Pi*k*r/m)*cos(2*Pi*r/m)^n is the number of walks of length n between two nodes at distance k in the cycle graph C_m. Here we have m=10 and k=2.

Equals INVERT transform of A014138: (1, 3, 8, 22, 64, 196, ...). - Gary W. Adamson, May 15 2009

Colin Barker, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (7,-13,4)

Cf. A014138.

f[n_]:=FullSimplify[TrigToExp[(4^n/10)Sum[Cos[2Pi*k/5]Cos[Pi*k/5]^(2n), {k, 0, 9}]]];Table[f[n], {n, 1, 35}]

Vec((-x+3*x^2)/((-1+4*x)*(1-3*x+x^2)) + O(x^50)) \\ Colin Barker, Apr 27 2016

a(n) = (4^n/10)*Sum_{r=0..9} cos(2*Pi*r/5)*cos(Pi*r/5)^(2*n).
a(n) = 7*a(n-1) - 13*a(n-2) + 4*a(n-3).
G.f.: (-x+3*x^2)/((-1+4*x)*(1-3*x+x^2)).
a(n) = (4^n + Lucas(2*n-1))/5. With a(0) = 0, binomial transform of A098703. - Ross La Haye, May 31 2006
a(n) = (2^(-1-n)*(2^(1+3*n) - (3-sqrt(5))^n*(1+sqrt(5)) + (-1+sqrt(5))*(3+sqrt(5))^n))/5. - Colin Barker, Apr 27 2016
E.g.f.: (2*exp(4*x) + (-1 - sqrt(5))*exp(((3 - sqrt(5))*x)/2) + (-1 + sqrt(5))*exp(((3 + sqrt(5))*x)/2))/10. - Ilya Gutkovskiy, Apr 27 2016

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A090888 Matrix defined by a(n,k) = 3^n*Fibonacci(k) - 2^n*Fibonacci(k-2), read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

Formula

Extensions

A099159 a(n) = (L(n-2)+2*3^n)/5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A095930 Number of walks of length 2n between two nodes at distance 2 in the cycle graph C_10.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A090888 Matrix defined by a(n,k) = 3^nFibonacci(k) - 2^nFibonacci(k-2), read by antidiagonals.