A162484 a(1) = 2, a(2) = 8; a(n) = 2 a(n - 1) + a(n - 2) - 4*(n mod 2).

2, 8, 14, 36, 82, 200, 478, 1156, 2786, 6728, 16238, 39204, 94642, 228488, 551614, 1331716, 3215042, 7761800, 18738638, 45239076, 109216786, 263672648, 636562078, 1536796804, 3710155682, 8957108168, 21624372014, 52205852196, 126036076402, 304278005000

Offset: 1

Author

Sarah-Marie Belcastro, Jul 04 2009

Keywords

• easy
• nonn

Comments

a(n) is the number of perfect matchings of an edge-labeled 2 X n toroidal grid graph, or equivalently the number of domino tilings of a 2 X n toroidal grid.

Examples

			a(3) = 2 a(2) + a(1) - 4*(3 mod 2) = 2*8 + 2 - 4 = 14.
		

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• 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).

Crossrefs

Cf. A000129.

Programs

Mathematica

Fold[Append[#1, 2 #1[[#2 - 1]] + #1[[#2 - 2]] - 4 Mod[#2, 2]] &, {2, 8}, Range[3, 30]] (* or *)
Rest@ CoefficientList[Series[-2 x (-1 - 2 x + 3 x^2 + 2 x^3)/((x - 1) (1 + x) (x^2 + 2 x - 1)), {x, 0, 30}], x] (* Michael De Vlieger, Dec 16 2017 *)
LinearRecurrence[{2,2,-2,-1},{2,8,14,36},30] (* Harvey P. Dale, Aug 24 2018 *)

Formula

for n > 2, (1/2) ((1 + sqrt(2))^n (2 - (-2 + sqrt(2)) (-1 + sqrt(2))^(2 floor(n/2))) + (1 - sqrt(2))^n (2 + (1 + sqrt(2))^(2 floor(n/2)) (2 + sqrt(2)))) (from Mathematica's solution to the recurrence).

Pell(n) + Pell(n-2) + 2*((n-1) mod 2).

From R. J. Mathar, Jul 26 2009: (Start)

a(n)= 2*a(n-1) + 2*a(n-2) - 2*a(n-3) - a(n-4) = 2*A100828(n-1).

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

(End)

a(n) = 1 + (-1)^n + (1-sqrt(2))^n + (1+sqrt(2))^n. - Colin Barker, Dec 16 2017