%I #133 Mar 12 2024 23:50:06
%S 0,2,8,30,112,418,1560,5822,21728,81090,302632,1129438,4215120,
%T 15731042,58709048,219105150,817711552,3051741058,11389252680,
%U 42505269662,158631825968,592022034210,2209456310872,8245803209278,30773756526240
%N a(n) = 4*a(n-1) - a(n-2), with a(0) = 0, a(1) = 2.
%C a(n-1) and a(n+1) are the solutions for c if b = a(n) in (b^2 + c^2)/(b*c + 1) = 4 and there are no other pairs of solutions apart from consecutive pairs of terms in this sequence. Cf. A061167. - _Henry Bottomley_, Apr 18 2001
%C a(n)^2 for n >= 1 gives solutions to A007913(3*x+4) = A007913(x). - _Benoit Cloitre_, Apr 07 2002
%C For all terms k of the sequence, 3*k^2 + 4 is a perfect square. Limit_{n->oo} a(n)/a(n-1) = 2 + sqrt(3). - _Gregory V. Richardson_, Oct 06 2002
%C a(n) = the number of compositions of the integer 2*n into even parts, where each part 2*i comes in 2*i colors. (Dedrickson, Theorem 3.2.6) An example is given below. Cf. A052529, A095263. - _Peter Bala_, Sep 17 2013
%C Except for an initial 1, this is the p-INVERT of (1, 1, 1, 1, 1, ...) for p(S) = 1 - 2*S - 2*S^2; see A291000. - _Clark Kimberling_, Aug 24 2017
%C a(n+1) is the number of spanning trees of the graph P_n, where P_n is a 2 X n grid with two additional vertices, u and v, where u is adjacent to (1,1) and (2,1), and v is adjacent to (1,n) and (2,n). - _Kevin Long_, May 04 2018
%C a(n) is also the output of Tesler's formula for the number of perfect matchings of an m X n Mobius band where m is even and n is odd, specialized to m=2. (The twist is on the length-n side.) - _Sarah-Marie Belcastro_, Feb 15 2022
%C In general, values of x and y which satisfy (x^2 + y^2)/(x*y + 1) = k^2 are any two adjacent terms of a second-order recurrence with initial terms 0 and k and signature (k^2,-1). This can also be expressed as a first-order recurrence a(n+1) = (k^2*a(n) + sqrt((k^4-4)*a(n)^2 + 4*k^2))/2, n > 1. - _Gary Detlefs_, Feb 27 2024
%H T. D. Noe, <a href="/A052530/b052530.txt">Table of n, a(n) for n = 0..200</a>
%H K. Andersen, L. Carbone, and D. Penta, <a href="https://pdfs.semanticscholar.org/8f0c/c3e68d388185129a56ed73b5d21224659300.pdf">Kac-Moody Fibonacci sequences, hyperbolic golden ratios, and real quadratic fields</a>, Journal of Number Theory and Combinatorics, Vol 2, No. 3 pp 245-278, 2011. See Section 9.
%H Hacène Belbachir, Soumeya Merwa Tebtoub, and László Németh, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Nemeth/nemeth7.html">Ellipse Chains and Associated Sequences</a>, J. Int. Seq., Vol. 23 (2020), Article 20.8.5.
%H Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, <a href="https://arxiv.org/abs/1707.07798">(an + b)-color compositions</a>, arXiv:1707.07798 [math.CO], 2017.
%H Niccolò Castronuovo, <a href="https://arxiv.org/abs/2102.02739">On the number of fixed points of the map gamma</a>, arXiv:2102.02739 [math.NT], 2021. Mentions this sequence.
%H C. R. Dedrickson III, <a href="https://digitalcommons.georgiasouthern.edu/etd/17">Compositions, Bijections, and Enumerations</a> Thesis, 2012, Jack N. Averitt College of Graduate Studies, Georgia Southern University.
%H J.-P. Ehrmann et al., <a href="http://forumgeom.fau.edu/POLYA/ProblemCenter/POLYA002.html">Problem POLYA002</a>, Integer pairs (x,y) for which (x^2+y^2)/(1+pxy) is an integer.
%H F. Goebel and A. A. Jagers, <a href="http://dx.doi.org/10.1016/0095-8956(79)90010-8">On a conjecture of Tutte concerning minimal tree numbers</a>, J. Combin. Theory Ser. B 26 (1979), no. 3, 346-348. MR0535948 (80m:05064). [From _N. J. A. Sloane_, Feb 20 2012]
%H A. F. Horadam, <a href="http://www.fq.math.ca/Scanned/3-3/horadam.pdf">Basic Properties of a Certain Generalized Sequence of Numbers</a>, Fibonacci Quarterly, Vol. 3, No. 3, 1965, pp. 161-176.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=460">Encyclopedia of Combinatorial Structures 460</a>
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H G. Tesler, <a href="https://doi.org/10.1006/jctb.1999.1941">Matchings in graphs on non-orientable surfaces</a>, Journal of Combinatorial Theory B, 78(2000), 198-231.
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,-1).
%F G.f.: 2*x/(1 - 4*x + x^2).
%F Invert transform of even numbers: a(n) = 2*Sum_{k=1..n} k*a(n-k). - _Vladeta Jovovic_, Apr 27 2001
%F From _Gregory V. Richardson_, Oct 06 2002: (Start)
%F a(n) = Sum(-(1/3)*(-1 + 2*alpha)*alpha^(-1 - n), alpha = root of (1 - 4*Z + Z^2),
%F a(n) = (((2+sqrt(3))^(n+1) -(2-sqrt(3))^(n+1)) -((2+sqrt(3))^(n) -(2 -sqrt(3))^(n)) +((2+sqrt(3))^(n-1) -(2-sqrt(3))^(n-1)))/(3*sqrt(3)). (End)
%F a(n) = A071954(n) - 2. - _N. J. A. Sloane_, Feb 20 2005
%F a(n) = (2*sinh(2n*arcsinh(1/sqrt(2))))/sqrt(3). - _Herbert Kociemba_, Apr 24 2008
%F a(n) = 2*A001353(n). - _R. J. Mathar_, Oct 26 2009
%F a(n) = ((3 - 2*sqrt(3))/3)*(2 - sqrt(3))^(n - 1) + ((3 + 2*sqrt(3))/3)*(2 + sqrt(3))^(n - 1). - _Vincenzo Librandi_, Nov 20 2010
%F a(n) = floor((2 + sqrt(3))^n/sqrt(3)). - _Zak Seidov_, Mar 31 2011
%F a(n) = ((2 + sqrt(3))^n - (2 - sqrt(3))^n)/sqrt(3). (See Horadam for construction.) - _Johannes Boot_, Jan 08 2012
%F a(n) = A217233(n) + A217233(n-1) with A217233(-1) = -1. - _Bruno Berselli_, Oct 01 2012
%F a(n) = A001835(n+1) - A001835(n). - _Kevin Long_, May 04 2018
%F E.g.f.: (exp((2 + sqrt(3))*x) - exp((2 - sqrt(3))*x))/sqrt(3). - _Franck Maminirina Ramaharo_, Nov 12 2018
%F a(n+1) = 2*a(n) + sqrt(3*a(n)^2 + 4), n > 1. - _Gary Detlefs_, Feb 27 2024
%e Colored compositions. a(2) = 8: There are two compositions of 4 into even parts, namely 4 and 2 + 2. Using primes to indicate the coloring of parts, the 8 colored compositions are 4, 4', 4'', 4''', 2 + 2, 2 + 2', 2' + 2 and 2' + 2'. - _Peter Bala_, Sep 17 2013
%p spec := [S,{S=Sequence(Prod(Union(Z,Z),Sequence(Z),Sequence(Z)))},unlabeled]: seq(combstruct[count](spec, size=n), n=0..20);
%p s := sqrt(3): a := n -> ((2-s)^n-(s+2)^n)/(s*(s-2)*(s+2)):
%p seq(simplify(a(n)), n=0..24); # _Peter Luschny_, Apr 28 2020
%t p=1; c=2; a[0]=0; a[1]=c; a[n_]:=a[n]=p*c^2*a[n-1]-a[n-2]; Table[a[n], {n, 0, 20}]
%t NestList[2 # + Sqrt[4 + 3 #^2]&, 0, 200] (* _Zak Seidov_, Mar 31 2011 *)
%t LinearRecurrence[{4, -1}, {0, 2}, 25] (* _T. D. Noe_, Jan 09 2012 *)
%t CoefficientList[Series[2x/(1-4x+x^2),{x,0,30}],x] (* _Harvey P. Dale_, May 31 2023 *)
%o (PARI) { polya002(p,c,m) = local(v,w,j,a); w=0; print1(w,", "); v=c; print1(v,", "); j=1; while(j<=m,a=p*c^2*v-w; print1(a,", "); w=v; v=a; j++) };
%o polya002(1,2,25)
%o (PARI) my(x='x+O('x^30)); concat([0], Vec(2*x/(1-4*x+x^2))) \\ _G. C. Greubel_, Feb 25 2019
%o (PARI) first(n) = n = max(n, 2); my(res = vector(n)); res[1] = 0; res[2] = 2; for(i = 3, n, res[i] = 4 * res[i-1] - res[i-2]); res \\ _David A. Corneth_, Apr 28 2020
%o (Haskell)
%o a052530 n = a052530_list !! n
%o a052530_list =
%o 0 : 2 : zipWith (-) (map (* 4) $ tail a052530_list) a052530_list
%o -- _Reinhard Zumkeller_, Sep 29 2011
%o (Magma) I:=[0,2]; [n le 2 select I[n] else 4*Self(n-1) - Self(n-2): n in [1..30]]; // _G. C. Greubel_, Feb 25 2019
%o (Sage) (2*x/(1-4*x+x^2)).series(x, 30).coefficients(x, sparse=False) # _G. C. Greubel_, Feb 25 2019
%Y Cf. A007913, A003699, A217233.
%Y Cf. A052529, A095263.
%K nonn,easy,nice
%O 0,2
%A encyclopedia(AT)pommard.inria.fr, Jan 25 2000
%E More terms from _James A. Sellers_, Jun 06 2000
%E Edited by _N. J. A. Sloane_, Nov 11 2006
%E a(0) changed to 0 and entry revised accordingly by _Max Alekseyev_, Nov 15 2007
%E Signs in definition corrected by _John W. Layman_, Nov 20 2007