A005246 -id:A005246 - 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)

A005248 Bisection of Lucas numbers: a(n) = L(2n) = A000032(2n).

Original entry on oeis.org

2, 3, 7, 18, 47, 123, 322, 843, 2207, 5778, 15127, 39603, 103682, 271443, 710647, 1860498, 4870847, 12752043, 33385282, 87403803, 228826127, 599074578, 1568397607, 4106118243, 10749957122, 28143753123, 73681302247, 192900153618, 505019158607, 1322157322203

Offset: 0

N. J. A. Sloane

Drop initial 2; then iterates of A050411 do not diverge for these starting values. - David W. Wilson
All nonnegative integer solutions of Pell equation a(n)^2 - 5*b(n)^2 = +4 together with b(n)=A001906(n), n>=0. - Wolfdieter Lang, Aug 31 2004
a(n+1) = B^(n)AB(1), n>=0, with compositions of Wythoff's complementary A(n):=A000201(n) and B(n)=A001950(n) sequences. See the W. Lang link under A135817 for the Wythoff representation of numbers (with A as 1 and B as 0 and the argument 1 omitted). E.g., 3=`10`, 7=`010`, 18=`0010`, 47=`00010`, ..., in Wythoff code. a(0) = 2 = B(1) in Wythoff code.
Output of Tesler's formula (as well as that of Lu and Wu) for the number of perfect matchings of an m X n Möbius band where m and n are both even specializes to this sequence for m=2. - Sarah-Marie Belcastro, Jul 04 2009
Numbers having two 1's in their base-phi representation. - Robert G. Wilson v, Sep 13 2010
Pisano period lengths: 1, 3, 4, 3, 2, 12, 8, 6, 12, 6, 5, 12, 14, 24, 4, 12, 18, 12, 9, 6, ... - R. J. Mathar, Aug 10 2012
From Wolfdieter Lang, Feb 18 2013: (Start)
a(n) is also one half of the total number of round trips, each of length 2*n, on the graph P_4 (o-o-o-o) (the simple path with 4 points (vertices) and 3 lines (or edges)). See the array and triangle A198632 for the general case of the graph P_N (there N is n and the length is l=2*k).
O.g.f. for w(4,l) (with zeros for odd l): y*(d/dy)S(4,y)/S(4,y) with y=1/x and Chebyshev S-polynomials (coefficients A049310). See also A198632 for a rewritten form. One half of this o.g.f. for x -> sqrt(x) produces the g.f. (2-3x)/(1-3x+x^2) given below. (End)
Solutions (x, y) = (a(n), a(n+1)) satisfying x^2 + y^2 = 3xy - 5. - Michel Lagneau, Feb 01 2014
Except for the first term, positive values of x (or y) satisfying x^2 - 7xy + y^2 + 45 = 0. - Colin Barker, Feb 16 2014
Except for the first term, positive values of x (or y) satisfying x^2 - 18xy + y^2 + 320 = 0. - Colin Barker, Feb 16 2014
a(n) are the numbers such that a(n)^2-2 are Lucas numbers. - Michel Lagneau, Jul 22 2014
All sequences of this form, b(n+1) = 3*b(n) - b(n-1), regardless of initial values, which includes this sequence, yield this sequence as follows: a(n) = (b(j+n) + b(j-n))/b(j), for any j, except where b(j) = 0. Also note formula below relating this a(n) to all sequences of the form G(n+1) = G(n) + G(n-1).  - Richard R. Forberg, Nov 18 2014
A non-simple continued fraction expansion for F(2n*(k+1))/F(2nk) k>=1 is a(n) + (-1)/(a(n) + (-1)/(a(n) + ... +  (-1)/a(n))) where a(n) appears exactly k times (F(n) denotes the n-th Fibonacci number). E.g., F(16)/F(12) equals 7 + (-1)/(7 + (-1)/7). Furthermore, these a(n) are exactly the positive integers k such that the non-simple infinite continued fraction k + (-1)/(k + (-1)/(k + (-1)/(k + ...))) belongs to Q(sqrt(5)). Compare to Benoit Cloitre and Thomas Baruchel's comments at A002878.  - Greg Dresden, Aug 13 2019
For n >= 1, a(n) is the number of cyclic up-down words of length 2*n over an alphabet of size 3. - Sela Fried, Apr 08 2025

			G.f. = 2 + 3*x + 7*x^2 + 18*x^3 + 47*x^4 + 123*x^5 + 322*x^6 + 843*x^7 + ... - _Michael Somos_, Aug 11 2009

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).
Richard P. Stanley, Enumerative combinatorics, Vol. 2. Volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Richard André-Jeannin, Summation of Certain Reciprocal Series Related to Fibonacci and Lucas Numbers, The Fibonacci Quarterly, Vol. 29, No. 3 (1991), pp. 200-204.
Peter Bala, Some simple continued fraction expansions for an infinite product, Part 1.
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.
Pooja Bhadouria, Deepika Jhala and Bijendra Singh, Binomial Transforms of the k-Lucas Sequences and its Properties, The Journal of Mathematics and Computer Science (JMCS), Vol. 8, No. 1 (2014), pp. 81-92; sequences B_1, T_1 and R_1.
Yurii S. Bystryk, Vitalii L. Denysenko, and Volodymyr I. Ostryk, Lune and Lens Sequences, ResearchGate preprint, 2024. See pp. 51, 56.
Noureddine Chair, Exact two-point resistance, and the simple random walk on the complete graph minus N edges, Ann. Phys., Vol. 327, No. 12 (2012), pp. 3116-3129, Eq. (18).
Tony Crilly, Double sequences of positive integers, Math. Gaz., Vol. 69 (1985), pp. 263-271.
Pedro P. B. de Oliveira, Enrico Formenti, Kévin Perrot, Sara Riva and Eurico L. P. Ruivo, Non-maximal sensitivity to synchronism in periodic elementary cellular automata: exact asymptotic measures, arXiv:2004.07128 [cs.FL], 2020.
Robert G. Donnelly, Molly W. Dunkum, Murray L. Huber and Lee Knupp, Sign-alternating Gibonacci polynomials, arXiv:2012.14993 [math.CO], 2020.
Sergio Falcon, Relationships between Some k-Fibonacci Sequences, Applied Mathematics, Vol. 5, No. 15 (2014), pp. 2226-2234.
Margherita Maria Ferrari and Norma Zagaglia Salvi, Aperiodic Compositions and Classical Integer Sequences, Journal of Integer Sequences, Vol. 20 (2017), Article 17.8.8.
Sela Fried, A formula for the number of up-down words, arXiv:2503.02005 [math.CO], 2025.
Sela Fried, Even-up words and their variants, arXiv:2505.14196 [math.CO], 2025. See p. 8.
Dale Gerdemann, Collision of Digits "Also interesting are the two bisections of the Lucas numbers A005248 (digit minimizer) and A002878 (digit maximizer). I particularly like the multiples of A005248 because I have this image of the two digits piling up on top of each other and then spreading out like waves".
André Gougenheim, About the linear sequence of integers such that each term is the sum of the two preceding Part 1 Part 2, Fib. Quart., Vol. 9, No. 3 (1971), pp. 277-295, 298.
Richard K. Guy, Letter to N. J. A. Sloane, Feb 1986.
Tanya Khovanova, Recursive Sequences.
Emrah Kılıç, Yücel Türker Ulutaş and Neşe Ömür, A Formula for the Generating Functions of Powers of Horadam's Sequence with Two Additional Parameters, J. Int. Seq., Vol. 14 (2011), Article 11.5.6, Table 2.
Wentao T. Lu and F. Y. Wu, Close-packed dimers on nonorientable surfaces, Physics Letters A, Vol. 293, No. 5-6 (2002), pp. 235-246. [From Sarah-Marie Belcastro, Jul 04 2009]
Yun-Tak Oh, Hosho Katsura, Hyun-Yong Lee and Jung Hoon Han, Proposal of a spin-one chain model with competing dimer and trimer interactions, arXiv:1709.01344 [cond-mat.str-el], 2017.
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.
Sara Riva, Factorisation of Discrete Dynamical Systems, Ph.D. Thesis, Univ. Côte d'Azur (France 2023).
Jeffrey Shallit, An interesting continued fraction, Math. Mag., Vol. 48, No. 4 (1975), pp. 207-211.
Jeffrey Shallit, An interesting continued fraction, Math. Mag., Vol. 48, No. 4 (1975), pp. 207-211. [Annotated scanned copy]
Jeffrey Shallit, Proving Properties of phi-Representations with the Walnut Theorem-Prover, arXiv:2305.02672 [math.NT], 2023.
Jeffrey Shallit and N. J. A. Sloane, Correspondence, 1975.
Paweł J. Szabłowski, On moments of Cantor and related distributions, arXiv preprint arXiv:1403.0386 [math.PR], 2014.
Glenn Tesler, Matchings in Graphs on Non-Orientable Surfaces, Journal of Combinatorial Theory, Series B, Vol. 78, No. 2 (2000), pp. 198-231.
Kai Wang, Fibonacci Numbers And Trigonometric Functions Outline, (2019).
Eric Weisstein's World of Mathematics, Phi Number System.
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 sequences related to Chebyshev polynomials.
Index entries for two-way infinite sequences.
Index entries for linear recurrences with constant coefficients, signature (3,-1).

Cf. A000032, A002878 (odd-indexed Lucas numbers), A001906 (Chebyshev S(n-1, 3)), a(n) = sqrt(4+5*A001906(n)^2), A228842.
a(n) = A005592(n)+1 = A004146(n)+2 = A065034(n)-1.
First differences of A002878. Pairwise sums of A001519. First row of array A103997.
Cf. A153415, A201157. Also Lucas(k*n): A000032 (k = 1), A014448 (k = 3), A056854 (k = 4), A001946 (k = 5), A087215 (k = 6), A087281 (k = 7), A087265 (k = 8), A087287 (k = 9), A065705 (k = 10), A089772 (k = 11), A089775 (k = 12).

a005248 n = a005248_list !! n
a005248_list = zipWith (+) (tail a001519_list) a001519_list
-- Reinhard Zumkeller, Jan 11 2012

[Lucas(2*n) : n in [0..100]]; // Vincenzo Librandi, Apr 14 2011

a:= n-> (<<2|3>>. <<3|1>, <-1|0>>^n)[1$2]: seq(a(n), n=0..30); # Alois P. Heinz, Jul 31 2008
with(combinat): seq(5*fibonacci(n)^2+2*(-1)^n, n= 0..26);

a[0] = 2; a[1] = 3; a[n_] := 3a[n - 1] - a[n - 2]; Table[ a[n], {n, 0, 27}] (* Robert G. Wilson v, Jan 30 2004 *)
Fibonacci[1 + 2n] + 1/2 (-Fibonacci[2n] + LucasL[2n]) (* Tesler. Sarah-Marie Belcastro, Jul 04 2009 *)
LinearRecurrence[{3, -1}, {2, 3}, 50] (* Sture Sjöstedt, Nov 27 2011 *)
LucasL[Range[0,60,2]] (* Harvey P. Dale, Sep 30 2014 *)

{a(n) = fibonacci(2*n + 1) + fibonacci(2*n - 1)}; /* Michael Somos, Jun 23 2002 */

{a(n) = 2 * subst( poltchebi(n), x, 3/2)}; /* Michael Somos, Jun 28 2003 */

[lucas_number2(n,3,1) for n in range(37)] # Zerinvary Lajos, Jun 25 2008

a(n) = Fibonacci(2*n-1) + Fibonacci(2*n+1).
G.f.: (2-3*x)/(1-3*x+x^2). - Simon Plouffe in his 1992 dissertation.
a(n) = S(n, 3) - S(n-2, 3) = 2*T(n, 3/2) with S(n-1, 3) = A001906(n) and S(-2, x) = -1. U(n, x)=S(n, 2*x) and T(n, x) are Chebyshev's U- and T-polynomials.
a(n) = a(k)*a(n - k) - a(n - 2k) for all k, i.e., a(n) = 2*a(n) - a(n) = 3*a(n - 1) - a(n - 2) = 7*a(n - 2) - a(n - 4) = 18*a(n - 3) - a(n - 6) = 47*a(n - 4) - a(n - 8) etc., a(2n) = a(n)^2 - 2. - Henry Bottomley, May 08 2001
a(n) = A060924(n-1, 0) = 3*A001906(n) - 2*A001906(n-1), n >= 1. - Wolfdieter Lang, Apr 26 2001
a(n) ~ phi^(2*n) where phi=(1+sqrt(5))/2. - Joe Keane (jgk(AT)jgk.org), May 15 2002
a(0)=2, a(1)=3, a(n) = 3*a(n-1) - a(n-2) = a(-n). - Michael Somos, Jun 28 2003
a(n) = phi^(2*n) + phi^(-2*n) where phi=(sqrt(5)+1)/2, the golden ratio. E.g., a(4)=47 because phi^(8) + phi^(-8) = 47. - Dennis P. Walsh, Jul 24 2003
With interpolated zeros, trace(A^n)/4, where A is the adjacency matrix of path graph P_4. Binomial transform is then A049680. - Paul Barry, Apr 24 2004
a(n) = (floor((3+sqrt(5))^n) + 1)/2^n. - Lekraj Beedassy, Oct 22 2004
a(n) = ((3-sqrt(5))^n + (3+sqrt(5))^n)/2^n (Note: substituting the number 1 for 3 in the last equation gives A000204, substituting 5 for 3 gives A020876). - Creighton Dement, Apr 19 2005
a(n) = (1/(n+1/2))*Sum_{k=0..n} B(2k)*L(2n+1-2k)*binomial(2n+1, 2k) where B(2k) is the (2k)-th Bernoulli number. - Benoit Cloitre, Nov 02 2005
a(n) = term (1,1) in the 1 X 2 matrix [2,3] . [3,1; -1,0]^n. - Alois P. Heinz, Jul 31 2008
a(n) = 2*cosh(2*n*psi), where psi=log((1+sqrt(5))/2). - Al Hakanson, Mar 21 2009
From Sarah-Marie Belcastro, Jul 04 2009: (Start)
a(n) - (a(n) - F(2n))/2 - F(2n+1) = 0. (Tesler)
Product_{r=1..n} (1 + 4*(sin((4r-1)*Pi/(4n)))^2). (Lu/Wu) (End)
a(n) = Fibonacci(2n+6) mod Fibonacci(2n+2), n > 1. - Gary Detlefs, Nov 22 2010
a(n) = 5*Fibonacci(n)^2 + 2*(-1)^n. - Gary Detlefs, Nov 22 2010
a(n) = A033888(n)/A001906(n), n > 0. - Gary Detlefs, Dec 26 2010
a(n) = 2^(2*n) * Sum_{k=1..2} (cos(k*Pi/5))^(2*n). - L. Edson Jeffery, Jan 21 2012
From Peter Bala, Jan 04 2013: (Start)
Let F(x) = Product_{n>=0} (1 + x^(4*n+1))/(1 + x^(4*n+3)). Let alpha = 1/2*(3 - sqrt(5)). This sequence gives the simple continued fraction expansion of 1 + F(alpha) = 2.31829 56058 81914 31334 ... = 2 + 1/(3 + 1/(7 + 1/(18 + ...))).
Also F(-alpha) = 0.64985 97768 07374 32950 has the continued fraction representation 1 - 1/(3 - 1/(7 - 1/(18 - ...))) and the simple continued fraction expansion 1/(1 + 1/((3-2) + 1/(1 + 1/((7-2) + 1/(1 + 1/((18-2) + 1/(1 + ...))))))).
F(alpha)*F(-alpha) has the simple continued fraction expansion 1/(1 + 1/((3^2-4) + 1/(1 + 1/((7^2-4) + 1/(1 + 1/((18^2-4) + 1/(1 + ...))))))).
Added Oct 13 2019: 1/2 + 1/2*F(alpha)/F(-alpha) = 1.5142923542... has the simple continued fraction expansion 1 + 1/((3 - 2) + 1/(1 + 1/((18 - 2) + 1/(1 + 1/(123 - 2) + 1/(1 + ...))))). (End)
G.f.: (W(0)+6)/(5*x), where W(k) = 5*x*k + x - 6 + 6*x*(5*k-9)/W(k+1) (continued fraction). - Sergei N. Gladkovskii, Aug 19 2013
Sum_{n >= 1} 1/( a(n) - 5/a(n) ) = 1. Compare with A001906, A002878 and A023039. - Peter Bala, Nov 29 2013
0 = a(n) * a(n+2) - a(n+1)^2 - 5 for all n in Z. - Michael Somos, Aug 24 2014
a(n) = (G(j+2n) + G(j-2n))/G(j), for n >= 0 and any j, positive or negative, except where G(j) = 0, and for any sequence of the form G(n+1) = G(n) + G(n-1) with any initial values for G(0), G(1), including non-integer values. G(n) includes Lucas, Fibonacci. Compare with A081067 for odd number offsets from j. - Richard R. Forberg, Nov 16 2014
a(n) = [x^n] ( (1 + 3*x + sqrt(1 + 6*x + 5*x^2))/2 )^n for n >= 1. - Peter Bala, Jun 23 2015
From J. M. Bergot, Oct 28 2015: (Start)
For n>0, a(n) = F(n-1) * L(n) + F(2*n+1) - (-1)^n with F(k) = A000045(k).
For n>1, a(n) = F(n+1) * L(n) + F(2*n-1) - (-1)^n.
For n>2, a(n) = 5*F(2*n-3) + 2*L(n-3) * L(n) + 8*(-1)^n. (End)
For n>1, a(n) = L(n-2)*L(n+2) -7*(-1)^n. - J. M. Bergot, Feb 10 2016
a(n) = 6*F(n-1)*L(n-1) - F(2*n-6) with F(n)=A000045(n) and L(n)=A000032(n). - J. M. Bergot, Apr 21 2017
a(n) = F(2*n) + 2*F(n-1)*L(n) with F(n)=A000045(n) and L(n)=A000032(n). - J. M. Bergot, May 01 2017
E.g.f.: exp(4*x/(1+sqrt(5))^2) + exp((1/4)*(1+sqrt(5))^2*x). - Stefano Spezia, Aug 13 2019
From Peter Bala, Oct 14 2019: (Start)
a(n) = F(2*n+2) - F(2*n-2) = A001906(n+1) - A001906(n-1).
a(n) = trace(M^n), where M is the 2 X 2 matrix [0, 1; 1, 1]^2 = [1, 1; 1, 2].
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).
Sum_{n >= 1} (-1)^(n+1)/( a(n) + 1/a(n) ) = 1/5.
Sum_{n >= 1} (-1)^(n+1)/( a(n) + 3/(a(n) + 2/(a(n))) ) = 1/6.
Sum_{n >= 1} (-1)^(n+1)/( a(n) + 9/(a(n) + 4/(a(n) + 1/(a(n)))) ) = 1/9.
x*exp(Sum_{n >= 1} a(n)*x^/n) = x + 3*x^2 + 8*x^3 + 21*x^4 + ... is the o.g.f. for A001906. (End)
a(n) = n + 2 + Sum_{k=1..n-1} k*a(n-k). - Yu Xiao, May 30 2020
Sum_{n>=1} 1/a(n) = A153415. - Amiram Eldar, Nov 11 2020
Sum_{n>=0} 1/(a(n) + 3) = (2*sqrt(5) + 1)/10 (André-Jeannin, 1991). - Amiram Eldar, Jan 23 2022
a(n) = 2*cosh(2*n*arccsch(2)) = 2*cosh(2*n*asinh(1/2)). - Peter Luschny, May 25 2022
a(n) = (5/2)*(Sum_{k=-n..n} binomial(2*n, n+5*k)) - (1/2)*4^n. - Greg Dresden, Jan 05 2023
a(n) = Sum_{k>=0} Lucas(2*n*k)/(Lucas(2*n)^(k+1)). - Diego Rattaggi, Jan 12 2025

Additional comments from Michael Somos, Jun 23 2001

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)

A002530 a(n) = 4*a(n-2) - a(n-4) for n > 1, a(n) = n for n = 0, 1.

Original entry on oeis.org

0, 1, 1, 3, 4, 11, 15, 41, 56, 153, 209, 571, 780, 2131, 2911, 7953, 10864, 29681, 40545, 110771, 151316, 413403, 564719, 1542841, 2107560, 5757961, 7865521, 21489003, 29354524, 80198051, 109552575, 299303201, 408855776, 1117014753, 1525870529, 4168755811

Offset: 0

N. J. A. Sloane

Denominators of continued fraction convergents to sqrt(3), for n >= 1.
Also denominators of continued fraction convergents to sqrt(3) - 1. See A048788 for numerators. - N. J. A. Sloane, Dec 17 2007. Convergents are 1, 2/3, 3/4, 8/11, 11/15, 30/41, 41/56, 112/153, ...
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 following sequence 1/1, 2/1, 5/3, 7/4, 19/11, ... converging to 3^(1/2). Sequence contains the denominators. The same mapping for N, i.e., f(a/b) = (a + Nb)/(a + b) gives fractions converging to N^(1/2). - Amarnath Murthy, Mar 22 2003
Sqrt(3) = 2/2 + 2/3 + 2/(3*11) + 2/(11*41) + 2/(41*153) + 2/(153*571), ...; the sum of the first 6 terms of this series = 1.7320490367..., while sqrt(3) = 1.7320508075... - Gary W. Adamson, Dec 15 2007
From Clark Kimberling, Aug 27 2008: (Start)
  Related convergents (numerator/denominator):
  lower principal convergents: A001834/A001835
  upper principal convergents: A001075/A001353
  intermediate convergents: A005320/A001075
  principal and intermediate convergents: A143642/A140827
  lower principal and intermediate convergents: A143643/A005246. (End)
Row sums of triangle A152063 = (1, 3, 4, 11, ...). - Gary W. Adamson, Nov 26 2008
From Alois P. Heinz, Apr 13 2011: (Start)
Also number of domino tilings of the 3 X (n-1) rectangle with upper left corner removed iff n is even.  For n=4 the 4 domino tilings of the 3 X 3 rectangle with upper left corner removed are:
   . ._. . ._. . ._. . ._.
   .|__| .|__| .| | | .|___|
   | |_| | | | | | ||| |_| |
   ||__| |||_| ||__| |_|_|  (End)
This is the sequence of Lehmer numbers u_n(sqrt(R),Q) with the parameters R = 2 and Q = -1. It is a strong divisibility sequence, that is, gcd(a(n),a(m)) = a(gcd(n,m)) for all natural numbers n and m. - Peter Bala, Apr 18 2014
2^(-floor(n/2))*(1 + sqrt(3))^n = A002531(n) + a(n)*sqrt(3); integers in the real quadratic number field Q(sqrt(3)). - Wolfdieter Lang, Feb 11 2018
Let T(n) = 2^(n mod 2), U(n) = a(n), V(n) = A002531(n), x(n) = V(n)/U(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) = (3 + x(n)*x(m))/(x(n) + x(m)). - Michael Somos, Nov 29 2022

			Convergents to sqrt(3) 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 for n >= 1.
1 + 1/(1 + 1/(2 + 1/(1 + 1/2))) = 19/11 so a(5) = 11.
G.f. = x + x^2 + 3*x^3 + 4*x^4 + 11*x^5 + 15*x^6 + 41*x^7 + ... - _Michael Somos_, Mar 18 2022

Serge Lang, Introduction to Diophantine Approximations, Addison-Wesley, New York, 1966.
Russell Lyons, A bird's-eye view of uniform spanning trees and forests, in Microsurveys in Discrete Probability, AMS, 1998.
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. 2nd ed., Wiley, NY, 1966, p. 181.
Murat Sahin and Elif Tan, Conditional (strong) divisibility sequences, Fib. Q., 56 (No. 1, 2018), 18-31.
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
Peter Bala, Notes on 2-periodic continued fractions and Lehmer sequences
Paul Barry, Symmetric Third-Order Recurring Sequences, Chebyshev Polynomials, and Riordan Arrays, JIS 12 (2009) 09.8.6.
Mario Catalani, Sequences related to convergents to square root of rationals, arXiv:math/0305270 [math.NT], 2003.
Marcia Edson, Scott Lewis and Omer Yayenie, The k-periodic Fibonacci sequence and an extended Binet's formula, INTEGERS 11 (2011) #A32.
Aviezri S. Fraenkel, Jonathan Levitt, and Michael Shimshoni, Characterization of the set of values f(n)=[n alpha], n=1,2,..., Discrete Math. 2 (1972), no.4, 335-345.
Clark Kimberling, Best lower and upper approximates to irrational numbers, Elemente der Mathematik, 52 (1997) 122-126.
Clark Kimberling, Matrix Transformations of Integer Sequences, J. Integer Seqs., Vol. 6, 2003.
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]
Russell Walsmith, CL-Chemy Transforms Fibonacci-Type Sequences to Arrays
E. W. Weisstein, MathWorld: Lehmer Number
Index entries for "core" sequences
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (0,4,0,-1).
Index entries for sequences related to Chebyshev polynomials.

Cf. A002531 (numerators of convergents to sqrt(3)), A048788, A003297.
Bisections: A001353 and A001835.
Cf. A152063.
Cf. A108412, A049310.
Analog for sqrt(m): A000129 (m=2), A001076 (m=5), A041007 (m=6), A041009 (m=7), A041011 (m=8), A005668 (m=10), A041015 (m=11), A041017 (m=12), ..., A042935 (m=999), A042937 (m=1000).

I:=[0,1,1,3]; [n le 4 select I[n] else 4*Self(n-2) - Self(n-4): n in [1..50]]; // G. C. Greubel, Feb 25 2019

a := proc(n) option remember; if n=0 then 0 elif n=1 then 1 elif n=2 then 1 elif n=3 then 3 else 4*a(n-2)-a(n-4) fi end; [ seq(a(i),i=0..50) ];
A002530:=-(-1-z+z**2)/(1-4*z**2+z**4); # conjectured (correctly) by Simon Plouffe in his 1992 dissertation

Join[{0},Table[Denominator[FromContinuedFraction[ContinuedFraction[Sqrt[3],n]]], {n,1,50}]] (* Stefan Steinerberger, Apr 01 2006 *)
Join[{0},Denominator[Convergents[Sqrt[3],50]]] (* or *) LinearRecurrence[ {0,4,0,-1},{0,1,1,3},50] (* Harvey P. Dale, Jan 29 2013 *)
a[ n_] := If[n<0, -(-1)^n, 1] SeriesCoefficient[ x*(1+x-x^2)/(1-4*x^2+x^4), {x, 0, Abs@n}]; (* Michael Somos, Apr 18 2019 *)
a[ n_] := ChebyshevU[n-1, Sqrt[-1/2]]*Sqrt[2]^(Mod[n, 2]-1)/I^(n-1) //Simplify; (* Michael Somos, Nov 29 2022 *)

{a(n) = if( n<0, -(-1)^n * a(-n), contfracpnqn(vector(n, i, 1 + (i>1) * (i%2)))[2, 1])}; /* Michael Somos, Jun 05 2003 */

{ for (n=0, 50, a=contfracpnqn(vector(n, i, 1+(i>1)*(i%2)))[2, 1]; write("b002530.txt", n, " ", a); ); } \\ Harry J. Smith, Jun 01 2009

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

from functools import cache
@cache
def a(n): return [0, 1, 1, 3][n] if n < 4 else 4*a(n-2) - a(n-4)
print([a(n) for n in range(36)]) # Michael S. Branicky, Nov 13 2022

(x*(1+x-x^2)/(1-4*x^2+x^4)).series(x, 50).coefficients(x, sparse=False) # G. C. Greubel, Feb 25 2019

G.f.: x*(1 + x - x^2)/(1 - 4*x^2 + x^4).
a(n) = 4*a(n-2) - a(n-4). [Corrected by László Szalay, Feb 21 2014]
a(n) = -(-1)^n * a(-n) for all n in Z, would satisfy the same recurrence relation. - Michael Somos, Jun 05 2003
a(2*n) = a(2*n-1) + a(2*n-2), a(2*n+1) = 2*a(2*n) + a(2*n-1).
From Benoit Cloitre, Dec 15 2002: (Start)
a(2*n) = ((2 + sqrt(3))^n - (2 - sqrt(3))^n)/(2*sqrt(3)).
a(2*n) = A001353(n).
a(2*n-1) = ceiling((1 + 1/sqrt(3))/2*(2 + sqrt(3))^n) = ((3 + sqrt(3))^(2*n - 1) + (3 - sqrt(3))^(2*n - 1))/6^n.
a(2*n-1) = A001835(n). (End)
a(n+1) = Sum_{k=0..floor(n/2)} binomial(n - k, k) * 2^floor((n - 2*k)/2). - Paul Barry, Jul 13 2004
a(n) = Sum_{k=0..floor(n/2)} binomial(floor(n/2) + k, floor((n - 1)/2 - k))*2^k. - Paul Barry, Jun 22 2005
G.f.: (sqrt(6) + sqrt(3))/12*Q(0), where Q(k) = 1 - a/(1 + 1/(b^(2*k) - 1 - b^(2*k)/(c + 2*a*x/(2*x - g*m^(2*k)/(1 + a/(1 - 1/(b^(2*k + 1) + 1 - b^(2*k + 1)/(h - 2*a*x/(2*x + g*m^(2*k + 1)/Q(k + 1)))))))))). - Sergei N. Gladkovskii, Jun 21 2012
a(n) = (alpha^n - beta^n)/(alpha - beta) for n odd, and a(n) = (alpha^n - beta^n)/(alpha^2 - beta^2) for n even, where alpha = 1/2*(sqrt(2) + sqrt(6)) and beta = (1/2)*(sqrt(2) - sqrt(6)). Cf. A108412. - Peter Bala, Apr 18 2014
a(n) = (-sqrt(2)*i)^n*S(n, sqrt(2)*i)*2^(-floor(n/2)) = A002605(n)*2^(-floor(n/2)), n >= 0, with i = sqrt(-1) and S the Chebyshev polynomials (A049310). - Wolfdieter Lang, Feb 10 2018
a(n+1)*a(n+2) - a(n+3)*a(n) = (-1)^n, n >= 0. - Kai Wang, Feb 06 2020
E.g.f.: sinh(sqrt(3/2)*x)*(sinh(x/sqrt(2)) + sqrt(2)*cosh(x/sqrt(2)))/sqrt(3). - Stefano Spezia, Feb 07 2020
a(n) = ((1 + sqrt(3))^n - (1 - sqrt(3))^n)/(2*2^floor(n/2))/sqrt(3) = A002605(n)/2^floor(n/2). - Robert FERREOL, Apr 13 2023

Definition edited by M. F. Hasler, Nov 04 2019

A101265 a(1) = 1, a(2) = 2, a(3) = 6; a(n) = 5a(n-1) - 5a(n-2) + a(n-3) for n > 3.

Original entry on oeis.org

1, 2, 6, 21, 77, 286, 1066, 3977, 14841, 55386, 206702, 771421, 2878981, 10744502, 40099026, 149651601, 558507377, 2084377906, 7779004246, 29031639077, 108347552061, 404358569166, 1509086724602, 5631988329241, 21018866592361, 78443478040202, 292755045568446

Offset: 1

Lambert Klasen (lambert.klasen(AT)gmx.net) and Gary W. Adamson, Jan 25 2005

Let M = [ 1, 1, 0; 1, 3, 1; 0, 1, 1 ]; then [1,0,0]*M^n = [a(n), A001353(n), A061278(n-1)] for n > 1. Further, A001353 consists of the first differences of {a(n)}, and since a(n) = A061278(n) + 1, A001353 is also the first differences of A061278. Let v(n) = [1,0,0]*M^n; then, for n >= 0, sum(v_i(n)) = A001075(n) and v_1(n) + v_3(n) = A001835(n). The characteristic polynomial of M is x^3 - 5x^2 + 5x - 1. a(n)/a(n-1) tends to 2 + sqrt(3) = 3.732.... (see A019973) (a root of the polynomial and an eigenvalue of the matrix).
Numbers k such that the RootMeanSquare([1..6*k-5]) is an integer. - Ctibor O. Zizka, Dec 17 2008
Place a(n) blue and b(n) red balls in an urn. Draw 3 balls without replacement. Then Probability(3 red balls) = Probability(1 red and 2 blue balls); binomial(b(n),3) = binomial(b(n),1)*binomial(a(n),2); b(n) = A179167(n). - Paul Weisenhorn, Jul 01 2010
Conjecture: consecutive terms of this sequence and consecutive terms of A032908 provide all the positive integer solutions of (a+b)*(a+b+1) == 0 (mod (a*b)). - Robert Israel, Aug 26 2015
Conjecture is true: see StackExchange link. - Robert Israel, Sep 06 2015
Values of a unitary Y-frieze pattern associated to the linearly oriented quiver K3 (i.e., the quiver whose underlying graph is the complete graph on the vertices {1,2,3}, oriented such that i -> j whenever i < j). - Antoine de Saint Germain, Dec 30 2024

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
R. Israel, W. Jagy et al., Diophantine equation (x+y)(x+y+1)-kxy=0, Math StackExchange, Sep 1 2015.
Giovanni Lucca, Circle Chains Inscribed in Symmetrical Lenses and Integer Sequences, Forum Geometricorum, Volume 16 (2016) 419-427.
Index entries for linear recurrences with constant coefficients, signature (5,-5,1).

Cf. A001075, A001353, A001835, A005246, A019973, A032908, A061278, A211955.

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

a101265 n = a101265_list !! (n-1)
a101265_list = 1 : 2 : 6 : zipWith (+) a101265_list
    (map (* 5) $ tail $ zipWith (-) (tail a101265_list) a101265_list)
-- Reinhard Zumkeller, May 18 2014

I:=[1,2,6]; [n le 3 select I[n] else 5*Self(n-1) - 5*Self(n-2) + Self(n-3): n in [1..30]]; // Vincenzo Librandi, Sep 07 2015

r:=sqrt(3): for n from 1 to 100 do a[n]:=(6+(3+r)*(2+r)^(n-1)+(3-r)*(2-r)^(n-1))/12: end do: # Paul Weisenhorn, Jul 01 2010
r:=sqrt(3): a[n]:=round((6+(3+r)*(2+r)^(n-1))/12): # Paul Weisenhorn, Jul 01 2010
f:= proc(n)
  option remember; local x;
  x:= procname(n-1);
  2*x + (sqrt(12*x^2 - 12*x + 1) - 1)/2
end proc:
f(1):= 1:
map(f, [$1..30]); # Robert Israel, Aug 26 2015
seq( simplify((ChebyshevU(n,2) - Chebyshev(n-1,2) + 1)/2), n=0..20); # G. C. Greubel, Dec 23 2019

LinearRecurrence[{5,-5,1},{1,2,6},25] (* Ray Chandler, Jan 27 2014 *)
CoefficientList[Series[(1-3x+x^2)/((1-x)(1-4x+x^2)), {x, 0, 33}], x] (* Vincenzo Librandi, Sep 07 2015 *)
Table[(ChebyshevU[n, 2] - ChebyshevU[n-1, 2] + 1)/2, {n, 0, 20}] (* G. C. Greubel, Dec 23 2019 *)

M = [ 1, 1, 0; 1, 3, 1; 0, 1, 1]; for(i=1,30,print1(([1,0,0]*M^i)[1],","))

{a(n)=polcoeff(x*(1-3*x+x^2)/((1-x)*(1-4*x+x^2)+x*O(x^n)),n)}

{a(n)=if(n==0,1,if(n==1,1,a(n-1)*(a(n-1)+1)/a(n-2)))} /* Paul D. Hanna, Apr 08 2012 */

vector(21, n, (polchebyshev(n, 2, 2) - polchebyshev(n-1, 2, 2) + 1)/2 ) \\ G. C. Greubel, Dec 23 2019

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

a(n) = A005246(n)*A005246(n+1). a(n+1) = a(n)*(a(n)+1)/a(n-1). - Franklin T. Adams-Watters, Apr 24 2006
a(n) = (A001835(n) + 1) / 2. - Ralf Stephan, May 16 2007
O.g.f.: x*(1-3*x+x^2)/((1-x)*(1-4*x+x^2)). - R. J. Mathar, Aug 22 2008
a(n) = 1 + A061278(n). - Ctibor O. Zizka, Dec 17 2008
a(n) = 4*a(n-1) - a(n-2) - 1. - N. Sato, Jan 21 2010
a(n) = (6+(3+r)*(2+r)^(n-1) + (3-r)*(2-r)^(n-1))/12; r=sqrt(3). - Paul Weisenhorn, Jul 01 2010
a(n+1) = a(n) * (a(n) + 1) / a(n-1) for n>1 with a(0)=1, a(1)=1. - Paul D. Hanna, Apr 08 2012
From Peter Bala, May 01 2012: (Start)
a(n+1) = 1 + Sum {k = 1..n} 2^(k-1)*binomial(n+k,2*k).
Row sums of A211955.
a(n) = T(n,u)*T(n+1,u)/u with u = sqrt(3) and T(n,x) denotes the Chebyshev polynomial of the first kind.
Sum_{n >= 0} 1/a(n) = sqrt(3). In fact, 3 - (Sum_{n = 0..2*N} 1/a(n))^2 = 2/(A001835(N+1))^2 and 3 - (Sum_{n = 0..2*N+1} 1/a(n))^2 = 3/(A001075(N+1))^2. (End)
From Robert Israel, Aug 26 2015: (Start)
(a(n) + a(n+1))*(a(n) + a(n+1) + 1) = 6 * a(n) * a(n+1).
a(n+1) = 2*a(n) + (sqrt(12*a(n)^2 - 12*a(n) + 1) - 1)/2. (End)
a(n) = (ChebyshevU(n, 2) - ChebyshevU(n-1, 2) + 1)/2 = (ChebyshevT(n, 2) + ChebyshevU(n, 2) + 2)/4. - G. C. Greubel, Dec 23 2019
a(n) = (1+a(n-1))*(1+a(n-2))/a(n-3) for n > 3. - Antoine de Saint Germain, Dec 30 2024

a(26)-a(27) from Vincenzo Librandi, Sep 07 2015

cp's OEIS Frontend

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

A005248 Bisection of Lucas numbers: a(n) = L(2*n) = A000032(2*n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

Sage

Sage

Formula

A002530 a(n) = 4*a(n-2) - a(n-4) for n > 1, a(n) = n for n = 0, 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Sage

A005248 Bisection of Lucas numbers: a(n) = L(2n) = A000032(2n).

A101265 a(1) = 1, a(2) = 2, a(3) = 6; a(n) = 5a(n-1) - 5a(n-2) + a(n-3) for n > 3.

A082630 Limit of the sequence obtained from S(0) = (1,1) and, for n > 0, S(n) = I(S(n-1)), where I consists of inserting, for i = 1, 2, 3..., the term a(i) + a(i+1) between any two terms for which 7a(i+1) <= 11a(i).

A101879 a(0) = 1, a(1) = 1, a(2) = 2; for n > 2, a(n) = 5a(n-1) - 5a(n-2) + a(n-3).

A051786 Propp's cubic recurrence: a(0)=a(1)=a(2)=a(3)=1; for n>3, a(n)=(1+a(n-1)a(n-2)a(n-3))/a(n-4).