OFFSET
0,1
COMMENTS
This is a specialization for m=2 of a general formula for the number of perfect matchings of an edge-labeled m X (2n+1) Mobius grid graph.
LINKS
Clark Kimberling, Table of n, a(n) for n = 0..1000
G. Tesler, Matchings in graphs on non-orientable surfaces, Journal of Combinatorial Theory B, 78(2000), 198-231.
Index entries for linear recurrences with constant coefficients, signature (4,-4,1).
FORMULA
a(n) = Real((1-I) * ((L(2*n+1) - F(2*n+1))/2 + F(2*n+2) + 2*I)).
From R. J. Mathar, Aug 08 2009: (Start)
a(n) = 4*a(n-1) - 4*a(n-2) + a(n-3).
G.f.: (3-6*x+x^2)/((1-x)*(x^2-3*x+1)). (End)
a(n+1)-a(n) = A005248(n+1). - R. J. Mathar, Dec 18 2010
a(n) = A000032(2n+1)+2. - Clark Kimberling, Oct 26 2012
a(n) = 2^(-1-n)*(2^(2+n)-(3-sqrt(5))^n*(-1+sqrt(5))+(1+sqrt(5))*(3+sqrt(5))^n). - Colin Barker, Nov 03 2016
a(n) = 2 + L(2*n+1), A256233(n) = -a(-n-1) for all n in Z. - Michael Somos, Nov 03 2016
EXAMPLE
G.f. = 3 + 6*x + 13*x^2 + 31*x^3 + 78*x^4 + 201*x^5 + 523*x^6 + 1366*x^7 + ...
a(0) = 3 because this is the number of perfect matchings of a 2 X 1 Mobius grid graph (one for each of the three multiple edges).
MATHEMATICA
Table[Re[(1 - I) (2*I + Fibonacci[2 + 2*n] + 1/2 (-Fibonacci[1 + 2*n] + LucasL[1 + 2*n]))], {n, 0, 30}]
Table[LucasL[2*n + 1] + 2, {n, 0, 30}] (* Clark Kimberling, Oct 26 2012 *)
LinearRecurrence[{4, -4, 1}, {3, 6, 13}, 30] (* or *) CoefficientList[Series[(-3 + 6 x - x^2)/(-1 + 4 x - 4 x^2 + x^3), {x, 0, 30}], x] (* Stefano Spezia, Sep 23 2018 *)
PROG
(PARI) {a(n) = 2 + fibonacci(2*n) + fibonacci(2*n+2)}; /* Michael Somos, Nov 03 2016 */
(Magma) m:=25; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!((3-6*x+x^2)/((1-x)*(x^2-3*x+1)))); // G. C. Greubel, Sep 22 2018
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Sarah-Marie Belcastro, Jul 04 2009
STATUS
approved