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

%I #28 Nov 20 2023 00:05:18

%S 2,8,14,36,82,200,478,1156,2786,6728,16238,39204,94642,228488,551614,

%T 1331716,3215042,7761800,18738638,45239076,109216786,263672648,

%U 636562078,1536796804,3710155682,8957108168,21624372014,52205852196,126036076402,304278005000

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

%C 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.

%H Colin Barker, <a href="/A162484/b162484.txt">Table of n, a(n) for n = 1..1000</a>

%H Sarah-Marie Belcastro, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Belcastro/belcastro4.html">Domino Tilings of 2 X n Grids (or Perfect Matchings of Grid Graphs) on Surfaces</a>, J. Integer Seq. 26 (2023), Article 23.5.6.

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

%F 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).

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

%F From _R. J. Mathar_, Jul 26 2009: (Start)

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

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

%F (End)

%F a(n) = 1 + (-1)^n + (1-sqrt(2))^n + (1+sqrt(2))^n. - _Colin Barker_, Dec 16 2017

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

%t Fold[Append[#1, 2 #1[[#2 - 1]] + #1[[#2 - 2]] - 4 Mod[#2, 2]] &, {2, 8}, Range[3, 30]] (* or *)

%t 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 *)

%t LinearRecurrence[{2,2,-2,-1},{2,8,14,36},30] (* _Harvey P. Dale_, Aug 24 2018 *)

%Y Cf. A000129.

%K easy,nonn

%O 1,1

%A _Sarah-Marie Belcastro_, Jul 04 2009