OFFSET
1,1
COMMENTS
a(n) is the number of perfect matchings of an edge-labeled 2 X n Klein bottle grid graph, or equivalently the number of domino tilings of a 2 X n Klein bottle grid. (The twist is on the length-2 side.)
LINKS
Sarah-Marie Belcastro, Domino Tilings of 2 X n Grids (or Perfect Matchings of Grid Graphs) on Surfaces, J. Integer Seq. 26 (2023), Article 23.5.6.
Index entries for linear recurrences with constant coefficients, signature (2,2,-2,-1).
FORMULA
For n > 1, a(n) = (1/2)*((1 + sqrt(2))^n*(2 + (-1 + sqrt(2))^(2*floor((1/2)*(-1 + n)))*(-4 + 3*sqrt(2))) + (1 - sqrt(2))^n*(2 - (-1 - sqrt(2))^(2*floor((1/2)*(-1 + n)))*(4 + 3*sqrt(2)))).
From Colin Barker, May 01 2012: (Start)
a(n) = 1 - (-1)^n + (1-sqrt(2))^n + (1+sqrt(2))^n.
G.f.: 2*x*(2-x-2*x^2-x^3)/(1-x)/(1+x)/(1-2*x-x^2). (End)
a(n) = A002203(n) + 1 - (-1)^n. - R. J. Mathar, Oct 08 2016
EXAMPLE
a(3) = 2*a(2) + a(1) - 4*(2 mod 2) = 2*6 + 4 - 0 = 16.
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Sarah-Marie Belcastro, Jul 04 2009
STATUS
approved