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

%I #128 Nov 20 2023 00:04:56

%S 0,1,2,3,8,11,30,41,112,153,418,571,1560,2131,5822,7953,21728,29681,

%T 81090,110771,302632,413403,1129438,1542841,4215120,5757961,15731042,

%U 21489003,58709048,80198051,219105150,299303201,817711552,1117014753

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

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

%C Convergents are 1, 2/3, 3/4, 8/11, 11/15, 30/41, 41/56, 112/153, ... - _Clark Kimberling_, Sep 21 2013

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

%C From _Sarah-Marie Belcastro_, Feb 15 2022: (Start)

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

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

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

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

%H Vincenzo Librandi, <a href="/A048788/b048788.txt">Table of n, a(n) for n = 0..1000</a>

%H Peter Bala, <a href="/A243469/a243469_1.pdf">Notes on 2-periodic continued fractions and Lehmer sequences</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 Marcia Edson, Scott Lewis and Omer Yayenie, <a href="http://www.emis.de/journals/INTEGERS/papers/l32/l32.Abstract.html">The k-periodic Fibonacci sequence and an extended Binet's formula</a>, INTEGERS 11 (2011) #A32.

%H W. T. Lu and F. Y. Wu, <a href="http://dx.doi.org/10.1016/S0375-9601(02)00019-1">Close-packed dimers on nonorientable surfaces</a>, Physics Letters A, 293 (2002), 235-246.

%H D. Panario, M. Sahin, and Q. Wang, <a href="http://www.emis.de/journals/INTEGERS/papers/n78/n78.Abstract.html">A family of Fibonacci-like conditional sequences</a>, INTEGERS, Vol. 13, 2013, #A78.

%H J. L. Ramirez and F. Sirvent, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Ramirez/ramirez9.html">A q-Analogue of the Bi-Periodic Fibonacci Sequence</a>, J. Int. Seq. 19 (2016) # 16.4.6, t_n at a=2, b=1.

%H <a href="/index/Di#divseq">Index to divisibility sequences</a>

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

%F G.f.: x*(1+2*x-x^2)/(1-4*x^2+x^4). - _Paul Barry_, Sep 18 2009

%F a(n) = 4*a(n-2) - a(n-4). - _Vincenzo Librandi_, Dec 10 2013

%F a(2*n-1) = A001835(n); a(2*n) = 2*A001353(n). - _Peter Bala_, Jun 06 2014

%F From _Gerry Martens_, Jul 11 2015: (Start)

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

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

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

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

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

%F a(n) = -(-1)^n*a(-n) for all n in Z. - _Michael Somos_, Sep 17 2020

%p 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

%t Numerator[NestList[(2/(2 + #))&, 0, 40]] (* _Vladimir Joseph Stephan Orlovsky_, Apr 13 2010 *)

%t CoefficientList[Series[x(1+2x-x^2)/(1-4x^2+x^4), {x, 0, 40}], x] (* _Vincenzo Librandi_, Dec 10 2013 *)

%t a0[n_]:= ((3+Sqrt[3])*(2-Sqrt[3])^n-((-3+Sqrt[3])*(2+Sqrt[3])^n))/6 // Simplify

%t a1[n_]:= 2*Sum[a0[i], {i, 1, n}]

%t Flatten[MapIndexed[{a1[#-1],a0[#]}&,Range[20]]] (* _Gerry Martens_, Jul 10 2015 *)

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

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

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

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

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

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

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

%o (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 */

%o (Sage)

%o @CachedFunction

%o def a(n):

%o if (mod(n,2)==0): return 2*chebyshev_U((n-2)/2, 2)

%o else: return chebyshev_U((n-1)/2, 2) - chebyshev_U((n-3)/2, 2)

%o [a(n) for n in (0..40)] # _G. C. Greubel_, Dec 23 2019

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

%Y Cf. A002530, A002531.

%Y Bisections are A001835 and A052530.

%K nonn,easy,frac

%O 0,3

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

%E Denominator of g.f. corrected by _Paul Barry_, Sep 18 2009

%E Incorrect g.f. deleted by _Colin Barker_, Aug 10 2012