A162485 a(1)=4, a(2)=6; for n > 2, a(n) = 2*a(n-1) + a(n-2) - 4*((n-1) mod 2).

4, 6, 16, 34, 84, 198, 480, 1154, 2788, 6726, 16240, 39202, 94644, 228486, 551616, 1331714, 3215044, 7761798, 18738640, 45239074, 109216788, 263672646, 636562080, 1536796802, 3710155684, 8957108166, 21624372016, 52205852194, 126036076404, 304278004998, 734592086400

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

Examples

			a(3) = 2*a(2) + a(1) - 4*(2 mod 2) = 2*6 + 4 - 0 = 16.
		

Links

• Paolo Xausa, 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. A002203.

Programs

Mathematica

LinearRecurrence[{2, 2, -2, -1}, {4, 6, 16, 34}, 50] (* Paolo Xausa, Jun 27 2025 *)

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