A048788 a(2n+1) = a(2n) + a(2n-1), a(2n) = 2*a(2n-1) + a(2n-2); a(n) = n for n = 0, 1.

0, 1, 2, 3, 8, 11, 30, 41, 112, 153, 418, 571, 1560, 2131, 5822, 7953, 21728, 29681, 81090, 110771, 302632, 413403, 1129438, 1542841, 4215120, 5757961, 15731042, 21489003, 58709048, 80198051, 219105150, 299303201, 817711552, 1117014753

Offset: 0

Author

Robin Trew (trew(AT)hcs.harvard.edu), Dec 11 1999

Keywords

• nonn
• easy
• frac

Comments

Numerators of continued fraction convergents to sqrt(3) - 1 (A160390). See A002530 for denominators. - N. J. A. Sloane, Dec 17 2007

Convergents are 1, 2/3, 3/4, 8/11, 11/15, 30/41, 41/56, 112/153, ... - Clark Kimberling, Sep 21 2013

A strong divisibility sequence, that is gcd(a(n),a(m)) = a(gcd(n,m)) for all positive integers n and m. - Peter Bala, Jun 06 2014

From Sarah-Marie Belcastro, Feb 15 2022: (Start)

a(n) is also the number of perfect matchings of an edge-labeled 2 X (n-1) Mobius band grid graph, or equivalently the number of domino tilings of a 2 X (n-1) Mobius band grid. (The twist is on the length-n side.)

a(n) is also the output of Lu and Wu's formula for the number of perfect matchings of an m X n Mobius band grid, specialized to m = 2 with the twist on the length-n side.

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

References

• Russell Lyons, A bird's-eye view of uniform spanning trees and forests, in Microsurveys in Discrete Probability, AMS, 1998.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Peter Bala, Notes on 2-periodic continued fractions and Lehmer sequences
• 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.
• Marcia Edson, Scott Lewis and Omer Yayenie, The k-periodic Fibonacci sequence and an extended Binet's formula, INTEGERS 11 (2011) #A32.
• W. T. Lu and F. Y. Wu, Close-packed dimers on nonorientable surfaces, Physics Letters A, 293 (2002), 235-246.
• D. Panario, M. Sahin, and Q. Wang, A family of Fibonacci-like conditional sequences, INTEGERS, Vol. 13, 2013, #A78.
• J. L. Ramirez and F. Sirvent, A q-Analogue of the Bi-Periodic Fibonacci Sequence, J. Int. Seq. 19 (2016) # 16.4.6, t_n at a=2, b=1.
• Index to divisibility sequences
• Index entries for linear recurrences with constant coefficients, signature (0,4,0,-1).

Crossrefs

Cf. A002530, A002531.

Bisections are A001835 and A052530.

Programs

GAP

a:=[0,1,2,3];; for n in [5..40] do a[n]:=4a[n-1]-a[n-2]; od; a; # G. C. Greubel, Dec 23 2019

Magma

I:=[0,1,2,3]; [n le 4 select I[n] else 4*Self(n-2)-Self(n-4): n in [1..40]]; // Vincenzo Librandi, Dec 10 2013

Maple

seq( simplify( `if`(`mod`(n,2)=0, 2*ChebyshevU((n-2)/2, 2), ChebyshevU((n-1)/2, 2) - ChebyshevU((n-3)/2, 2)) ), n=0..40); # G. C. Greubel, Dec 23 2019

Mathematica

Numerator[NestList[(2/(2 + #))&, 0, 40]] (* Vladimir Joseph Stephan Orlovsky, Apr 13 2010 *)
CoefficientList[Series[x(1+2x-x^2)/(1-4x^2+x^4), {x, 0, 40}], x] (* Vincenzo Librandi, Dec 10 2013 *)
a0[n_]:= ((3+Sqrt[3])*(2-Sqrt[3])^n-((-3+Sqrt[3])*(2+Sqrt[3])^n))/6 // Simplify
a1[n_]:= 2*Sum[a0[i], {i, 1, n}]
Flatten[MapIndexed[{a1[#-1],a0[#]}&,Range[20]]] (* Gerry Martens, Jul 10 2015 *)
Round@Table[With[{r=1+Sqrt[2], s=1+Sqrt[3]}, ((r + (-1)^n/r) s^n/2^(n/2) - (1/r + (-1)^n r) 2^(n/2)/s^n) Sqrt[6]/12], {n, 0, 20}] (* or *) LinearRecurrence[ {0,4,0,-1}, {0,1,2,3}, 40] (* Vladimir Reshetnikov, May 11 2016 *)
Table[If[EvenQ[n], 2*ChebyshevU[(n-2)/2, 2], ChebyshevU[(n-1)/2, 2] - ChebyshevU[(n-3)/2, 2]], {n, 0, 40}] (* G. C. Greubel, Dec 23 2019 *)

PARI

main(size)=v=vector(size); v[1]=0;v[2]=1;v[3]=2;v[4]=3;for(i=5, size, v[i]=4*v[i-2] - v[i-4]); v; \\ Anders Hellström, Jul 11 2015

PARI

a=vector(50); a[1]=1; a[2]=2; for(n=3, #a, if(n%2==1, a[n]=a[n-1]+a[n-2], a[n]=2*a[n-1]+a[n-2])); concat(0, a) \\ Colin Barker, Jan 30 2016

PARI

a(n)=([0,1,0,0;0,0,1,0;0,0,0,1;-1,0,4,0]^n*[0;1;2;3])[1,1] \\ Charles R Greathouse IV, Mar 16 2017

PARI

apply( {A048788(n)=imag((2+quadgen(12))^(n\/2)*if(bittest(n, 0), quadgen(12)-1, 2))}, [0..30]) \\ M. F. Hasler, Nov 04 2019

PARI

{a(n) = my(s=1,m=n); if(n<0,s=-(-1)^n; m=-n); polcoeff(x*(1+2*x-x^2)/(1-4*x^2+x^4) + x*O(x^m), m)*s}; /* Michael Somos, Sep 17 2020 */

Sage

@CachedFunction
def a(n):
    if (mod(n,2)==0): return 2*chebyshev_U((n-2)/2, 2)
    else: return chebyshev_U((n-1)/2, 2) - chebyshev_U((n-3)/2, 2)
[a(n) for n in (0..40)] # G. C. Greubel, Dec 23 2019

Formula

G.f.: x*(1+2*x-x^2)/(1-4*x^2+x^4). - Paul Barry, Sep 18 2009

a(n) = 4*a(n-2) - a(n-4). - Vincenzo Librandi, Dec 10 2013

a(2*n-1) = A001835(n); a(2*n) = 2*A001353(n). - Peter Bala, Jun 06 2014

From Gerry Martens, Jul 11 2015: (Start)

Interspersion of 2 sequences [a1(n-1),a0(n)] for n>0:

a0(n) = ((3+sqrt(3))*(2-sqrt(3))^n-((-3+sqrt(3))*(2+sqrt(3))^n))/6.

a1(n) = 2*Sum_{i=1..n} a0(i). (End)

a(n) = ((r + (-1)^n/r)*s^n/2^(n/2) - (1/r + (-1)^n*r)*2^(n/2)/s^n)*sqrt(6)/12, where r = 1 + sqrt(2), s = 1 + sqrt(3). - Vladimir Reshetnikov, May 11 2016

a(n) = 2*ChebyshevU(n-1, 2) if n is even and ChebyshevU(n, 2) - ChebyshevU(n-1, 2) if n in odd. - G. C. Greubel, Dec 23 2019

a(n) = -(-1)^n*a(-n) for all n in Z. - Michael Somos, Sep 17 2020

Extensions

Denominator of g.f. corrected by Paul Barry, Sep 18 2009

Incorrect g.f. deleted by Colin Barker, Aug 10 2012