A002530 -id:A002530 - cp's OEIS frontend

A001353 a(n) = 4*a(n-1) - a(n-2) with a(0) = 0, a(1) = 1.

0, 1, 4, 15, 56, 209, 780, 2911, 10864, 40545, 151316, 564719, 2107560, 7865521, 29354524, 109552575, 408855776, 1525870529, 5694626340, 21252634831, 79315912984, 296011017105, 1104728155436, 4122901604639, 15386878263120, 57424611447841, 214311567528244

Offset: 0

N. J. A. Sloane

3*a(n)^2 + 1 is a square. Moreover, 3*a(n)^2 + 1 = (2*a(n) - a(n-1))^2.
Consecutive terms give nonnegative solutions to x^2 - 4*x*y + y^2 = 1. - Max Alekseyev, Dec 12 2012
Values y solving the Pellian x^2 - 3*y^2 = 1; corresponding x values given by A001075(n). Moreover, we have a(n) = 2*a(n-1) + A001075(n-1). - Lekraj Beedassy, Jul 13 2006
Number of spanning trees in 2 X n grid: by examining what happens at the right-hand end we see that a(n) = 3*a(n-1) + 2*a(n-2) + 2*a(n-3) + ... + 2*a(1) + 1, where the final 1 corresponds to the tree ==...=| !. Solving this we get a(n) = 4*a(n-1) - a(n-2).
Complexity of 2 X n grid.
A016064 also describes triangles whose sides are consecutive integers and in which an inscribed circle has an integer radius. A001353 is exactly and precisely mapped to the integer radii of such inscribed circles, i.e., for each term of A016064, the corresponding term of A001353 gives the radius of the inscribed circle. - Harvey P. Dale, Dec 28 2000
n such that 3*n^2 = floor(sqrt(3)*n*ceiling(sqrt(3)*n)). - Benoit Cloitre, May 10 2003
For n>0, ratios a(n+1)/a(n) may be obtained as convergents of the continued fraction expansion of 2+sqrt(3): either as successive convergents of [4;-4] or as odd convergents of [3;1, 2]. - Lekraj Beedassy, Sep 19 2003
Ways of packing a 3 X (2*n-1) rectangle with dominoes, after attaching an extra square to the end of one of the sides of length 3. With reference to A001835, therefore: a(n) = a(n-1) + A001835(n-1) and A001835(n) = 3*A001835(n-1) + 2*a(n-1). - Joshua Zucker and the Castilleja School Math Club, Oct 28 2003
a(n+1) is a Chebyshev transform of 4^n, where the sequence with g.f. G(x) is sent to the sequence with g.f. (1/(1+x^2))G(x/(1+x^2)). - Paul Barry, Oct 25 2004
This sequence is prime-free, because a(2n) = a(n) * (a(n+1)-a(n-1)) and a(2n+1) = a(n+1)^2 - a(n)^2 = (a(n+1)+a(n)) * (a(n+1)-a(n)). - Jianing Song, Jul 06 2019
Numbers such that there is an m with t(n+m) = 3*t(m), where t(n) are the triangular numbers A000217. For instance, t(35) = 3*t(20) = 630, so 35 - 20 = 15 is in the sequence. - Floor van Lamoen, Oct 13 2005
a(n) = number of distinct matrix products in (A + B + C + D)^n where commutator [A,B] = 0 but neither A nor B commutes with C or D. - Paul D. Hanna and Max Alekseyev, Feb 01 2006
For n > 1, middle side (or long leg) of primitive Pythagorean triangles having an angle nearing Pi/3 with larger values of sides. [Complete triple (X, Y, Z), X < Y < Z, is given by X = A120892(n), Y = a(n), Z = A120893(n), with recurrence relations X(i+1) = 2*{X(i) - (-1)^i} + a(i); Z(i+1) = 2*{Z(i) + a(i)} - (-1)^i.] - Lekraj Beedassy, Jul 13 2006
From Dennis P. Walsh, Oct 04 2006: (Start)
Number of 2 X n simple rectangular mazes. A simple rectangular m X n maze is a graph G with vertex set {0, 1, ..., m} X {0, 1, ..., n} that satisfies the following two properties: (i) G consists of two orthogonal trees; (ii) one tree has a path that sequentially connects (0,0),(0,1), ..., (0,n), (1,n), ...,(m-1,n) and the other tree has a path that sequentially connects (1,0), (2,0), ..., (m,0), (m,1), ..., (m,n). For example, a(2) = 4 because there are four 2 X 2 simple rectangular mazes:
                                          
   |  |  |        |   |       |     |        |   |
   |   |        |   |       |  ||        |   |
(End)
[1, 4, 15, 56, 209, ...] is the Hankel transform of [1, 1, 5, 26, 139, 758, ...](see A005573). - Philippe Deléham, Apr 14 2007
The upper principal convergents to 3^(1/2), beginning with 2/1, 7/4, 26/15, 97/56, comprise a strictly decreasing sequence; numerators=A001075, denominators=A001353. - Clark Kimberling, Aug 27 2008
From Gary W. Adamson, Jun 21 2009: (Start)
A001353 and A001835 = bisection of continued fraction [1, 2, 1, 2, 1, 2, ...], i.e., of [1, 3, 4, 11, 15, 41, ...].
For n>0, a(n) equals the determinant of an (n-1) X (n-1) tridiagonal matrix with ones in the super and subdiagonals and (4, 4, 4, ...) as the main diagonal. [Corrected by Johannes Boot, Sep 04 2011]
A001835 and A001353 = right and next to right borders of triangle A125077. (End)
a(n) is equal to the permanent of the (n-1) X (n-1) Hessenberg matrix with 4's along the main diagonal, i's along the superdiagonal and the subdiagonal (i is the imaginary unit), and 0's everywhere else. - John M. Campbell, Jun 09 2011
2a(n) is the number of n-color compositions of 2n consisting of only even parts; see Guo in references. - Brian Hopkins, Jul 19 2011
Pisano period lengths: 1, 2, 6, 4, 3, 6, 8, 4, 18, 6, 10, 12, 12, 8, 6, 8, 18, 18, 5, 12, ... - R. J. Mathar, Aug 10 2012
From Michel Lagneau, Jul 08 2014: (Start)
a(n) is defined also by the recurrence a(1)=1; for n>1, a(n+1) = 2*a(n) + sqrt(3*a(n)^2 + 1) where a(n) is an integer for every n. This sequence is generalizable by the sequence b(n,m) of parameter m with the initial condition b(1,m) = 1, and for n > 1 b(n+1,m) = m*b(n,m) + sqrt((m^2 - 1)*b(n,m)^2 + 1) for m = 2, 3, 4, ... where b(n,m) is an integer for every n.
The first corresponding sequences are
   b(n,2)  = a(n) = A001353(n);
   b(n,3)  = A001109(n);
   b(n,4)  = A001090(n);
   b(n,5)  = A004189(n);
   b(n,6)  = A004191(n);
   b(n,7)  = A007655(n);
   b(n,8)  = A077412(n);
   b(n,9)  = A049660(n);
   b(n,10) = A075843(n);
   b(n,11) = A077421(n);
   ....................
We obtain a general sequence of polynomials {b(n,x)} = {1, 2*x, 4*x^2 - 1, 8*x^3 - 4*x, 16*x^4 - 12*x^2 + 1, 32*x^5 - 32*x^3 + 6*x, ...} with x = m where each b(n,x) is a Gegenbauer polynomial defined by the recurrence b(n,x)- 2*x*b(n-1,x) + b(n-2,x) = 0, the same relation as the Chebyshev recurrence, but with the initial conditions b(x,0) = 1 and b(x,1) = 2*x instead b(x,0) = 1 and b(x,1) = x for the Chebyshev polynomials. (End)
If a(n) denotes the n-th term of the above sequence and we construct a triangle whose sides are a(n) - 1, a(n) + 1 and sqrt(3a(n)^2 + 1), then, for every n the measure of one of the angles of the triangle so constructed will always be 120 degrees. This result of ours was published in Mathematics Spectrum (2012/2013), Vol. 45, No. 3, pp. 126-128. - K. S. Bhanu and Dr. M. N. Deshpande, Professor (Retd), Department of Statistics, Institute of Science, Nagpur (India).
For n >= 1, a(n) equals the number of 01-avoiding words of length n - 1 on alphabet {0, 1, 2, 3}. - Milan Janjic, Jan 25 2015
For n > 0, 10*a(n) is the number of vertices and roots on level n of the {4, 5} mosaic (see L. Németh Table 1 p. 6). - Michel Marcus, Oct 30 2015
(2 + sqrt(3))^n = A001075(n) + a(n)*sqrt(3), n >= 0; integers in the quadratic number field Q(sqrt(3)). - Wolfdieter Lang, Feb 16 2018
A strong divisibility sequence, that is, gcd(a(n), a(m)) = a(gcd(n, m)) for all positive integers n and m. - Michael Somos, Dec 12 2019
The Cholesky decomposition A = C C* for tridiagonal A with A[i,i] = 4 and A[i+1,i] = A[i,i+1] = -1, as it arises in the discretized 2D Laplace operator (Poisson equation...), has nonzero elements C[i,i] = sqrt(a(i+1)/a(i)) = -1/C[i+1,i], i = 1, 2, 3, ... - M. F. Hasler, Mar 12 2021
The triples (a(n-1), 2a(n), a(n+1)), n=2,3,..., are exactly the triples (a,b,c) of positive integers a < b < c in arithmetic progression such that a*b+1, b*c+1, and c*a+1 are perfect squares. - Bernd Mulansky, Jul 10 2021
From Greg Dresden and Linyun Sheng, Jul 01 2025: (Start)
  a(n) is the number of ways to tile this strip of length n,
  .________________
  |  |  |  |  |  |  |\
  ||__||__||__|_\,
  where the last cell is a right triangle, with three types of tiles: 1 X 1 squares, 1 X 1 small right triangles, and large right triangles (with large side length 2) formed by joining two of those small right triangles along a short leg. As an example, here is one of the a(7)=2911 ways to tile the 1 X 7 strip with these kinds of tiles:
  .________________
  |\   /|\ | /|  | / \
  |\/_|\|/|__|/_\,
(End)

			For example, when n = 3:
  ****
  .***
  .***
can be packed with dominoes in 4 different ways: 3 in which the top row is tiled with two horizontal dominoes and 1 in which the top row has two vertical and one horizontal domino, as shown below, so a(2) = 4.
  ---- ---- ---- ||--
  .||| .--| .|-- .|||
  .||| .--| .|-- .|||
G.f. = x + 4*x^2 + 15*x^3 + 56*x^4 + 209*x^5 + 780*x^6 + 2911*x^7 + 10864*x^8 + ...

Bastida, Julio R., Quadratic properties of a linearly recurrent sequence. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 163-166, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561042 (81e:10009)
G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; p. 163.
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 329.
J. D. E. Konhauser et al., Which Way Did the Bicycle Go?, MAA 1996, p. 104.
Serge Lang, Introduction to Diophantine Approximations, Addison-Wesley, New York, 1966.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..200
Marco Abrate, Stefano Barbero, Umberto Cerruti, and Nadir Murru, Polynomial sequences on quadratic curves, Integers, Vol. 15, 2015, #A38.
Christian Aebi and Grant Cairns, Lattice Equable Parallelograms, arXiv:2006.07566 [math.NT], 2020.
Christian Aebi and Grant Cairns, Equable Parallelograms on the Eisenstein Lattice, arXiv:2401.08827 [math.CO], 2024. See p. 14.
W. K. Alt, Enumeration of Domino Tilings on the Projective Grid Graph, A Thesis Presented to The Division of Mathematics and Natural Sciences, Reed College, May 2013.
K. Andersen, L. Carbone, and D. Penta, Kac-Moody Fibonacci sequences, hyperbolic golden ratios, and real quadratic fields, Journal of Number Theory and Combinatorics, Vol 2, No. 3 pp 245-278, 2011. See Section 9.
Francesca Arici and Jens Kaad, Gysin sequences and SU(2)-symmetries of C*-algebras, arXiv:2012.11186 [math.OA], 2020.
Krassimir T. Atanassov and Anthony G. Shannon, On intercalated Fibonacci sequences, Notes on Number Theory and Discrete Mathematics (2020) Vol. 26, No. 3, 218-223.
J. Austin and L. Schneider, Generalized Fibonacci sequences in Pythagorean triple preserving sequences, Fib. Q., 58:4 (2020), 340-350.
Paul Barry, Notes on Riordan arrays and lattice paths, arXiv:2504.09719 [math.CO], 2025. See pp. 15, 29.
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, Linear recurrence sequences with indices in arithmetic progression and their sums, arXiv preprint arXiv:1505.06339 [math.NT], 2015.
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, example 12.
K. S. Bhanu and M. N. Deshpande, Integral triangles with 120° angle Mathematics Spectrum, 45 (3) (2012/2013), 126-128.
Latham Boyle and Paul J. Steinhardt, Self-Similar One-Dimensional Quasilattices, arXiv preprint arXiv:1608.08220 [math-ph], 2016.
Yurii S. Bystryk, Vitalii L. Denysenko, and Volodymyr I. Ostryk, Lune and Lens Sequences, ResearchGate preprint, 2024. See pp. 48, 56.
Fabrizio Canfora, Maxim Kurkov, Luigi Rosa, and Patrizia Vitale, The Gribov problem in Noncommutative QED, arXiv preprint arXiv:1505.06342 [hep-th], 2015.
Niccolò Castronuovo, On the number of fixed points of the map gamma, arXiv:2102.02739 [math.NT], 2021. Mentions this sequence.
Z. Cinkir, Effective Resistances, Kirchhoff index and Admissible Invariants of Ladder Graphs, arXiv preprint arXiv:1503.06353 [math.CO], 2015.
J. B. Cosgrave and K. Dilcher, A role for generalized Fermat numbers, Math. Comp. 86 (2017), 899-933 (see also paper #10).
M. N. Deshpande, One Interesting Family of Diophantine Triplets, International Journal of Mathematical Education In Science and Technology, Vol. 33 (No. 2, Mar-Apr), 2002.
M. N. Deshpande, Hansruedi Widmer and Zachary Franco, Simultaneous Squares from Arithmetic Progressions: 10622, The American Mathematical Monthly Vol. 106, No. 9 (Nov., 1999), 867-868.
Tomislav Doslic, Planar polycyclic graphs and their Tutte polynomials, Journal of Mathematical Chemistry, Volume 51, Issue 6, 2013, pp. 1599-1607.
G. Dresden and Y. Li, Periodic Weighted Sums of Binomial Coefficients, arXiv:2210.04322 [math.NT], 2022.
E. I. Emerson, Recurrent Sequences in the Equation DQ^2=R^2+N, Fib. Quart., 7 (1969), pp. 231-242.
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
Felix Flicker, Time quasilattices in dissipative dynamical systems, arXiv:1707.09371 [nlin.CD], 2017. Also SciPost Phys. 5, 001 (2018).
D. Fortin, B-spline Toeplitz Inverse Under Corner Perturbations, International Journal of Pure and Applied Mathematics, Volume 77, No. 1, 2012, 107-118. - From _N. J. A. Sloane_, Oct 22 2012
Dale Gerdemann, Fractal images from (4, -1) recursion, YouTube, Oct 27 2014.
Juan B. Gil and Jessica A. Tomasko, Fibonacci colored compositions and applications, arXiv:2108.06462 [math.CO], 2021.
Andrew Granville and Zhi-Wei Sun, Values of Bernoulli polynomials, Pacific J. Math. 172 (1996), 117-137, at p. 119.
T. N. E. Greville, Table for third-degree spline interpolations with equally spaced arguments, Math. Comp., 24 (1970), 179-183.
Y.-H. Guo, n-Colour even self-inverse compositions, Proc. Indian Acad. Sci. (Math. Sci.), 120 (2010), 27-33.
B. Hopkins, Spotted tilings and n-color compositions, INTEGERS 12B (2012/2013), #A6.
A. F. Horadam, Special properties of the sequence W_n(a,b; p,q), Fib. Quart., 5.5 (1967), 424-434. Case a=0,b=1; p=4, q=-1.
W. D. Hoskins, Table for third-degree spline interpolation using equi-spaced knots, Math. Comp., 25 (1971), 797-801.
Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
Tanya Khovanova, Recursive Sequences
Seong Ju Kim, R. Stees, and L. Taalman, Sequences of Spiral Knot Determinants, Journal of Integer Sequences, Vol. 19 (2016), #16.1.4
Clark Kimberling, Best lower and upper approximates to irrational numbers, Elemente der Mathematik, 52 (1997) 122-126.
Germain Kreweras, Complexite et circuits Euleriens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212.
Pablo Lam-Estrada, Myriam Rosalía Maldonado-Ramírez, José Luis López-Bonilla, Fausto Jarquín-Zárate, The sequences of Fibonacci and Lucas for each real quadratic fields Q(Sqrt(d)), arXiv:1904.13002 [math.NT], 2019.
Wolfdieter Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38,5 (2000) 408-419; Eq.(44), lhs, m=6.
Ioana-Claudia Lazăr, Lucas sequences in t-uniform simplicial complexes, arXiv:1904.06555 [math.GR], 2019.
Hojoo Lee, Problems in elementary number theory Problem I 18.
E. Keith Lloyd, The Standard Deviation of 1, 2,..., n: Pell's Equation and Rational Triangles, Math. Gaz. vol 81 (1997), 231-243.
Dino Lorenzini and Z. Xiang, Integral points on variable separated curves, Preprint 2016.
Valcho Milchev and Tsvetelina Karamfilova, Domino tiling in grid - new dependence, arXiv:1707.09741 [math.HO], 2017.
László Németh, Trees on hyperbolic honeycombs, arXiv:1510.08311 [math.CO], 2015.
Hideyuki Ohtskua, proposer, Problem B-1351, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 62, No. 3 (2024), p. 258.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Ariel D. Procaccia and Jamie Tucker-Foltz, Compact Redistricting Plans Have Many Spanning Trees, Harvard Univ. (2021).
P. Raff, Analysis of the Number of Spanning Trees of K_2 x P_n. Contains sequence, recurrence, generating function, and more. [From _Paul Raff_, Mar 06 2009]
Franck Ramaharo, The bracket polynomial of the Celtic link shadow CK_4^(2n), arXiv:2508.10410 [math.GT], 2025. See p. 6.
Ryan Stees, Sequences of Spiral Knot Determinants, Senior Honors Projects, Paper 84, James Madison Univ., May 2016.
D. P. Walsh, Counting n x 2 Simple Rectangular Mazes
F. V. Waugh and M. W. Maxfield, Side-and-diagonal numbers, Math. Mag., 40 (1967), 74-83.
Eric Weisstein's World of Mathematics, Ladder Graph
Eric Weisstein's World of Mathematics, Spanning Tree
Jianqiang Zhao, Finite Multiple zeta Values and Finite Euler Sums, arXiv preprint arXiv:1507.04917 [math.NT], 2015.
Index entries for linear recurrences with constant coefficients, signature (4,-1)
Index entries for sequences related to Chebyshev polynomials.

Cf. A001075, A001542, A001571, A001834, A001835, A002531, A003500, A005246, A016064, A019679, A079935, A082840.
A bisection of A002530.
Cf. A125077.
A row of A116469.
Chebyshev sequence U(n, m): A000027 (m=1), this sequence (m=2), A001109 (m=3), A001090 (m=4), A004189 (m=5), A004191 (m=6), A007655 (m=7), A077412 (m=8), A049660 (m=9), A075843 (m=10), A077421 (m=11), A077423 (m=12), A097309 (m=13), A097311 (m=14), A097313 (m=15), A029548 (m=16), A029547 (m=17), A144128 (m=18), A078987 (m=19), A097316 (m=33).
Cf. A323182.

a:=[0,1];; for n in [3..30] do a[n]:=4*a[n-1]-a[n-2]; od; a; # Muniru A Asiru, Feb 16 2018

a001353 n = a001353_list !! n
a001353_list =
   0 : 1 : zipWith (-) (map (4 *) $ tail a001353_list) a001353_list
-- Reinhard Zumkeller, Aug 14 2011

I:=[0,1]; [n le 2 select I[n] else 4*Self(n-1)-Self(n-2): n in [1..30]]; // G. C. Greubel, Jun 06 2019

A001353 := proc(n) option remember; if n <= 1 then n else 4*A001353(n-1)-A001353(n-2); fi; end;
A001353:=z/(1-4*z+z**2); # Simon Plouffe in his 1992 dissertation.
seq( simplify(ChebyshevU(n-1, 2)), n=0..20); # G. C. Greubel, Dec 23 2019

a[n_] := (MatrixPower[{{1, 2}, {1, 3}}, n].{{1}, {1}})[[2, 1]]; Table[ a[n], {n, 0, 30}] (* Robert G. Wilson v, Jan 13 2005 *)
Table[GegenbauerC[n-1, 1, 2], {n, 0, 30}] (* Zerinvary Lajos, Jul 14 2009 *)
Table[-((I Sin[n ArcCos[2]])/Sqrt[3]), {n, 0, 30}] // FunctionExpand (* Eric W. Weisstein, Jul 16 2011 *)
Table[Sinh[n ArcCosh[2]]/Sqrt[3], {n, 0, 30}] // FunctionExpand (* Eric W. Weisstein, Jul 16 2011 *)
Table[ChebyshevU[n-1, 2], {n, 0, 30}] (* Eric W. Weisstein, Jul 16 2011 *)
a[0]:=0; a[1]:=1; a[n_]:= a[n]= 4a[n-1] - a[n-2]; Table[a[n], {n, 0, 30}] (* Alonso del Arte, Jul 19 2011 *)
LinearRecurrence[{4, -1}, {0, 1}, 30] (* Sture Sjöstedt, Dec 06 2011 *)
Round@Table[Fibonacci[2n, Sqrt[2]]/Sqrt[2], {n, 0, 30}] (* Vladimir Reshetnikov, Sep 15 2016 *)

M = [ 1, 1, 0; 1, 3, 1; 0, 1, 1]; for(i=0,30,print1(([1,0,0]*M^i)[2],",")) \\ Lambert Klasen (Lambert.Klasen(AT)gmx.net), Jan 25 2005

{a(n) = real( (2 + quadgen(12))^n / quadgen(12) )}; /* Michael Somos, Sep 19 2008 */

{a(n) = polchebyshev(n-1, 2, 2)}; /* Michael Somos, Sep 19 2008 */

concat(0, Vec(x/(1-4*x+x^2) + O(x^30))) \\ Altug Alkan, Oct 30 2015

a001353 = [0, 1]
for n in range(30): a001353.append(4*a001353[-1] - a001353[-2])
print(a001353)  # Gennady Eremin, Feb 05 2022

[lucas_number1(n,4,1) for n in range(30)] # Zerinvary Lajos, Apr 22 2009

[chebyshev_U(n-1,2) for n in (0..20)] # G. C. Greubel, Dec 23 2019

G.f.: x/(1-4*x+x^2).
a(n) = ((2 + sqrt(3))^n - (2 - sqrt(3))^n)/(2*sqrt(3)).
a(n) = sqrt((A001075(n)^2 - 1)/3).
a(n) = 2*a(n-1) + sqrt(3*a(n-1)^2 + 1). - Lekraj Beedassy, Feb 18 2002
Limit_{n->oo} a(n)/a(n-1) = 2 + sqrt(3). - Gregory V. Richardson, Oct 06 2002
Binomial transform of A002605.
E.g.f.: exp(2*x)*sinh(sqrt(3)*x)/sqrt(3).
a(n) = S(n-1, 4) = U(n-1, 2); S(-1, x) := 0, Chebyshev's polynomials of the second kind A049310.
a(n+1) = Sum_{k=0..floor(n/2)} binomial(n-k, k)(-1)^k*4^(n - 2*k). - Paul Barry, Oct 25 2004
a(n) = Sum_{k=0..n-1} binomial(n+k,2*k+1)*2^k. - Paul Barry, Nov 30 2004
a(n) = 3*a(n-1) + 3*a(n-2) - a(n-3), n>=3. - Lekraj Beedassy, Jul 13 2006
a(n) = -A106707(n). - R. J. Mathar, Jul 07 2006
M^n * [1,0] = [A001075(n), A001353(n)], where M = the 2 X 2 matrix [2,3; 1,2]; e.g., a(4) = 56 since M^4 * [1,0] = [97, 56] = [A001075(4), A001353(4)]. - Gary W. Adamson, Dec 27 2006
From Michael Somos, Sep 19 2008: (Start)
Sequence satisfies 1 = f(a(n), a(n+1)) where f(u, v) = u^2 + v^2 - 4*u*v.
a(n) = -a(-n) for all integer n. (End)
Rational recurrence: a(n) = (17*a(n-1)*a(n-2) - 4*(a(n-1)^2 + a(n-2)^2))/a(n-3) for n > 3. - Jaume Oliver Lafont, Dec 05 2009
If p[i] = Fibonacci(2i) and if A is the Hessenberg matrix of order n defined by A[i,j] = p[j-i+1], (i <= j), A[i,j] = -1, (i = j + 1), and A[i,j] = 0 otherwise, then, for n >= 1, a(n) = det A. - Milan Janjic, May 08 2010
From Eric W. Weisstein, Jul 16 2011: (Start)
a(n) = C_{n-1}^{(1)}(2), where C_n^{(m)}(x) is the Gegenbauer polynomial.
a(n) = -i*sin(n*arccos(2))/sqrt(3).
a(n) = sinh(n*arccosh(2))/sqrt(3). (End)
a(n) = b such that Integral_{x=0..Pi/2} (sin(n*x))/(2-cos(x)) dx = c + b*log(2). - Francesco Daddi, Aug 02 2011
a(n) = sqrt(A098301(n)) = sqrt([A055793 / 3]), base 3 analog of A031150. - M. F. Hasler, Jan 16 2012
a(n+1) = Sum_{k=0..n} A101950(n,k)*3^k. - Philippe Deléham, Feb 10 2012
1, 4, 15, 56, 209, ... = INVERT(INVERT(1, 2, 3, 4, 5, ...)). - David Callan, Oct 13 2012
From Peter Bala, Dec 23 2012: (Start)
Product_{n >= 1} (1 + 1/a(n)) = 1 + sqrt(3).
Product_{n >= 2} (1 - 1/a(n)) = 1/4*(1 + sqrt(3)). (End)
a(n+1) = (A001834(n) + A001835(n))/2. a(n+1) + a(n) = A001834(n). a(n+1) - a(n) = A001835(n). - Richard R. Forberg, Sep 04 2013
a(n) = -(-i)^(n+1)*Fibonacci(n, 4*i), i = sqrt(-1). - G. C. Greubel, Jun 06 2019
a(n)^2 - a(m)^2 = a(n+m) * a(n-m), a(n+2)*a(n-2) = 16*a(n+1)*a(n-1) - 15*a(n)^2, a(n+3)*a(n-2) = 15*a(n+2)*a(n-1) - 14*a(n+1)*a(n) for all integer n, m. - Michael Somos, Dec 12 2019
a(n) = 2^n*Sum_{k >= n} binomial(2*k,2*n-1)*(1/3)^(k+1). Cf. A102591. - Peter Bala, Nov 29 2021
a(n) = Sum_{k > 0} (-1)^((k-1)/2)*binomial(2*n, n+k)*(k|12), where (k|12) is the Kronecker symbol. - Greg Dresden, Oct 11 2022
Sum_{k=0..n} a(k) = (a(n+1) - a(n) - 1)/2. - Prabha Sivaramannair, Sep 22 2023
a(2n+1) = A001835(n+1) * A001834(n). - M. Farrokhi D. G., Oct 15 2023
Sum_{n>=1} arctan(1/(4*a(n)^2)) = Pi/12 (A019679) (Ohtskua, 2024). - Amiram Eldar, Aug 29 2024
From Peter Bala, May 21 2025: (Start)
Product_{n >= 1} (1 + 1/a(n))^2 = 2*(2 + sqrt(3)) (telescoping product: (1 + 1/a(2*n-1))^2 * (1 + 1/a(2*n-2))^2 = (4 + 2*A251963(n)/A005246(2*n)^2)/(4 + 2*A251963(n-1)/A005246(2*n-2)^2) ).
Product_{n >= 2} (1 - 1/a(n))^2 = (1/8)*(2 + sqrt(3)).
Product_{n >= 1} ((a(2*n) + 1)/(a(2*n) - 1))^2 = 3 (telescoping product: ((a(2*n) + 1)/(a(2*n) - 1))^2 = (3 - 2/A001835(n+1)^2)/(3 - 2/A001835(n)^2) ).
Product_{n >= 2} ((a(2*n-1) + 1)/(a(2*n-1) - 1))^2 = 4/3.
The o.g.f. A(x) satisfies A(x) + A(-x) + 8*A(x)*A(-x) = 0. The o.g.f. for A007655 equals -A(sqrt(x))*A(-sqrt(x)). (End)

A002605 a(n) = 2*(a(n-1) + a(n-2)), a(0) = 0, a(1) = 1.

Original entry on oeis.org

0, 1, 2, 6, 16, 44, 120, 328, 896, 2448, 6688, 18272, 49920, 136384, 372608, 1017984, 2781184, 7598336, 20759040, 56714752, 154947584, 423324672, 1156544512, 3159738368, 8632565760, 23584608256, 64434348032, 176037912576, 480944521216, 1313964867584

Offset: 0

Colin Mallows

Individually, both this sequence and A028859 are convergents to 1 + sqrt(3). Mutually, both sequences are convergents to 2 + sqrt(3) and 1 + sqrt(3)/2. - Klaus E. Kastberg (kastberg(AT)hotkey.net.au), Nov 04 2001
The number of (s(0), s(1), ..., s(n+1)) such that 0 < s(i) < 6 and |s(i) - s(i-1)| <= 1 for i = 1, 2, ..., n + 1, s(0) = 2, s(n+1) = 3. - Herbert Kociemba, Jun 02 2004
The same sequence may be obtained by the following process. Starting a priori with the fraction 1/1, the denominators of fractions built according to the rule: add top and bottom to get the new bottom, add top and 4 times the bottom to get the new top. The limit of the sequence of fractions is sqrt(4). - Cino Hilliard, Sep 25 2005
The Hankel transform of this sequence is [1, 2, 0, 0, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Nov 21 2007
[1, 3; 1, 1]^n *[1, 0] = [A026150(n), a(n)]. - Gary W. Adamson, Mar 21 2008
(1 + sqrt(3))^n = A026150(n) + a(n)*sqrt(3). - Gary W. Adamson, Mar 21 2008
a(n+1) is the number of ways to tile a board of length n using red and blue tiles of length one and two. - Geoffrey Critzer, Feb 07 2009
Starting with offset 1 = INVERT transform of the Jacobsthal sequence, A001045: (1, 1, 3, 5, 11, 21, ...). - Gary W. Adamson, May 12 2009
Starting with "1" = INVERTi transform of A007482: (1, 3, 11, 39, 139, ...). - Gary W. Adamson, Aug 06 2010
An elephant sequence, see A175654. For the corner squares four A[5] vectors, with decimal values 85, 277, 337 and 340, lead to this sequence (without the leading 0). For the central square these vectors lead to the companion sequence A026150, without the first leading 1. - Johannes W. Meijer, Aug 15 2010
The sequence 0, 1, -2, 6, -16, 44, -120, 328, -896, ... (with alternating signs) is the Lucas U(-2,-2)-sequence. - R. J. Mathar, Jan 08 2013
a(n+1) counts n-walks (closed) on the graph G(1-vertex;1-loop,1-loop,2-loop,2-loop). - David Neil McGrath, Dec 11 2014
Number of binary strings of length 2*n - 2 in the regular language (00+11+0101+1010)*. - Jeffrey Shallit, Dec 14 2015
For n >= 1, a(n) equals the number of words of length n - 1  over {0, 1, 2, 3} in which 0 and 1 avoid runs of odd lengths. - Milan Janjic, Dec 17 2015
a(n+1) is the number of compositions of n into parts 1 and 2, both of two kinds. - Gregory L. Simay, Sep 20 2017
Number of associative, quasitrivial, and order-preserving binary operations on the n-element set {1, ..., n} that have neutral elements. - J. Devillet, Sep 28 2017
(1 + sqrt(3))^n = A026150(n) + a(n)*sqrt(3), for n >= 0; integers in the real quadratic number field Q(sqrt(3)). - Wolfdieter Lang, Feb 10 2018
Starting with 1, 2, 6, 16, ..., number of permutations of length n>0 avoiding the partially ordered pattern (POP) {1>3, 1>4} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the third and fourth elements. - Sergey Kitaev, Dec 09 2020
a(n) is the number of tilings of a 2 X n board missing one corner cell, with 1 X 1 and L-shaped tiles (where the L-shaped tiles cover 3 squares). Compare to A127864. - Greg Dresden and Yilin Zhu, Jul 17 2025

John Derbyshire, Prime Obsession, Joseph Henry Press, April 2004, p. 16.

Vincenzo Librandi, Table of n, a(n) for n = 0..500
A. Abdurrahman, CM Method and Expansion of Numbers, arXiv:1909.10889 [math.NT], 2019.
Jean-Luc Baril, Nathanaël Hassler, Sergey Kirgizov, and José L. Ramírez, Grand zigzag knight's paths, arXiv:2402.04851 [math.CO], 2024.
Paul Barry, On the Gap-sum and Gap-product Sequences of Integer Sequences, arXiv:2104.05593 [math.CO], 2021.
Paul Barry, Notes on Riordan arrays and lattice paths, arXiv:2504.09719 [math.CO], 2025. See pp. 8, 29.
Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
M. Couceiro, J. Devillet, and J.-L. Marichal, Quasitrivial semigroups: characterizations and enumerations, arXiv:1709.09162 [math.RA], 2017.
M. Diepenbroek, M. Maus, and A. Stoll, Pattern Avoidance in Reverse Double Lists, Preprint 2015. See Table 3.
Sergio Falcón, Binomial Transform of the Generalized k-Fibonacci Numbers, Communications in Mathematics and Applications (2019) Vol. 10, No. 3, 643-651.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
Dale Gerdemann Bird Flock, Youtube video, 2011.
A. F. Horadam, Special properties of the sequence W_n(a,b; p,q), Fib. Quart., 5.5 (1967), 424-434. Case n->n+1, a=0,b=1; p=q=2.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 476
D. Jhala, G. P. S. Rathore, and K. Sisodiya, Some Properties of k-Jacobsthal Numbers with Arithmetic Indexes, Turkish Journal of Analysis and Number Theory, 2014, Vol. 2, No. 4, 119-124.
Tanya Khovanova, Recursive Sequences
Wolfdieter Lang, On polynomials related to powers of the generating function of Catalan's numbers, Fib. Quart. 38,5 (2000) 408-419; Eqs. (39), (41) and (45), lhs, m=2.
D. H. Lehmer, On Lucas's test for the primality of Mersenne's numbers, Journal of the London Mathematical Society 1.3 (1935): 162-165. See U_n.
Toufik Mansour and Mark Shattuck, Pattern avoidance in flattened derangements, Disc. Math. Lett. (2025) Vol. 15, 67-74. See p. 74.
Yassine Otmani, The 2-Pascal Triangle and a Related Riordan Array, J. Int. Seq. (2025) Vol. 28, Issue 3, Art. No. 25.3.5. See p. 12.
Alan Prince, Counting parses, Rutgers Optimality Archive, 2010.
Index entries for linear recurrences with constant coefficients, signature (2,2).
Index entries for sequences related to Chebyshev polynomials.
Index entries for Lucas sequences.

First differences are given by A026150.
a(n) = A073387(n, 0), n>=0 (first column of triangle).
Equals (1/3) A083337. First differences of A077846. Pairwise sums of A028860 and abs(A077917).
a(n) = A028860(n)/2 apart from the initial terms.
Row sums of A081577 and row sums of triangle A156710.
The following sequences (and others) belong to the same family: A001333, A000129, A026150, A046717, A015518, A084057, A063727, A002533, A002532, A083098, A083099, A083100, A015519.
Cf. A080953, A052948, A080040, A028859, A030195, A106435, A108898, A125145, A265106, A265107, A265278, A270810, A293005, A293006, A293007.
Cf. A175289 (Pisano periods).
Cf. A002530.
Cf. A127864.

a002605 n = a002605_list !! n
a002605_list =
   0 : 1 : map (* 2) (zipWith (+) a002605_list (tail a002605_list))
-- Reinhard Zumkeller, Oct 15 2011

[Floor(((1 + Sqrt(3))^n - (1 - Sqrt(3))^n)/(2*Sqrt(3))): n in [0..30]]; // Vincenzo Librandi, Aug 18 2011

[n le 2 select n-1 else 2*Self(n-1) + 2*Self(n-2): n in [1..30]]; // G. C. Greubel, Jan 07 2018

a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=2*a[n-1]+2*a[n-2]od: seq(a[n], n=0..33); # Zerinvary Lajos, Dec 15 2008
a := n -> `if`(n<3, n, 2^(n-1)*hypergeom([1-n/2, (1-n)/2], [1-n], -2));
seq(simplify(a(n)), n=0..29); # Peter Luschny, Dec 16 2015

Expand[Table[((1 + Sqrt[3])^n - (1 - Sqrt[3])^n)/(2Sqrt[3]), {n, 0, 30}]] (* Artur Jasinski, Dec 10 2006 *)
a[n_]:=(MatrixPower[{{1,3},{1,1}},n].{{1},{1}})[[2,1]]; Table[a[n],{n,-1,40}] (* Vladimir Joseph Stephan Orlovsky, Feb 19 2010 *)
LinearRecurrence[{2, 2}, {0, 1}, 30] (* Robert G. Wilson v, Apr 13 2013 *)
Round@Table[Fibonacci[n, Sqrt[2]] 2^((n - 1)/2), {n, 0, 20}] (* Vladimir Reshetnikov, Oct 15 2016 *)
nxt[{a_,b_}]:={b,2(a+b)}; NestList[nxt,{0,1},30][[All,1]] (* Harvey P. Dale, Sep 17 2022 *)

Vec(x/(1-2*x-2*x^2)+O(x^99)) \\ Charles R Greathouse IV, Jun 10 2011

A002605(n)=([2,2;1,0]^n)[2,1] \\ M. F. Hasler, Aug 06 2018

[lucas_number1(n,2,-2) for n in range(0, 30)] # Zerinvary Lajos, Apr 22 2009

a = BinaryRecurrenceSequence(2,2)
print([a(n) for n in (0..29)])  # Peter Luschny, Aug 29 2016

a(n) = (-I*sqrt(2))^(n-1)*U(n-1, I/sqrt(2)) where U(n, x) is the Chebyshev U-polynomial. - Wolfdieter Lang
G.f.: x/(1 - 2*x - 2*x^2).
From Paul Barry, Sep 17 2003: (Start)
E.g.f.: x*exp(x)*(sinh(sqrt(3)*x)/sqrt(3) + cosh(sqrt(3)*x)).
a(n) = (1 + sqrt(3))^(n-1)*(1/2 + sqrt(3)/6) + (1 - sqrt(3))^(n-1)*(1/2 - sqrt(3)/6), for n>0.
Binomial transform of 1, 1, 3, 3, 9, 9, ... Binomial transform is A079935. (End)
a(n) = Sum_{k=0..floor(n/2)} binomial(n - k, k)*2^(n - k). - Paul Barry, Jul 13 2004
a(n) = A080040(n) - A028860(n+1). - Creighton Dement, Jan 19 2005
a(n) = Sum_{k=0..n} A112899(n,k). - Philippe Deléham, Nov 21 2007
a(n) = Sum_{k=0..n} A063967(n,k). - Philippe Deléham, Nov 03 2006
a(n) = ((1 + sqrt(3))^n - (1 - sqrt(3))^n)/(2*sqrt(3)).
a(n) = Sum_{k=0..n} binomial(n, 2*k + 1) * 3^k.
Binomial transform of expansion of sinh(sqrt(3)x)/sqrt(3) (0, 1, 0, 3, 0, 9, ...). E.g.f.: exp(x)*sinh(sqrt(3)*x)/sqrt(3). - Paul Barry, May 09 2003
a(n) = (1/3)*Sum_{k=1..5} sin(Pi*k/2)*sin(2*Pi*k/3)*(1 + 2*cos(Pi*k/6))^n, n >= 1. - Herbert Kociemba, Jun 02 2004
a(n+1) = ((3 + sqrt(3))*(1 + sqrt(3))^n + (3 - sqrt(3))*(1 - sqrt(3))^n)/6. - Al Hakanson (hawkuu(AT)gmail.com), Jun 29 2009
Antidiagonals sums of A081577. - J. M. Bergot, Dec 15 2012
G.f.: Q(0)*x/2, where Q(k) = 1 + 1/(1 - x*(4*k + 2 + 2*x)/(x*(4*k + 4 + 2*x) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 30 2013
a(n) = 2^(n - 1)*hypergeom([1 - n/2, (1 - n)/2], [1 - n], -2) for n >= 3. - Peter Luschny, Dec 16 2015
Sum_{k=0..n} a(k)*2^(n-k) = a(n+2)/2 - 2^n. - Greg Dresden, Feb 11 2022
a(n) = 2^floor(n/2) * A002530(n). - Gregory L. Simay, Sep 22 2022
From Peter Bala, May 08 2024: (Start)
G.f.: x/(1 - 2*x - 2*x^2) = Sum_{n >= 0} x^(n+1) *( Product_{k = 1..n} (k + 2*x + 1)/(1 + k*x) )
Also x/(1 - 2*x - 2*x^2) = Sum_{n >= 0} (2*x)^n *( x*Product_{k = 1..n} (m*k + 2 - m + x)/(1 + 2*m*k*x) ) for arbitrary m (both series are telescoping). (End)
a(n) = A127864(n-1) + A127864(n-2). - Greg Dresden and Yilin Zhu, Jul 17 2025

Edited by N. J. A. Sloane, Apr 15 2009

A001835 a(n) = 4*a(n-1) - a(n-2), with a(0) = 1, a(1) = 1.

Original entry on oeis.org

1, 1, 3, 11, 41, 153, 571, 2131, 7953, 29681, 110771, 413403, 1542841, 5757961, 21489003, 80198051, 299303201, 1117014753, 4168755811, 15558008491, 58063278153, 216695104121, 808717138331, 3018173449203, 11263976658481, 42037733184721, 156886956080403, 585510091136891

Offset: 0

N. J. A. Sloane

See A079935 for another version.
Number of ways of packing a 3 X 2*(n-1) rectangle with dominoes. - David Singmaster.
Equivalently, number of perfect matchings of the P_3 X P_{2(n-1)} lattice graph. - Emeric Deutsch, Dec 28 2004
The terms of this sequence are the positive square roots of the indices of the octagonal numbers (A046184) - Nicholas S. Horne (nairon(AT)loa.com), Dec 13 1999
Terms are the solutions to: 3*x^2 - 2 is a square. - Benoit Cloitre, Apr 07 2002
Gives solutions x > 0 of the equation floor(x*r*floor(x/r)) == floor(x/r*floor(x*r)) where r = 1 + sqrt(3). - Benoit Cloitre, Feb 19 2004
a(n) = L(n-1,4), where L is defined as in A108299; see also A001834 for L(n,-4). - Reinhard Zumkeller, Jun 01 2005
Values x + y, where (x, y) solves for x^2 - 3*y^2 = 1, i.e., a(n) = A001075(n) + A001353(n). - Lekraj Beedassy, Jul 21 2006
Number of 01-avoiding words of length n on alphabet {0,1,2,3} which do not end in 0. (E.g., for n = 2 we have 02, 03, 11, 12, 13, 21, 22, 23, 31, 32, 33.) - Tanya Khovanova, Jan 10 2007
sqrt(3) = 2/2 + 2/3 + 2/(3*11) + 2/(11*41) + 2/(41*153) + 2/(153*571) + ... - Gary W. Adamson, Dec 18 2007
The lower principal convergents to 3^(1/2), beginning with 1/1, 5/3, 19/11, 71/41, comprise a strictly increasing sequence; numerators = A001834, denominators = A001835. - Clark Kimberling, Aug 27 2008
From Gary W. Adamson, Jun 21 2009: (Start)
A001835 and A001353 = bisection of denominators of continued fraction [1, 2, 1, 2, 1, 2, ...]; i.e., bisection of A002530.
a(n) = determinant of an n*n tridiagonal matrix with 1's in the super- and subdiagonals and (3, 4, 4, 4, ...) as the main diagonal.
Also, the product of the eigenvalues of such matrices: a(n) = Product_{k=1..(n-1)/2)} (4 + 2*cos(2*k*Pi/n).
(End)
Let M = a triangle with the even-indexed Fibonacci numbers (1, 3, 8, 21, ...) in every column, and the leftmost column shifted up one row. a(n) starting (1, 3, 11, ...) = lim_{n->oo} M^n, the left-shifted vector considered as a sequence. - Gary W. Adamson, Jul 27 2010
a(n+1) is the number of compositions of n when there are 3 types of 1 and 2 types of other natural numbers. - Milan Janjic, Aug 13 2010
For n >= 2, a(n) equals the permanent of the (2*n-2) X (2*n-2) tridiagonal matrix with sqrt(2)'s along the main diagonal, and 1's along the superdiagonal and the subdiagonal. - John M. Campbell, Jul 08 2011
Primes in the sequence are apparently those in A096147. - R. J. Mathar, May 09 2013
Except for the first term, positive values of x (or y) satisfying x^2 - 4xy + y^2 + 2 = 0. - Colin Barker, Feb 04 2014
Except for the first term, positive values of x (or y) satisfying x^2 - 14xy + y^2 + 32 = 0. - Colin Barker, Feb 10 2014
The (1,1) element of A^n where A = (1, 1, 1; 1, 2, 1; 1, 1, 2). - David Neil McGrath, Jul 23 2014
Yong Hao Ng has shown that for any n, a(n) is coprime with any member of A001834 and with any member of A001075. - René Gy, Feb 25 2018
a(n+1) is the number of spanning trees of the graph T_n, where T_n is a 2 X n grid with an additional vertex v adjacent to (1,1) and (2,1). - Kevin Long, May 04 2018
a(n)/A001353(n) is the resistance of an n-ladder graph whose edges are replaced by one-ohm resistors. The resistance in ohms is measured at two nodes at one end of the ladder. It approaches sqrt(3) - 1 for n -> oo. See A342568, A357113, and A357115 for related information. - Hugo Pfoertner, Sep 17 2022
a(n) is the number of ways to tile a 1 X (n-1) strip with three types of tiles: small isosceles right triangles (with small side length 1), 1 X 1 squares formed by joining two of those right triangles along the hypotenuse, and large isosceles right triangles (with large side length 2) formed by joining two of those right triangles along a short leg. As an example, here is one of the a(6)=571 ways to tile a 1 X 5 strip with these kinds of tiles:
   ____________
  | / \ |\   /|  |
  |/_\|\/_||. - Greg Dresden and Arjun Datta, Jun 30 2023
From Klaus Purath, May 11 2024: (Start)
For any two consecutive terms (a(n), a(n+1)) = (x,y): x^2 - 4xy + y^2 = -2 = A028872(-1). In general, the following applies to all sequences (t) satisfying t(i) = 4t(i-1) - t(i-2) with t(0) = 1 and two consecutive terms (x,y): x^2 - 4xy + y^2 = A028872(t(1)-2). This includes and interprets the Feb 04 2014 comments here and on A001075 by Colin Barker and the Dec 12 2012 comment on A001353 by Max Alekseyev. By analogy to this, for three consecutive terms (x,y,z) y^2 - xz = A028872(t(1)-2). This includes and interprets the Jul 10 2021 comment on A001353 by Bernd Mulansky.
If (t) is a sequence satisfying t(k) = 3t(k-1) + 3t(k-2) - t(k-3) or t(k) = 4t(k-1) - t(k-2) without regard to initial values and including this sequence itself, then a(n) = (t(k+2n+1) + t(k))/(t(k+n+1) + t(k+n)) always applies, as long as t(k+n+1) + t(k+n) != 0 for integer k and n >= 1. (End)
Binomial transform of 1, 0, 2, 4, 12, ... (A028860 without the initial -1) and reverse binomial transform of 1, 2, 6, 24, 108, ... (A094433 without the initial 1). - Klaus Purath, Sep 09 2024

Julio R. Bastida, Quadratic properties of a linearly recurrent sequence. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 163-166, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561042 (81e:10009).
Leonhard Euler, (E388) Vollstaendige Anleitung zur Algebra, Zweiter Theil, reprinted in: Opera Omnia. Teubner, Leipzig, 1911, Series (1), Vol. 1, p. 375.
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 329.
Serge Lang, Introduction to Diophantine Approximations, Addison-Wesley, New York, 1966.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics I, p. 292.

T. D. Noe, Table of n, a(n) for n = 0..200
Mudit Aggarwal and Samrith Ram, Generating functions for straight polyomino tilings of narrow rectangles, arXiv:2206.04437 [math.CO], 2022.
R. C. Alperin, A family of nonlinear recurrences and their linear solutions, Fib. Q., 57:4 (2019), 318-321.
Krassimir T. Atanassov and Anthony G. Shannon, On intercalated Fibonacci sequences, Notes on Number Theory and Discrete Mathematics (2020) Vol. 26, No. 3, 218-223.
Steve Butler, Paul Horn, and Eric Tressler, Intersecting Domino Tilings, Fibonacci Quart. 48 (2010), no. 2, 114-120.
Yurii S. Bystryk, Vitalii L. Denysenko, and Volodymyr I. Ostryk, Lune and Lens Sequences, ResearchGate preprint, 2024. See pp. 31, 56.
Niccolò Castronuovo, On the number of fixed points of the map gamma, arXiv:2102.02739 [math.NT], 2021. Mentions this sequence.
A. Consilvio et al., Tilings, ordered partitions, and weird languages, MAA FOCUS, June/July 2012, 16-17.
J. B. Cosgrave and K. Dilcher, A role for generalized Fermat numbers, Math. Comp., to appear 2016; (See paper #10).
J. B. Cosgrave and K. Dilcher, A role for generalized Fermat numbers, Math. Comp. 86 (2017), 899-933.
Leonhard Euler, Vollstaendige Anleitung zur Algebra, Zweiter Teil.
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
F. Faase, Counting Hamiltonian cycles in product graphs.
F. Faase, Results from the counting program.
Alex Fink, Richard K. Guy, and Mark Krusemeyer, Partitions with parts occurring at most thrice, Contributions to Discrete Mathematics, Vol 3, No 2 (2008), pp. 76-114. See Section 13.
Darren B. Glass, Critical groups of graphs with dihedral actions. II, Eur. J. Comb. 61, 25-46 (2017).
H. Hosoya and A. Motoyama, An effective algorithm for obtaining polynomials for dimer statistics. Application of operator technique on the topological index to two- and three-dimensional rectangular and torus lattices, J. Math. Physics 26 (1985) 157-167 (Table V).
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 409.
Tanya Khovanova, Recursive Sequences,
Clark Kimberling, Best lower and upper approximates to irrational numbers, Elemente der Mathematik, 52 (1997) 122-126.
David Klarner and Jordan Pollack, Domino tilings of rectangles with fixed width, Disc. Math. 32 (1980) 45-52.
R. J. Mathar, Paving Rectangular Regions with Rectangular Tiles: Tatami and Non-Tatami Tilings, arXiv:1311.6135 [math.CO], 2013, Table 2.
R. J. Mathar, Tilings of rectangular regions by rectangular tiles: Counts derived from transfer matrices, arXiv:1406.7788 (2014), eq. (4).
Valcho Milchev and Tsvetelina Karamfilova, Domino tiling in grid - new dependence, arXiv:1707.09741 [math.HO], 2017.
Yong Hao Ng, A partition in three classes of the set of all prime numbers?, Math StackExchange.
J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), 609-640.
John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their N-numbers, not their A-numbers.
David Singmaster, Letter to N. J. A. Sloane, Oct 3 1982.
Anitha Srinivasan, The Markoff-Fibonacci Numbers, Fibonacci Quart. 58 (2020), no. 5, 222-228.
Thotsaporn "Aek" Thanatipanonda, Statistics of Domino Tilings on a Rectangular Board, Fibonacci Quart. 57 (2019), no. 5, 145-153. See p. 151.
Herman Tulleken, Polyominoes 2.2: How they fit together, (2019).
F. V. Waugh and M. W. Maxfield, Side-and-diagonal numbers, Math. Mag., 40 (1967), 74-83.
Index entries for sequences related to dominoes.
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (4,-1).

Row 3 of array A099390.
Essentially the same as A079935.
First differences of A001353.
Partial sums of A052530.
Pairwise sums of A006253.
Bisection of A002530, A005246 and A048788.
First column of array A103997.
Cf. A001519, A003699, A082841, A101265, A125077, A001353, A001542, A096147 (subsequence of primes).

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

a001835 n = a001835_list !! n
a001835_list =
   1 : 1 : zipWith (-) (map (4 *) $ tail a001835_list) a001835_list
-- Reinhard Zumkeller, Aug 14 2011

[n le 2 select 1 else 4*Self(n-1)-Self(n-2): n in [1..25]]; // Vincenzo Librandi, Sep 16 2016

f:=n->((3+sqrt(3))^(2*n-1)+(3-sqrt(3))^(2*n-1))/6^n; [seq(simplify(expand(f(n))),n=0..20)]; # N. J. A. Sloane, Nov 10 2009

CoefficientList[Series[(1-3x)/(1-4x+x^2), {x, 0, 24}], x] (* Jean-François Alcover, Jul 25 2011, after g.f. *)
LinearRecurrence[{4,-1},{1,1},30] (* Harvey P. Dale, Jun 08 2013 *)
Table[Round@Fibonacci[2n-1, Sqrt[2]], {n, 0, 20}] (* Vladimir Reshetnikov, Sep 15 2016 *)
Table[(3*ChebyshevT[n, 2] - ChebyshevU[n, 2])/2, {n, 0, 20}] (* G. C. Greubel, Dec 23 2019 *)

{a(n) = real( (2 + quadgen(12))^n * (1 - 1 / quadgen(12)) )} /* Michael Somos, Sep 19 2008 */

{a(n) = subst( (polchebyshev(n) + polchebyshev(n-1)) / 3, x, 2)} /* Michael Somos, Sep 19 2008 */

[lucas_number1(n,4,1)-lucas_number1(n-1,4,1) for n in range(25)] # Zerinvary Lajos, Apr 29 2009

[(3*chebyshev_T(n,2) - chebyshev_U(n,2))/2 for n in (0..20)] # G. C. Greubel, Dec 23 2019

G.f.: (1 - 3*x)/(1 - 4*x + x^2). - Simon Plouffe in his 1992 dissertation
a(1-n) = a(n).
a(n) = ((3 + sqrt(3))^(2*n - 1) + (3 - sqrt(3))^(2*n - 1))/6^n. - Dean Hickerson, Dec 01 2002
a(n) = (8 + a(n-1)*a(n-2))/a(n-3). - Michael Somos, Aug 01 2001
a(n+1) = Sum_{k=0..n} 2^k * binomial(n + k, n - k), n >= 0. - Len Smiley, Dec 09 2001
Limit_{n->oo} a(n)/a(n-1) = 2 + sqrt(3). - Gregory V. Richardson, Oct 10 2002
a(n) = 2*A061278(n-1) + 1 for n > 0. - Bruce Corrigan (scentman(AT)myfamily.com), Nov 04 2002
Let q(n, x) = Sum_{i=0..n} x^(n-i)*binomial(2*n - i, i); then q(n, 2) = a(n+1). - Benoit Cloitre, Nov 10 2002
a(n+1) = Sum_{k=0..n} ((-1)^k)*((2*n+1)/(2*n + 1 - k))*binomial(2*n + 1 - k, k)*6^(n - k) (from standard T(n,x)/x, n >= 1, Chebyshev sum formula). The Smiley and Cloitre sum representation is that of the S(2*n, i*sqrt(2))*(-1)^n Chebyshev polynomial. - Wolfdieter Lang, Nov 29 2002
a(n) = S(n-1, 4) - S(n-2, 4) = T(2*n-1, sqrt(3/2))/sqrt(3/2) = S(2*(n-1), i*sqrt(2))*(-1)^(n - 1), with S(n, x) := U(n, x/2), resp. T(n, x), Chebyshev's polynomials of the second, resp. first, kind. See A049310 and A053120. S(-1, x) = 0, S(-2, x) = -1, S(n, 4) = A001353(n+1), T(-1, x) = x.
a(n+1) = sqrt((A001834(n)^2 + 2)/3), n >= 0 (see Cloitre comment).
Sequence satisfies -2 = f(a(n), a(n+1)) where f(u, v) = u^2 + v^2 - 4*u*v. - Michael Somos, Sep 19 2008
a(n) = (1/6)*(3*(2 - sqrt(3))^n + sqrt(3)*(2 - sqrt(3))^n + 3*(2 + sqrt(3))^n - sqrt(3)*(2 + sqrt(3))^n) (Mathematica's solution to the recurrence relation). - Sarah-Marie Belcastro, Jul 04 2009
If p[1] = 3, p[i] = 2, (i > 1), and if A is Hessenberg matrix of order n defined by: A[i,j] = p[j-i+1], (i <= j), A[i,j] = -1, (i = j+1), and A[i,j] = 0 otherwise. Then, for n >= 1, a(n+1) = det A. - Milan Janjic, Apr 29 2010
a(n) = (a(n-1)^2 + 2)/a(n-2). - Irene Sermon, Oct 28 2013
a(n) = A001353(n+1) - 3*A001353(n). - R. J. Mathar, Oct 30 2015
a(n) = a(n-1) + 2*A001353(n-1). - Kevin Long, May 04 2018
From Franck Maminirina Ramaharo, Nov 11 2018: (Start)
a(n) = (-1)^n*(A125905(n) + 3*A125905(n-1)), n > 0.
E.g.f.: exp^(2*x)*(3*cosh(sqrt(3)*x) - sqrt(3)*sinh(sqrt(3)*x))/3. (End)
From Peter Bala, Feb 12 2024: (Start)
For n in Z, a(n) = A001353(n) + A001353(1-n).
For n, j, k in Z, a(n)*a(n+j+k) - a(n+j)*a(n+k) = 2*A001353(j)*A001353(k). The case j = 1, k = 2 is given above. (End)

A003500 a(n) = 4*a(n-1) - a(n-2) with a(0) = 2, a(1) = 4.

Original entry on oeis.org

2, 4, 14, 52, 194, 724, 2702, 10084, 37634, 140452, 524174, 1956244, 7300802, 27246964, 101687054, 379501252, 1416317954, 5285770564, 19726764302, 73621286644, 274758382274, 1025412242452, 3826890587534, 14282150107684, 53301709843202, 198924689265124

Offset: 0

N. J. A. Sloane

a(n) gives values of x satisfying x^2 - 3*y^2 = 4; corresponding y values are given by 2*A001353(n).
If M is any given term of the sequence, then the next one is 2*M + sqrt(3*M^2 - 12). - Lekraj Beedassy, Feb 18 2002
For n > 0, the three numbers a(n) - 1, a(n), and a(n) + 1 form a Fleenor-Heronian triangle, i.e., a Heronian triangle with consecutive sides, whose area A(n) may be obtained from the relation [4*A(n)]^2 = 3([a(2n)]^2 - 4); or A(n) = 3*A001353(2*n)/2 and whose semiperimeter is 3*a[n]/2. The sequence is symmetrical about a[0], i.e., a[-n] = a[n].
For n > 0, a(n) + 2 is the number of dimer tilings of a 2*n X 2 Klein bottle (cf. A103999).
Tsumura shows that, for prime p, a(p) is composite (contrary to a conjecture of Juricevic). - Charles R Greathouse IV, Apr 13 2010
Except for the first term, positive values of x (or y) satisfying x^2 - 4*x*y + y^2 + 12 = 0. - Colin Barker, Feb 04 2014
Except for the first term, positive values of x (or y) satisfying x^2 - 14*x*y + y^2 + 192 = 0. - Colin Barker, Feb 16 2014
A268281(n) - 1 is a member of this sequence iff A268281(n) is prime. - Frank M Jackson, Feb 27 2016
a(n) gives values of x satisfying 3*x^2 - 4*y^2 = 12; corresponding y values are given by A005320. - Sture Sjöstedt, Dec 19 2017
Middle side lengths of almost-equilateral Heronian triangles. - Wesley Ivan Hurt, May 20 2020
For all elements k of the sequence, 3*(k-2)*(k+2) is a square. - Davide Rotondo, Oct 25 2020

B. C. Berndt, Ramanujan's Notebooks Part IV, Springer-Verlag, see p. 82.
J. M. Borwein and P. B. Borwein, Pi and the AGM, Wiley, 1987, p.91.
Michael P. Cohen, Generating Heronian Triangles With Consecutive Integer Sides. Journal of Recreational Mathematics, vol. 30 no. 2 1999-2000 p. 123.
L. E. Dickson, History of The Theory of Numbers, Vol. 2 pp. 197;198;200;201. Chelsea NY.
Charles R. Fleenor, Heronian Triangles with Consecutive Integer Sides, Journal of Recreational Mathematics, Volume 28, no. 2 (1996-7) 113-115.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999.
V. D. To, "Finding All Fleenor-Heronian Triangles", Journal of Recreational Mathematics vol. 32 no.4 2003-4 pp. 298-301 Baywood NY.

T. D. Noe, Table of n, a(n) for n=0..200
P. Bala, Some simple continued fraction expansions for an infinite product, Part 1
R. A. Beauregard and E. R. Suryanarayan, The Brahmagupta Triangles, The College Mathematics Journal 29(1) 13-7 1998 MAA.
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, Linear recurrence sequences with indices in arithmetic progression and their sums, arXiv preprint arXiv:1505.06339 [math.NT], 2015.
K. S. Brown's Mathpages, Some Properties of the Lucas Sequence(2, 4, 14, 52, 194, ...)
H. W. Gould, A triangle with integral sides and area, Fib. Quart., 11 (1973), 27-39.
Tanya Khovanova, Recursive Sequences
E. Keith Lloyd, The Standard Deviation of 1, 2, ..., n: Pell's Equation and Rational Triangles, Math. Gaz. vol 81 (1997), 231-243.
S. Northshield, An Analogue of Stern's Sequence for Z[sqrt(2)], Journal of Integer Sequences, 18 (2015), #15.11.6.
Hideyuki Ohtskua, proposer, Problem B-1351, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 62, No. 3 (2024), p. 258.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Jeffrey Shallit, An interesting continued fraction, Math. Mag., 48 (1975), 207-211.
Jeffrey Shallit, An interesting continued fraction, Math. Mag., 48 (1975), 207-211. [Annotated scanned copy]
Yu Tsumura, On compositeness of special types of integers, arXiv:1004.1244 [math.NT], 2010.
Eric Weisstein's World of Mathematics, Heronian Triangle
Wikipedia, Heronian triangle
A. V. Zarelua, On Matrix Analogs of Fermat's Little Theorem, Mathematical Notes, vol. 79, no. 6, 2006, pp. 783-796. Translated from Matematicheskie Zametki, vol. 79, no. 6, 2006, pp. 840-855.
Index entries for recurrences a(n) = k*a(n - 1) +/- a(n - 2)
Index entries for linear recurrences with constant coefficients, signature (4,-1).

Cf. A001075, A001353, A001835.
Cf. A011945 (areas), A334277 (perimeters).
Cf. this sequence (middle side lengths), A016064 (smallest side lengths), A335025 (largest side lengths).
Cf. A001570, A002530, A005320, A006051, A048788, A174500, A268281.
Cf. A011943, A102344, A019673, A105531.

a003500 n = a003500_list !! n
a003500_list = 2 : 4 : zipWith (-)
   (map (* 4) $ tail a003500_list) a003500_list
-- Reinhard Zumkeller, Dec 17 2011

I:=[2,4]; [n le 2 select I[n] else 4*Self(n-1)-Self(n-2): n in [1..30]]; // Vincenzo Librandi, Nov 14 2018

A003500 := proc(n) option remember; if n <= 1 then 2*n+2 else 4*procname(n-1)-procname(n-2); fi;
end proc;

a[0]=2; a[1]=4; a[n_]:= a[n]= 4a[n-1] -a[n-2]; Table[a[n], {n, 0, 23}]
LinearRecurrence[{4,-1},{2,4},30] (* Harvey P. Dale, Aug 20 2011 *)
Table[Round@LucasL[2n, Sqrt[2]], {n, 0, 20}] (* Vladimir Reshetnikov, Sep 15 2016 *)

x='x+O('x^99); Vec(-2*(-1+2*x)/(1-4*x+x^2)) \\ Altug Alkan, Apr 04 2016

[lucas_number2(n,4,1) for n in range(0, 24)] # Zerinvary Lajos, May 14 2009

a(n) = ( 2 + sqrt(3) )^n + ( 2 - sqrt(3) )^n.
a(n) = 2*A001075(n).
G.f.: 2*(1 - 2*x)/(1 - 4*x + x^2). Simon Plouffe in his 1992 dissertation.
a(n) = A001835(n) + A001835(n+1).
a(n) = trace of n-th power of the 2 X 2 matrix [1 2 / 1 3]. - Gary W. Adamson, Jun 30 2003 [corrected by Joerg Arndt, Jun 18 2020]
From the addition formula, a(n+m) = a(n)*a(m) - a(m-n), it is easy to derive multiplication formulas, such as: a(2*n) = (a(n))^2 - 2, a(3*n) = (a(n))^3 - 3*(a(n)), a(4*n) = (a(n))^4 - 4*(a(n))^2 + 2, a(5*n) = (a(n))^5 - 5*(a(n))^3 + 5*(a(n)), a(6*n) = (a(n))^6 - 6*(a(n))^4 + 9*(a(n))^2 - 2, etc. The absolute values of the coefficients in the expansions are given by the triangle A034807. - John Blythe Dobson, Nov 04 2007
a(n) = 2*A001353(n+1) - 4*A001353(n). - R. J. Mathar, Nov 16 2007
From Peter Bala, Jan 06 2013: (Start)
Let F(x) = Product_{n=0..infinity} (1 + x^(4*n + 1))/(1 + x^(4*n + 3)). Let alpha = 2 - sqrt(3). This sequence gives the simple continued fraction expansion of 1 + F(alpha) = 2.24561 99455 06551 88869 ... = 2 + 1/(4 + 1/(14 + 1/(52 + ...))). Cf. A174500.
Also F(-alpha) = 0.74544 81786 39692 68884 ... has the continued fraction representation 1 - 1/(4 - 1/(14 - 1/(52 - ...))) and the simple continued fraction expansion 1/(1 + 1/((4 - 2) + 1/(1 + 1/((14 - 2) + 1/(1 + 1/((52 - 2) + 1/(1 + ...))))))).
F(alpha)*F(-alpha) has the simple continued fraction expansion 1/(1 + 1/((4^2 - 4) + 1/(1 + 1/((14^2 - 4) + 1/(1 + 1/((52^2 - 4) + 1/(1 + ...))))))).
(End)
a(2^n) = A003010(n). - John Blythe Dobson, Mar 10 2014
a(n) = [x^n] ( (1 + 4*x + sqrt(1 + 8*x + 12*x^2))/2 )^n for n >= 1. - Peter Bala, Jun 23 2015
E.g.f.: 2*exp(2*x)*cosh(sqrt(3)*x). - Ilya Gutkovskiy, Apr 27 2016
a(n) = Sum_{k=0..floor(n/2)} (-1)^k*n*(n - k - 1)!/(k!*(n - 2*k)!)*4^(n - 2*k) for n >= 1. - Peter Luschny, May 10 2016
From Peter Bala, Oct 15 2019: (Start)
a(n) = trace(M^n), where M is the 2 X 2 matrix [0, 1; -1, 4].
Consequently the Gauss congruences hold: a(n*p^k) = a(n*p^(k-1)) ( mod p^k ) for all prime p and positive integers n and k. See Zarelua and also Stanley (Ch. 5, Ex. 5.2(a) and its solution).
2*Sum_{n >= 1} 1/( a(n) - 6/a(n) ) = 1.
6*Sum_{n >= 1} (-1)^(n+1)/( a(n) + 2/a(n) ) = 1.
8*Sum_{n >= 1} 1/( a(n) + 24/(a(n) - 12/(a(n))) ) = 1.
8*Sum_{n >= 1} (-1)^(n+1)/( a(n) + 8/(a(n) + 4/(a(n))) ) = 1.
Series acceleration formulas for sums of reciprocals:
Sum_{n >= 1} 1/a(n) = 1/2 - 6*Sum_{n >= 1} 1/(a(n)*(a(n)^2 - 6)),
Sum_{n >= 1} 1/a(n) = 1/8 + 24*Sum_{n >= 1} 1/(a(n)*(a(n)^2 + 12)),
Sum_{n >= 1} (-1)^(n+1)/a(n) = 1/6 + 2*Sum_{n >= 1} (-1)^(n+1)/(a(n)*(a(n)^2 + 2)) and
Sum_{n >= 1} (-1)^(n+1)/a(n) = 1/8 + 8*Sum_{n >= 1} (-1)^(n+1)/(a(n)*(a(n)^2 + 12)).
Sum_{n >= 1} 1/a(n) = ( theta_3(2-sqrt(3))^2 - 1 )/4 = 0.34770 07561 66992 06261 .... See Borwein and Borwein, Proposition 3.5 (i), p.91.
Sum_{n >= 1} (-1)^(n+1)/a(n) = ( 1 - theta_3(sqrt(3)-2)^2 )/4. Cf. A003499 and A153415. (End)
a(n) = tan(Pi/12)^n + tan(5*Pi/12)^n. - Greg Dresden, Oct 01 2020
From Wolfdieter Lang, Sep 06 2021: (Start)
a(n) = S(n, 4) - S(n-2, 4) = 2*T(n, 2), for n >= 0, with S and T Chebyshev polynomials, with S(-1, x) = 0 and S(-2, x) = -1. S(n, 4) = A001353(n+1), for n >= -1, and T(n, 2) = A001075(n).
a(2*k) = A067902(k), a(2*k+1) = 4*A001570(k+1), for k >= 0. (End)
a(n) = sqrt(2 + 2*A011943(n+1)) = sqrt(2 + 2*A102344(n+1)), n>0. - Ralf Steiner, Sep 23 2021
Sum_{n>=1} arctan(3/a(n)^2) = Pi/6 - arctan(1/3) = A019673 - A105531 (Ohtskua, 2024). - Amiram Eldar, Aug 29 2024

More terms from James Sellers, May 03 2000

Additional comments from Lekraj Beedassy, Feb 14 2002

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

Original entry on oeis.org

1, 1, 2, 5, 7, 19, 26, 71, 97, 265, 362, 989, 1351, 3691, 5042, 13775, 18817, 51409, 70226, 191861, 262087, 716035, 978122, 2672279, 3650401, 9973081, 13623482, 37220045, 50843527, 138907099, 189750626, 518408351, 708158977, 1934726305

Offset: 0

N. J. A. Sloane

Numerators of continued fraction convergents to sqrt(3), for n >= 1.
For the denominators see A002530.
Consider the mapping f(a/b) = (a + 3*b)/(a + b). Taking a = b = 1 to start with and carrying out this mapping repeatedly on each new (reduced) rational number gives the convergents 1/1, 2/1, 5/3, 7/4, 19/11, ... converging to sqrt(3). Sequence contains the numerators. - Amarnath Murthy, Mar 22 2003
In the Murthy comment if we take a = 0, b = 1 then the denominator of the reduced fraction is a(n+1). A083336(n)/a(n+1) converges to sqrt(3). - Mario Catalani (mario.catalani(AT)unito.it), Apr 26 2003
If signs are disregarded, all terms of A002316 appear to be elements of this sequence. - Creighton Dement, Jun 11 2007
2^(-floor(n/2))*(1 + sqrt(3))^n = a(n) + A002530(n)*sqrt(3); integers in the real quadratic number field Q(sqrt(3)). - Wolfdieter Lang, Feb 10 2018
Let T(n) = A000034(n), U(n) = A002530(n), V(n) = a(n), x(n) = U(n)/V(n). Then T(n*m) * U(n+m) = U(n)*V(m) + U(m)*V(n), T(n*m) * V(n+m) = 3*U(n)*U(m) + V(m)*V(n), x(n+m) = (x(n) + x(m))/(1 + 3*x(n)*x(m)). - Michael Somos, Nov 29 2022

			1 + 1/(1 + 1/(2 + 1/(1 + 1/2))) = 19/11 so a(5) = 19.
Convergents are 1, 2, 5/3, 7/4, 19/11, 26/15, 71/41, 97/56, 265/153, 362/209, 989/571, 1351/780, 3691/2131, ... = A002531/A002530.
G.f. = 1 + x + 2*x^2 + 5*x^3 + 7*x^4 + 19*x^5 + 26*x^6 + 71*x^7 + ... - _Michael Somos_, Mar 22 2022

I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 181.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
A. Tarn, Approximations to certain square roots and the series of numbers connected therewith, Mathematical Questions and Solutions from the Educational Times, 1 (1916), 8-12.

Harry J. Smith, Table of n, a(n) for n = 0..2000
MacTutor, D'Arcy Thompson on Greek irrationals
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Albert Tarn, Approximations to certain square roots and the series of numbers connected therewith [Annotated scanned copy]
D'Arcy Thompson, Excess and Defect: Or the Little More and the Little Less, Mind, New Series, Vol. 38, No. 149 (Jan., 1929), pp. 43-55 (13 pages). See page 48.
Hein van Winkel, Q-quadrangles inscribed in a circle, 2014. See Table 1. [Reference from Antreas Hatzipolakis, Jul 14 2014]
Index entries for "core" sequences
Index entries for linear recurrences with constant coefficients, signature (0,4,0,-1).
Index entries for sequences related to Chebyshev polynomials.

Bisections are A001075 and A001834.
Cf. A002530 (denominators), A048788.
Cf. A002316.
Cf. A083332, A199710, A026150, A053120.

a:=[1,1,2,5];; for n in [5..40] do a[n]:=4*a[n-2]-a[n-4]; od; a; # G. C. Greubel, Nov 16 2018

m:=40; R:=PowerSeriesRing(Integers(), m); Coefficients(R!( (1 +x-2*x^2+x^3)/(1-4*x^2+x^4))); // G. C. Greubel, Nov 16 2018

A002531 := proc(n) option remember; if n=0 then 0 elif n=1 then 1 elif n=2 then 1 elif type(n,odd) then A002531(n-1)+A002531(n-2) else 2*A002531(n-1)+A002531(n-2) fi; end; [ seq(A002531(n), n=0..50) ];
with(numtheory): tp := cfrac (tan(Pi/3),100): seq(nthnumer(tp,i), i=-1..32 ); # Zerinvary Lajos, Feb 07 2007
A002531:=(1+z-2*z**2+z**3)/(1-4*z**2+z**4); # Simon Plouffe; see his 1992 dissertation

Insert[Table[Numerator[FromContinuedFraction[ContinuedFraction[Sqrt[3], n]]], {n, 1, 40}], 1, 1] (* Stefan Steinerberger, Apr 01 2006 *)
Join[{1},Numerator[Convergents[Sqrt[3],40]]] (* Harvey P. Dale, Jan 23 2012 *)
CoefficientList[Series[(1 + x - 2 x^2 + x^3)/(1 - 4 x^2 + x^4), {x, 0, 30}], x] (* Vincenzo Librandi, Nov 01 2014 *)
LinearRecurrence[{0, 4, 0, -1}, {1, 1, 2, 5}, 35] (* Robert G. Wilson v, Feb 11 2018 *)
a[ n_] := ChebyshevT[n, Sqrt[-1/2]]*Sqrt[2]^Mod[n,2]/I^n //Simplify; (* Michael Somos, Mar 22 2022 *)
a[ n_] := If[n<0, (-1)^n*a[-n], SeriesCoefficient[ (1 + x - 2*x^2 + x^3) / (1 - 4*x^2 + x^4), {x, 0, n}]]; (* Michael Somos, Sep 23 2024 *)

a(n)=contfracpnqn(vector(n,i,1+(i>1)*(i%2)))[1,1]

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

{a(n) = if(n<0, (-1)^n*a(-n), polcoeff( (1 + x - 2*x^2 + x^3) / (1 - 4*x^2 + x^4) + x*O(x^n), n))}; /* Michael Somos, Sep 23 2024 */

s=((1+x-2*x^2+x^3)/(1-4*x^2+x^4)).series(x,40); s.coefficients(x, sparse=False) # G. C. Greubel, Nov 16 2018

G.f.: (1 + x - 2*x^2 + x^3)/(1 - 4*x^2 + x^4).
a(2*n) = a(2*n-1) + a(2*n-2), a(2*n+1) = 2*a(2*n) + a(2*n-1), n > 0.
a(2*n) = (1/2)*((2 + sqrt(3))^n+(2 - sqrt(3))^n); a(2*n) = A003500(n)/2; a(2*n+1) = round(1/(1 + sqrt(3))*(2 + sqrt(3))^n). - Benoit Cloitre, Dec 15 2002
a(n) = ((1 + sqrt(3))^n + (1 - sqrt(3))^n)/(2*2^floor(n/2)). - Bruno Berselli, Nov 10 2011
a(n) = A080040(n)/(2*2^floor(n/2)). - Ralf Stephan, Sep 08 2013
a(2*n) = (-1)^n*T(2*n,u) and a(2*n+1) = (-1)^n*1/u*T(2*n+1,u), where u = sqrt(-1/2) and T(n,x) denotes the Chebyshev polynomial of the first kind. - Peter Bala, May 01 2012
a(n) = (-sqrt(2)*i)^n*T(n, sqrt(2)*i/2)*2^(-floor(n/2)) = A026150(n)*2^(-floor(n/2)), n >= 0, with i = sqrt(-1) and the Chebyshev T polynomials (A053120). - Wolfdieter Lang, Feb 10 2018
From Franck Maminirina Ramaharo, Nov 14 2018: (Start)
a(n) = ((1 - sqrt(2))*(-1)^n + 1 + sqrt(2))*(((sqrt(2) - sqrt(6))/2)^n + ((sqrt(6) + sqrt(2))/2)^n)/4.
E.g.f.: cosh(sqrt(3/2)*x)*(sqrt(2)*sinh(x/sqrt(2)) + cosh(x/sqrt(2))). (End)
a(n) = (-1)^n*a(-n) for all n in Z. - Michael Somos, Mar 22 2022
a(n) = 4*a(n-2) - a(n-4). - Boštjan Gec, Sep 21 2023

Name edited (as by discussion in A002530) by M. F. Hasler, Nov 04 2019

A006253 Number of perfect matchings (or domino tilings) in C_4 X P_n.

Original entry on oeis.org

1, 2, 9, 32, 121, 450, 1681, 6272, 23409, 87362, 326041, 1216800, 4541161, 16947842, 63250209, 236052992, 880961761, 3287794050, 12270214441, 45793063712, 170902040409, 637815097922, 2380358351281, 8883618307200, 33154114877521, 123732841202882

Offset: 0

N. J. A. Sloane

Number of tilings of a box with sides 2 X 2 X n in R^3 by boxes of sides 2 X 1 X 1 (3-dimensional dominoes). - Frans J. Faase
The number of domino tilings in A006253, A004003, A006125 is the number of perfect matchings in the relevant graphs. There are results of Jockusch and Ciucu that if a planar graph has a rotational symmetry then the number of perfect matchings is a square or twice a square - this applies to these 3 sequences. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 12 2001
Also stacking bricks.
a(n)*(-1)^n = (1-T(n+1,-2))/3, n>=0, with Chebyshev's polynomials T(n,x) of the first kind, is the r=-2 member of the r-family of sequences S_r(n) defined in A092184 where more information can be found. - Wolfdieter Lang, Oct 18 2004
Partial sums of A217233. - Bruno Berselli, Oct 01 2012
The sequence is the case P1 = 2, P2 = -8, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - Peter Bala, Apr 03 2014

			G.f. = 1 + 2*x + 9*x^2 + 32*x^3 + 121*x^4 + 450*x^5 + ... - _Michael Somos_, Mar 17 2022

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 360.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
S. Butler and S. Osborne, Counting tilings by taking walks, preprint, 2012; J. Combin. Math. Combin. Comput. 88 2014 17-25. - From _N. J. A. Sloane_, Dec 27 2012
M. Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry, J. Combin. Theory Ser. A 77 (1997), no. 1, 67-97
D. Deford, Seating rearrangements on arbitrary graphs, preprint 2013; involve, Vol. 7 (2014), No. 6, 787-805.
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
Charles H. Jepsen, Packing a box with bricks, Math. Mag. 64 (2) (1991) 92-97, Table 1
W. Jockusch, Perfect matchings and perfect squares J. Combin. Theory Ser. A 67 (1994), no. 1, 100-115.
R. J. Mathar, Tilings of rectangular regions by rectangular tiles: Counts derived from transfer matrices, arXiv:1406.7788 (2014), eq. (36).
Valcho Milchev and Tsvetelina Karamfilova, Domino tiling in grid - new dependence, arXiv:1707.09741 [math.HO], 2017.
László Németh, Tilings of (2 X 2 X n)-board with colored cubes and bricks, arXiv:1909.11729 [math.CO], 2019.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Radovan Potůček, The number of fillings a 2 X 2 X n prism with 1 X 1 X 2 prisms, Equations (2024) Vol. 3, 104-114.
H. C. Williams and R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory 7 (5) (2011) 1255-1277.
H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences Integers, Volume 12A (2012) The John Selfridge Memorial Volume
Index entries for sequences related to dominoes
Index entries for sequences related to bricks
Index entries for linear recurrences with constant coefficients, signature (3,3,-1).

Cf. A002530, A004003, A006125, A217233 (first differences), A109437 (partial sums).
Column k=2 of A181206, A189650, A233308.
Cf. A100047.

a:=[1,2,9];; for n in [4..30] do a[n]:=3*a[n-1]+3*a[n-2]-a[n-3]; od; a; # G. C. Greubel, Nov 16 2018

m:=30; R:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-x)/(1-3*x-3*x^2+x^3))); // G. C. Greubel, Nov 16 2018

CoefficientList[Series[(1 - x)/(1 - 3 x - 3 x^2 + x^3), {x, 0, 30}], x] (* Vincenzo Librandi, Oct 15 2012 *)
RecurrenceTable[{a[1] == 1, a[2] == 2, a[n] == BitXor[1, a[n - 1]]^2/a[n - 2]}, a, {n, 30}] (* Jon Maiga, Nov 16 2018 *)
LinearRecurrence[{3,3,-1}, {1,2,9}, 30] (* G. C. Greubel, Nov 16 2018 *)
a[ n_] := (-1)^n * ChebyshevU[n, Sqrt[-1/2]]^2; (* Michael Somos, Mar 17 2022 *)

a(n)=(sqrt(3)+2)^(n+1) \/ 6 \\ Charles R Greathouse IV, Aug 18 2016

a(n)=([0,1,0; 0,0,1; -1,3,3]^n*[1;2;9])[1,1] \\ Charles R Greathouse IV, Aug 18 2016

Vec((1 - x) / ((1 + x)*(1 - 4*x + x^2)) + O(x^40)) \\ Colin Barker, Dec 16 2017

{a(n) = simplify((-1)^n * polchebyshev(n, 2, quadgen(-8)/2)^2)}; /* Michael Somos, Mar 17 2022 */

s=((1-x)/(1-3*x-3*x^2+x^3)).series(x,30); s.coefficients(x, sparse=False) # G. C. Greubel, Nov 16 2018

G.f.: (1-x)/((1+x)*(1-4*x+x^2)) = (1-x)/(1-3*x-3*x^2+x^3). - Simon Plouffe in his 1992 dissertation; typo corrected by Vincenzo Librandi, Oct 15 2012
Nearest integer to (1/6)*(2+sqrt(3))^(n+1). - Don Knuth, Jul 15 1995
For n >= 4, a(n) = 3a(n-1) + 3a(n-2) - a(n-3). - Avi Peretz (njk(AT)netvision.net.il), Mar 30 2001
For n >= 3, a(n) = 4a(n-1) - a(n-2) + 2*(-1)^n. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 14 2001
From Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 11 2001: The values are a(1) = 2 * 1^2, a(2) = 3^2, a(3) = 2 * 4^2, a(4) = 11^2, a(5) = 2 * 15^2, ... and in general for odd n a(n) is twice a square, for even n a(n) is a square. If we define b(n) by b(n) = sqrt(a(n)) for even n, b(n) = sqrt(a(n)/2) for odd n then apart from the first 2 elements b(n) is A002530(n+1).
a(n) + a(n+1) = A001835(n+2). - R. J. Mathar, Dec 06 2013
From Peter Bala, Apr 03 2014: (Start)
a(n) = |U(n,i/sqrt(2))|^2 where U(n,x) denotes the Chebyshev polynomial of the second kind.
a(n-1) = the bottom left entry of the 2 X 2 matrix T(n, M), where M is the 2 X 2 matrix [0, 2; 1, 1] and T(n,x) denotes the Chebyshev polynomial of the first kind.
See the remarks in A100047 for the general connection between Chebyshev polynomials of the first kind and 4th-order linear divisibility sequences. (End)
a(n) = (2*(-1)^n + (2-sqrt(3))^(1+n) + (2+sqrt(3))^(1+n)) / 6. - Colin Barker, Dec 16 2017
a(n) = (1 XOR a(n-1))^2/a(n-2). - Jon Maiga, Nov 16 2018
a(n) = a(-2-n) for all n in Z. - Michael Somos, Mar 17 2022
INVERT transform of sequence p(n), n > 0, where p is the number of nonreducible tilings by height of 2 X 2 X n using dicubes; p is (2, 5, 4, 4, 4, 4...). - Nicolas Bělohoubek, Jun 04 2024

cp's OEIS Frontend

A321118 T(n,k) = A321119(n) - (-1)^k*A321119(n-2*k)/2 for 0 < k < n, with T(0,0) = 0 and T(n,0) = T(n,n) = A002530(n+1) for n > 0, triangle read by rows; unreduced numerator of the weights of Holladay-Sard's quadrature formula.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Maxima

Formula

A276386 Write A003511(n) in the base {1, 3, 4, 11, 15, 41, 56, 153, 209, ...} (see A002530).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A276387 Write A003512(n) in the base {1, 3, 4, 11, 15, 41, 56, 153, 209, ...} (see A002530).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A276388 Write n in the P-base {1, 3, 4, 11, 15, 41, 56, 153, 209, ...} corresponding to (1+sqrt(3))/2 (see A002530).

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A001353 a(n) = 4*a(n-1) - a(n-2) with a(0) = 0, a(1) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Sage

Sage

Formula

A002605 a(n) = 2*(a(n-1) + a(n-2)), a(0) = 0, a(1) = 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Magma

Maple

Mathematica

PARI

PARI

Sage

A321118 T(n,k) = A321119(n) - (-1)^kA321119(n-2k)/2 for 0 < k < n, with T(0,0) = 0 and T(n,0) = T(n,n) = A002530(n+1) for n > 0, triangle read by rows; unreduced numerator of the weights of Holladay-Sard's quadrature formula.

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