OFFSET
0,1
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
G.f.: (8 - 3*x + 8*x^2 + 9*x^3)/((1-x-x^2)*(1+x^2)).
a(n) = (7*Lucas(n+3) + 6*i^(n*(n+1))*(3-(-1)^n))/5 where i = sqrt(-1).
E.g.f.: (12*cos(x) - 24*sin(x) + 14*exp(x/2)*(2*cosh(sqrt(5)*x/2) + sqrt(5)*sinh(sqrt(5)*x/2)))/5. - Stefano Spezia, Sep 18 2021
From Greg Dresden, Mar 19 2024: (Start)
a(2*n) = (7*Lucas(2*n+3) + 12*(-1)^n)/5.
a(2*n+1) = (7*Lucas(2*n+4) - 24*(-1)^n)/5. (End)
EXAMPLE
Here is one of the a(10)=727 tilings for n=10.
_
_| |_
_______| |_|_|_____
|_|___|_|_|___|_|___|
MATHEMATICA
LinearRecurrence[{1, 0, 1, 1}, {8, 5, 13, 30}, 33]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Reeva Bohra and Greg Dresden, Sep 18 2021
STATUS
approved