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,3

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

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

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

Prog

(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
(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
(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

Crossrefs

Cf. A002530, A002531.

Bisections are A001835 and A052530.

Sequence in context: A119064 A285113 A335632 * A239453 A143914 A041123

Adjacent sequences: A048785 A048786 A048787 * A048789 A048790 A048791

Keyword

nonn,easy,frac

Author

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

Extensions

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

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

Status

approved