cp's OEIS Frontend

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

%I A002605 #285 Jul 20 2025 15:29:07
%S A002605 0,1,2,6,16,44,120,328,896,2448,6688,18272,49920,136384,372608,
%T A002605 1017984,2781184,7598336,20759040,56714752,154947584,423324672,
%U A002605 1156544512,3159738368,8632565760,23584608256,64434348032,176037912576,480944521216,1313964867584
%N A002605 a(n) = 2*(a(n-1) + a(n-2)), a(0) = 0, a(1) = 1.
%C A002605 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
%C A002605 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
%C A002605 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
%C A002605 The Hankel transform of this sequence is [1, 2, 0, 0, 0, 0, 0, 0, 0, ...]. - _Philippe Deléham_, Nov 21 2007
%C A002605 [1, 3; 1, 1]^n *[1, 0] = [A026150(n), a(n)]. - _Gary W. Adamson_, Mar 21 2008
%C A002605 (1 + sqrt(3))^n = A026150(n) + a(n)*sqrt(3). - _Gary W. Adamson_, Mar 21 2008
%C A002605 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
%C A002605 Starting with offset 1 = INVERT transform of the Jacobsthal sequence, A001045: (1, 1, 3, 5, 11, 21, ...). - _Gary W. Adamson_, May 12 2009
%C A002605 Starting with "1" = INVERTi transform of A007482: (1, 3, 11, 39, 139, ...). - _Gary W. Adamson_, Aug 06 2010
%C A002605 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
%C A002605 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
%C A002605 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
%C A002605 Number of binary strings of length 2*n - 2 in the regular language (00+11+0101+1010)*. - _Jeffrey Shallit_, Dec 14 2015
%C A002605 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
%C A002605 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
%C A002605 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
%C A002605 (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
%C A002605 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
%C A002605 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
%D A002605 John Derbyshire, Prime Obsession, Joseph Henry Press, April 2004, p. 16.
%H A002605 Vincenzo Librandi, <a href="/A002605/b002605.txt">Table of n, a(n) for n = 0..500</a>
%H A002605 A. Abdurrahman, <a href="https://arxiv.org/abs/1909.10889">CM Method and Expansion of Numbers</a>, arXiv:1909.10889 [math.NT], 2019.
%H A002605 Jean-Luc Baril, Nathanaël Hassler, Sergey Kirgizov, and José L. Ramírez, <a href="https://arxiv.org/abs/2402.04851">Grand zigzag knight's paths</a>, arXiv:2402.04851 [math.CO], 2024.
%H A002605 Paul Barry, <a href="https://arxiv.org/abs/2104.05593">On the Gap-sum and Gap-product Sequences of Integer Sequences</a>, arXiv:2104.05593 [math.CO], 2021.
%H A002605 Paul Barry, <a href="https://arxiv.org/abs/2504.09719">Notes on Riordan arrays and lattice paths</a>, arXiv:2504.09719 [math.CO], 2025. See pp. 8, 29.
%H A002605 Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Szczyrba/sz3.html">Analytic Representations of the n-anacci Constants and Generalizations Thereof</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
%H A002605 M. Couceiro, J. Devillet, and J.-L. Marichal, <a href="http://arxiv.org/abs/1709.09162">Quasitrivial semigroups: characterizations and enumerations</a>, arXiv:1709.09162 [math.RA], 2017.
%H A002605 M. Diepenbroek, M. Maus, and A. Stoll, <a href="http://www.valpo.edu/mathematics-statistics/files/2014/09/Pudwell2015.pdf">Pattern Avoidance in Reverse Double Lists</a>, Preprint 2015. See Table 3.
%H A002605 Sergio Falcón, <a href="https://www.rgnpublications.com/journals/index.php/cma/article/viewFile/1221/950">Binomial Transform of the Generalized k-Fibonacci Numbers</a>, Communications in Mathematics and Applications (2019) Vol. 10, No. 3, 643-651.
%H A002605 Alice L. L. Gao and Sergey Kitaev, <a href="https://arxiv.org/abs/1903.08946">On partially ordered patterns of length 4 and 5 in permutations</a>, arXiv:1903.08946 [math.CO], 2019.
%H A002605 Alice L. L. Gao and Sergey Kitaev, <a href="https://doi.org/10.37236/8605">On partially ordered patterns of length 4 and 5 in permutations</a>, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
%H A002605 Dale Gerdemann <a href="http://www.youtube.com/watch?v=7fUghbI1y3o">Bird Flock</a>, Youtube video, 2011.
%H A002605 A. F. Horadam, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/5-5/horadam.pdf">Special properties of the sequence W_n(a,b; p,q)</a>, Fib. Quart., 5.5 (1967), 424-434. Case n->n+1, a=0,b=1; p=q=2.
%H A002605 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=476">Encyclopedia of Combinatorial Structures 476</a>
%H A002605 D. Jhala, G. P. S. Rathore, and K. Sisodiya, <a href="http://dx.doi.org/10.12691/tjant-2-4-3">Some Properties of k-Jacobsthal Numbers with Arithmetic Indexes</a>, Turkish Journal of Analysis and Number Theory, 2014, Vol. 2, No. 4, 119-124.
%H A002605 Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>
%H A002605 Wolfdieter Lang, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/38-5/lang.pdf">On polynomials related to powers of the generating function of Catalan's numbers</a>, Fib. Quart. 38,5 (2000) 408-419; Eqs. (39), (41) and (45), lhs, m=2.
%H A002605 D. H. Lehmer, <a href="https://doi.org/10.1112/jlms/s1-10.2.162">On Lucas's test for the primality of Mersenne's numbers</a>, Journal of the London Mathematical Society 1.3 (1935): 162-165. See U_n.
%H A002605 Toufik Mansour and Mark Shattuck, <a href="https://doi.org/10.47443/dml.2025.060">Pattern avoidance in flattened derangements</a>, Disc. Math. Lett. (2025) Vol. 15, 67-74. See p. 74.
%H A002605 Yassine Otmani, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL28/Otmani/otmani10.html">The 2-Pascal Triangle and a Related Riordan Array</a>, J. Int. Seq. (2025) Vol. 28, Issue 3, Art. No. 25.3.5. See p. 12.
%H A002605 Alan Prince, <a href="http://roa.rutgers.edu/article/view/1127">Counting parses</a>, Rutgers Optimality Archive, 2010.
%H A002605 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,2).
%H A002605 <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>
%H A002605 <a href="/index/Lu#Lucas">Index entries for Lucas sequences.</a>
%F A002605 a(n) = (-I*sqrt(2))^(n-1)*U(n-1, I/sqrt(2)) where U(n, x) is the Chebyshev U-polynomial. - _Wolfdieter Lang_
%F A002605 G.f.: x/(1 - 2*x - 2*x^2).
%F A002605 From _Paul Barry_, Sep 17 2003: (Start)
%F A002605 E.g.f.: x*exp(x)*(sinh(sqrt(3)*x)/sqrt(3) + cosh(sqrt(3)*x)).
%F A002605 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.
%F A002605 Binomial transform of 1, 1, 3, 3, 9, 9, ... Binomial transform is A079935. (End)
%F A002605 a(n) = Sum_{k=0..floor(n/2)} binomial(n - k, k)*2^(n - k). - _Paul Barry_, Jul 13 2004
%F A002605 a(n) = A080040(n) - A028860(n+1). - _Creighton Dement_, Jan 19 2005
%F A002605 a(n) = Sum_{k=0..n} A112899(n,k). - _Philippe Deléham_, Nov 21 2007
%F A002605 a(n) = Sum_{k=0..n} A063967(n,k). - _Philippe Deléham_, Nov 03 2006
%F A002605 a(n) = ((1 + sqrt(3))^n - (1 - sqrt(3))^n)/(2*sqrt(3)).
%F A002605 a(n) = Sum_{k=0..n} binomial(n, 2*k + 1) * 3^k.
%F A002605 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
%F A002605 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
%F A002605 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
%F A002605 Antidiagonals sums of A081577. - _J. M. Bergot_, Dec 15 2012
%F A002605 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
%F A002605 a(n) = 2^(n - 1)*hypergeom([1 - n/2, (1 - n)/2], [1 - n], -2) for n >= 3. - _Peter Luschny_, Dec 16 2015
%F A002605 Sum_{k=0..n} a(k)*2^(n-k) = a(n+2)/2 - 2^n. - _Greg Dresden_, Feb 11 2022
%F A002605 a(n) = 2^floor(n/2) * A002530(n). - _Gregory L. Simay_, Sep 22 2022
%F A002605 From _Peter Bala_, May 08 2024: (Start)
%F A002605 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) )
%F A002605 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)
%F A002605 a(n) = A127864(n-1) + A127864(n-2). - _Greg Dresden_ and Yilin Zhu, Jul 17 2025
%p A002605 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
%p A002605 a := n -> `if`(n<3, n, 2^(n-1)*hypergeom([1-n/2, (1-n)/2], [1-n], -2));
%p A002605 seq(simplify(a(n)), n=0..29); # _Peter Luschny_, Dec 16 2015
%t A002605 Expand[Table[((1 + Sqrt[3])^n - (1 - Sqrt[3])^n)/(2Sqrt[3]), {n, 0, 30}]] (* _Artur Jasinski_, Dec 10 2006 *)
%t A002605 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 *)
%t A002605 LinearRecurrence[{2, 2}, {0, 1}, 30] (* _Robert G. Wilson v_, Apr 13 2013 *)
%t A002605 Round@Table[Fibonacci[n, Sqrt[2]] 2^((n - 1)/2), {n, 0, 20}] (* _Vladimir Reshetnikov_, Oct 15 2016 *)
%t A002605 nxt[{a_,b_}]:={b,2(a+b)}; NestList[nxt,{0,1},30][[All,1]] (* _Harvey P. Dale_, Sep 17 2022 *)
%o A002605 (Sage) [lucas_number1(n,2,-2) for n in range(0, 30)] # _Zerinvary Lajos_, Apr 22 2009
%o A002605 (Sage)
%o A002605 a = BinaryRecurrenceSequence(2,2)
%o A002605 print([a(n) for n in (0..29)])  # _Peter Luschny_, Aug 29 2016
%o A002605 (PARI) Vec(x/(1-2*x-2*x^2)+O(x^99)) \\ _Charles R Greathouse IV_, Jun 10 2011
%o A002605 (PARI) A002605(n)=([2,2;1,0]^n)[2,1] \\ _M. F. Hasler_, Aug 06 2018
%o A002605 (Magma) [Floor(((1 + Sqrt(3))^n - (1 - Sqrt(3))^n)/(2*Sqrt(3))): n in [0..30]]; // _Vincenzo Librandi_, Aug 18 2011
%o A002605 (Haskell)
%o A002605 a002605 n = a002605_list !! n
%o A002605 a002605_list =
%o A002605    0 : 1 : map (* 2) (zipWith (+) a002605_list (tail a002605_list))
%o A002605 -- _Reinhard Zumkeller_, Oct 15 2011
%o A002605 (Magma) [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
%Y A002605 First differences are given by A026150.
%Y A002605 a(n) = A073387(n, 0), n>=0 (first column of triangle).
%Y A002605 Equals (1/3) A083337. First differences of A077846. Pairwise sums of A028860 and abs(A077917).
%Y A002605 a(n) = A028860(n)/2 apart from the initial terms.
%Y A002605 Row sums of A081577 and row sums of triangle A156710.
%Y A002605 The following sequences (and others) belong to the same family: A001333, A000129, A026150, A046717, A015518, A084057, A063727, A002533, A002532, A083098, A083099, A083100, A015519.
%Y A002605 Cf. A080953, A052948, A080040, A028859, A030195, A106435, A108898, A125145, A265106, A265107, A265278, A270810, A293005, A293006, A293007.
%Y A002605 Cf. A175289 (Pisano periods).
%Y A002605 Cf. A002530.
%Y A002605 Cf. A127864.
%K A002605 nonn,easy
%O A002605 0,3
%A A002605 _Colin Mallows_
%E A002605 Edited by _N. J. A. Sloane_, Apr 15 2009