OFFSET
0,2
COMMENTS
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:
_
_________|_|_______
|_|_|_|_|_|_|_|_|_|_|
|_|
LINKS
Index entries for linear recurrences with constant coefficients, signature (1,0,1,1).
FORMULA
a(n) = a(n-1) + a(n-3) + a(n-4), where a(0) = 1, a(1) = 2, a(2) = 5, a(3) = 7.
G.f.: (1 + x + 3*x^2 + x^3)/((1 +x^2)*(1-x-x^2)).
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.
Sum_{k=0..n} a(k) = A295681(n+5) - 3.
a(n)+a(n+2) = 3*A000045(n+3). - R. J. Mathar, Jun 22 2023
EXAMPLE
Here is one of the a(10)=194 tilings for length n=10:
_
_________|_|_______
|___|___| |___|_|___|
|_|
MATHEMATICA
LinearRecurrence[{1, 0, 1, 1}, { 1, 2, 5, 7}, 50]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Greg Dresden and Jiaqi Wang, Jun 18 2023
STATUS
approved