login
a(n) = a(n-1) + a(n-3) + a(n-4), where a(0) = 1, a(1) = 2, a(2) = 5, a(3) = 7.
0

%I #45 Jun 22 2023 13:32:07

%S 1,2,5,7,10,17,29,46,73,119,194,313,505,818,1325,2143,3466,5609,9077,

%T 14686,23761,38447,62210,100657,162865,263522,426389,689911,1116298,

%U 1806209,2922509,4728718,7651225,12379943,20031170,32411113,52442281,84853394

%N a(n) = a(n-1) + a(n-3) + a(n-4), where a(0) = 1, a(1) = 2, a(2) = 5, a(3) = 7.

%C For n >= 3, a(n) is also the number of ways to tile this "central staircase" figure of length n with squares and dominoes; this is the picture for length n=10:

%C _

%C _________|_|_______

%C |_|_|_|_|_|_|_|_|_|_|

%C |_|

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,1,1).

%F a(n) = a(n-1) + a(n-3) + a(n-4), where a(0) = 1, a(1) = 2, a(2) = 5, a(3) = 7.

%F G.f.: (1 + x + 3*x^2 + x^3)/((1 +x^2)*(1-x-x^2)).

%F a(2*n) = F(n+2)^2 + F(n)^2, a(2*n+1) = F(n+2)^2 + F(n+1)*L(n+1) for F(n) and L(n) the Fibonacci and Lucas numbers.

%F Sum_{k=0..n} a(k) = A295681(n+5) - 3.

%F 5*a(n) = 3*A000032(n+2) -2*A000034(n+1)*(-1)^floor(n/2). - _R. J. Mathar_, Jun 22 2023

%F a(n)+a(n+2) = 3*A000045(n+3). - _R. J. Mathar_, Jun 22 2023

%e Here is one of the a(10)=194 tilings for length n=10:

%e _

%e _________|_|_______

%e |___|___| |___|_|___|

%e |_|

%t LinearRecurrence[{1, 0, 1, 1}, { 1, 2, 5, 7}, 50]

%Y Cf. A000032, A000045, A195971, A295681, A347902.

%K nonn,easy

%O 0,2

%A _Greg Dresden_ and Jiaqi Wang, Jun 18 2023