OFFSET
0,2
COMMENTS
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
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
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
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
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
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
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
This sequence can be uniquely extended to satisfy the linear recurrence by a(n) = -a(-n) for all n in Z. - Michael Somos, Feb 22 2026
LINKS
T. D. Noe, Table of n, a(n) for n = 0..200
Norman Anning, Problem 3052, The American Mathematical Monthly, Vol. 31, No. 1 (1924), p. 49; Solution, by the proposer, ibid., Vol. 32, No. 7 (1925), p. 386.
Kasper K. Andersen, Lisa Carbone, and Diego Penta, Kac-Moody Fibonacci sequences, hyperbolic golden ratios, and real quadratic fields, Journal of Number Theory and Combinatorics, Vol 2, No. 3 (2011), pp. 245-278. See Section 9.
Hacène Belbachir, Soumeya Merwa Tebtoub, and László Németh, Ellipse Chains and Associated Sequences, J. Int. Seq., Vol. 23 (2020), Article 20.8.5.
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, (an + b)-color compositions, arXiv:1707.07798 [math.CO], 2017.
Niccolò Castronuovo, On the number of fixed points of the map gamma, arXiv:2102.02739 [math.NT], 2021-2023. Mentions this sequence.
Charles R. Dedrickson III, Compositions, Bijections, and Enumerations Thesis, 2012, Jack N. Averitt College of Graduate Studies, Georgia Southern University.
Jean-Pierre Ehrmann et al., Problem POLYA002, Integer pairs (x,y) for which (x^2+y^2)/(1+pxy) is an integer, 2001.
F. Göbel and A. A. Jagers, On a conjecture of Tutte concerning minimal tree numbers, J. Combin. Theory Ser. B 26 (1979), no. 3, 346-348. MR0535948 (80m:05064). [From N. J. A. Sloane, Feb 20 2012]
A. F. Horadam, Basic Properties of a Certain Generalized Sequence of Numbers, Fibonacci Quarterly, Vol. 3, No. 3 (1965), pp. 161-176.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 460.
N. J. A. Sloane, Transforms.
Glenn 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,-1).
FORMULA
G.f.: 2*x/(1 - 4*x + x^2).
Invert transform of even numbers: a(n) = 2*Sum_{k=1..n} k*a(n-k). - Vladeta Jovovic, Apr 27 2001
From Gregory V. Richardson, Oct 06 2002: (Start)
a(n) = Sum_{alpha} -(1/3)*(-1 + 2*alpha)*alpha^(-1 - n), alpha = root of (1 - 4*Z + Z^2).
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)
a(n) = A071954(n) - 2. - N. J. A. Sloane, Feb 20 2005
a(n) = (2*sinh(2n*arcsinh(1/sqrt(2))))/sqrt(3). - Herbert Kociemba, Apr 24 2008
a(n) = 2*A001353(n). - R. J. Mathar, Oct 26 2009
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
a(n) = floor((2 + sqrt(3))^n/sqrt(3)). - Zak Seidov, Mar 31 2011
a(n) = ((2 + sqrt(3))^n - (2 - sqrt(3))^n)/sqrt(3). (See Horadam for construction.) - Johannes Boot, Jan 08 2012
E.g.f.: (exp((2 + sqrt(3))*x) - exp((2 - sqrt(3))*x))/sqrt(3). - Franck Maminirina Ramaharo, Nov 12 2018
a(n+1) = 2*a(n) + sqrt(3*a(n)^2 + 4), n > 1. - Gary Detlefs, Feb 27 2024
Sum_{n>=1} arccot(a(n)^2) = Pi/12 (A019679) (Anning, 1924). - Amiram Eldar, Apr 07 2026
EXAMPLE
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
G.f. = 2*x + 8*x^2 + 30*x^3 + 112*x^4 + 418*x^5 + 1560*x^6 + ... - Michael Somos, Feb 22 2026
MAPLE
spec := [S, {S=Sequence(Prod(Union(Z, Z), Sequence(Z), Sequence(Z)))}, unlabeled]: seq(combstruct[count](spec, size=n), n=0..20);
# Alternative:
s := sqrt(3): a := n -> ((2-s)^n-(s+2)^n)/(s*(s-2)*(s+2)):
seq(simplify(a(n)), n=0..24); # Peter Luschny, Apr 28 2020
MATHEMATICA
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}]
(* Alternative: *)
NestList[2 # + Sqrt[4 + 3 #^2]&, 0, 26] (* Zak Seidov, Mar 31 2011 *)
(* Alternative: *)
LinearRecurrence[{4, -1}, {0, 2}, 25] (* T. D. Noe, Jan 09 2012 *)
(* Alternative: *)
CoefficientList[Series[2x/(1-4x+x^2), {x, 0, 30}], x] (* Harvey P. Dale, May 31 2023 *)
(* Alternative: *)
a[ n_] := ChebyshevU[n-1, 2]*2; (* Michael Somos, Feb 22 2026 *)
PROG
(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++) };
polya002(1, 2, 25)
(PARI) my(x='x+O('x^30)); concat([0], Vec(2*x/(1-4*x+x^2))) \\ G. C. Greubel, Feb 25 2019
(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
(PARI) {a(n) = polchebyshev(n-1, 2, 2)*2}; /* Michael Somos, Feb 22 2026 */
(Haskell)
a052530 n = a052530_list !! n
a052530_list =
0 : 2 : zipWith (-) (map (* 4) $ tail a052530_list) a052530_list
-- Reinhard Zumkeller, Sep 29 2011
(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
(SageMath) (2*x/(1-4*x+x^2)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Feb 25 2019
CROSSREFS
KEYWORD
nonn,easy,nice
AUTHOR
INRIA Encyclopedia of Combinatorial Structures, Jan 25 2000
EXTENSIONS
More terms from James Sellers, Jun 06 2000
Edited by N. J. A. Sloane, Nov 11 2006
a(0) changed to 0 and entry revised accordingly by Max Alekseyev, Nov 15 2007
Signs in definition corrected by John W. Layman, Nov 20 2007
STATUS
approved