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
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
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Mar 03 2003
EXTENSIONS
Corrected and extended by Vladeta Jovovic and Michael Somos, Mar 05 2003
STATUS
approved