%I #33 Apr 26 2023 18:54:12
%S 1,2,6,18,58,186,602,1946,6298,20378,65946,213402,690586,2234778,
%T 7231898,23402906,75733402,245078426,793090458,2566494618,8305351066,
%U 26876680602,86974765466,281456253338,910811568538,2947448150426,9538142575002,30866077751706
%N 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.
%C a(n) ~ c*(sqrt(5)+1)^n, where c = (sqrt(5)+3)/10.
%C 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]
%C From _R. J. Mathar_, Oct 12 2010: (Start)
%C 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:
%C 1,2,4,8,16,32,64,128,256,512,1024,2048,4096,
%C 1,2,6,16,48,128,384,1024,3072,8192,24576,65536,196608,
%C 1,2,6,18,58,186,602,1946,6298,20378,65946,213402,690586,
%C 1,2,6,18,60,198,684,2322,8100,27702,96876,331938,1161540,
%C 1,2,6,18,60,200,698,2432,8658,30762,110374,395428,1422916,
%C 1,2,6,18,60,200,700,2448,8800,31552,115104,418176,1537536,
%C 1,2,6,18,60,200,700,2450,8818,31730,116182,425172,1573416,
%C 1,2,6,18,60,200,700,2450,8820,31750,116400,426600,1583400,
%C 1,2,6,18,60,200,700,2450,8820,31752,116422,426862,1585246,
%C 1,2,6,18,60,200,700,2450,8820,31752,116424,426886,1585556,
%C 1,2,6,18,60,200,700,2450,8820,31752,116424,426888,1585582,
%C (End)
%C 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]
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,2,-4).
%F G.f.: (1-x-2x^2)/(1-3x-2x^2+4x^3). - _Michael Somos_, Mar 04 2003
%F a(n) - 2*a(n-1) = A014334(n), n > 0. - _Vladeta Jovovic_, Mar 05 2003
%F From _Vladeta Jovovic_, Mar 05 2003: (Start)
%F 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.
%F Recurrence: a(n) = 3*a(n-1) + 2*a(n-2) - 4*a(n-3).
%F G.f.: (1+x)*(1-2*x)/(1-2*x-4*x^2)/(1-x). (End)
%F 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
%F a(n) = (2^n*Lucas(n+2)+2)/5. - _Ira M. Gessel_, Mar 06 2022
%Y a(n) = A052899(n-1) + A052899(n). a(n) - 2*a(n-1) = A014334(n).
%Y Cf. A000032, A000045, A000204.
%Y Row sums of A109906.
%K nonn
%O 0,2
%A _Paul D. Hanna_, Mar 03 2003
%E Corrected and extended by _Vladeta Jovovic_ and _Michael Somos_, Mar 05 2003