A081057 E.g.f.: Sum_{n>=0} a(n)*x^n/n! = {Sum_{n>=0} F(n+1)*x^n/n!}^2, where F(n) is the n-th Fibonacci number.

1, 2, 6, 18, 58, 186, 602, 1946, 6298, 20378, 65946, 213402, 690586, 2234778, 7231898, 23402906, 75733402, 245078426, 793090458, 2566494618, 8305351066, 26876680602, 86974765466, 281456253338, 910811568538, 2947448150426, 9538142575002, 30866077751706

Offset: 0

Author

Paul D. Hanna, Mar 03 2003

Keywords

• nonn

Comments

a(n) ~ c*(sqrt(5)+1)^n, where c = (sqrt(5)+3)/10.

The inverse binomial transform is 1,1,3,5,... (1 followed by A056487). Partial sum of 1,1,4,12,..., i.e., 1 plus n-th partial sum of A087206. [R. J. Mathar, Oct 04 2010]

From R. J. Mathar, Oct 12 2010: (Start)

Apparently the row n=4 of an array which counts walks with k steps on an n X n board, starting at a corner, each step to one of the <= 4 adjacent squares:

1,2,4,8,16,32,64,128,256,512,1024,2048,4096,

1,2,6,16,48,128,384,1024,3072,8192,24576,65536,196608,

1,2,6,18,58,186,602,1946,6298,20378,65946,213402,690586,

1,2,6,18,60,198,684,2322,8100,27702,96876,331938,1161540,

1,2,6,18,60,200,698,2432,8658,30762,110374,395428,1422916,

1,2,6,18,60,200,700,2448,8800,31552,115104,418176,1537536,

1,2,6,18,60,200,700,2450,8818,31730,116182,425172,1573416,

1,2,6,18,60,200,700,2450,8820,31750,116400,426600,1583400,

1,2,6,18,60,200,700,2450,8820,31752,116422,426862,1585246,

1,2,6,18,60,200,700,2450,8820,31752,116424,426886,1585556,

1,2,6,18,60,200,700,2450,8820,31752,116424,426888,1585582,

(End)

Decomposing rook walks of length=n on a 4 X 4 board into combinations of independent vertical and horizontal walks in 4-wide corridors leads to an exponential convolution of the Fibonacci numbers, cf. A052899. [David Scambler, Oct 17 2010]

Links

• Index entries for linear recurrences with constant coefficients, signature (3,2,-4).

Crossrefs

a(n) = A052899(n-1) + A052899(n). a(n) - 2*a(n-1) = A014334(n).

Cf. A000032, A000045, A000204.

Row sums of A109906.

Formula

G.f.: (1-x-2x^2)/(1-3x-2x^2+4x^3). - Michael Somos, Mar 04 2003

a(n) - 2*a(n-1) = A014334(n), n > 0. - Vladeta Jovovic, Mar 05 2003

From Vladeta Jovovic, Mar 05 2003: (Start)

a(n) = 2/5 + (3/10 - 1/10*5^(1/2))*(1 - 5^(1/2))^n + (3/10 + 1/10*5^(1/2))*(1 + 5^(1/2))^n.

Recurrence: a(n) = 3*a(n-1) + 2*a(n-2) - 4*a(n-3).

G.f.: (1+x)*(1-2*x)/(1-2*x-4*x^2)/(1-x). (End)

a(n) = Sum_{k=0..n} ( F(k+1) * F(n-k+1) * C(n,k) ), where F(k) = Fibonacci(k). - David Scambler, Oct 17 2010

a(n) = (2^n*Lucas(n+2)+2)/5. - Ira M. Gessel, Mar 06 2022

Extensions

Corrected and extended by Vladeta Jovovic and Michael Somos, Mar 05 2003