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

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

Table of n, a(n) for n=0..27.

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

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

Crossrefs

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

Cf. A000032, A000045, A000204.

Row sums of A109906.

Sequence in context: A351787 A307755 A304200 * A000137 A151282 A193777

Adjacent sequences: A081054 A081055 A081056 * A081058 A081059 A081060

Keyword

nonn

Author

Paul D. Hanna, Mar 03 2003

Extensions

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

Status

approved