login
a(0) = a(1) = 1; a(n+2) = 2*a(n+1) + 2*a(n).
54

%I #152 Sep 08 2022 08:44:49

%S 1,1,4,10,28,76,208,568,1552,4240,11584,31648,86464,236224,645376,

%T 1763200,4817152,13160704,35955712,98232832,268377088,733219840,

%U 2003193856,5472827392,14952042496,40849739776

%N a(0) = a(1) = 1; a(n+2) = 2*a(n+1) + 2*a(n).

%C a(n+1)/A002605(n) converges to sqrt(3). - Mario Catalani (mario.catalani(AT)unito.it), Apr 22 2003

%C a(n+1)/a(n) converges to 1 + sqrt(3) = 2.732050807568877293.... - _Philippe Deléham_, Jul 03 2005

%C Binomial transform of expansion of cosh(sqrt(3)x) (A000244 with interpolated zeros); inverse binomial transform of A001075. - _Philippe Deléham_, Jul 04 2005

%C The same sequence may be obtained by the following process. Starting a priori with the fraction 1/1, the numerators of fractions built according to the rule: add top and bottom to get the new bottom, add top and 3 times the bottom to get the new top. The limit of the sequence of fractions is sqrt(3). - _Cino Hilliard_, Sep 25 2005

%C Inverse binomial transform of A001075: (1, 2, 7, 26, 97, 362, ...). - _Gary W. Adamson_, Nov 23 2007

%C Starting (1, 4, 10, 28, 76, ...), the sequence is the binomial transform of [1, 3, 3, 9, 9, 27, 27, 81, 81, ...], and inverse binomial transform of A001834: (1, 5, 19, 71, 265, ...). - _Gary W. Adamson_, Nov 30 2007

%C [1, 3; 1, 1]^n * [1,0] = [a(n), A002605(n)]. - _Gary W. Adamson_, Mar 21 2008

%C (1 + sqrt(3))^n = a(n) + A002605(n)*(sqrt(3)). - _Gary W. Adamson_, Mar 21 2008

%C Equals right border of triangle A143908. Also, starting (1, 4, 10, 28, ...) = row sums of triangle A143908 and INVERT transform of (1, 3, 3, 3, ...). - _Gary W. Adamson_, Sep 06 2008

%C a(n) is the number of compositions of n when there are 1 type of 1 and 3 types of other natural numbers. - _Milan Janjic_, Aug 13 2010

%C An elephant sequence, see A175655. For the central square four A[5] vectors, with decimal values 85, 277, 337 and 340, lead to this sequence (without the first leading 1). For the corner squares these vectors lead to the companion sequence A002605 (without the leading 0). - _Johannes W. Meijer_, Aug 15 2010

%C Pisano period lengths: 1, 1, 1, 1, 24, 1, 48, 1, 3, 24, 10, 1, 12, 48, 24, 1,144, 3,180, 24, ... - _R. J. Mathar_, Aug 10 2012

%C (1 + sqrt(3))^n = a(n) + A002605(n)*sqrt(3), for n >= 0; integers in the real quadratic number field Q(sqrt(3)). - _Wolfdieter Lang_, Feb 10 2018

%C a(n) is also the number of solutions for cyclic three-dimensional stable matching instances with master preference lists of size n (Escamocher and O'Sullivan 2018). - _Guillaume Escamocher_, Jun 15 2018

%C Starting from a(1), first differences of A005665. - _Ivan N. Ianakiev_, Nov 22 2019

%C Number of 3-permutations of n elements avoiding the patterns 231, 312. See Bonichon and Sun. - _Michel Marcus_, Aug 19 2022

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

%H Reinhard Zumkeller, <a href="/A026150/b026150.txt">Table of n, a(n) for n = 0..1000</a>

%H Martin Burtscher, Igor Szczyrba, Rafał Szczyrba, <a href="http://www.emis.de/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 C. Banderier and D. Merlini, <a href="http://lipn.univ-paris13.fr/~banderier/Papers/fpsac02.pdf">Lattice paths with an infinite set of jumps</a>, FPSAC02, Melbourne, 2002.

%H C. Bautista-Ramos and C. Guillen-Galvan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Bautista/bautista4.html">Fibonacci numbers of generalized Zykov sums</a>, J. Integer Seq., 15 (2012), Article 12.7.8.

%H Nicolas Bonichon and Pierre-Jean Morel, <a href="https://arxiv.org/abs/2202.12677">Baxter d-permutations and other pattern avoiding classes</a>, arXiv:2202.12677 [math.CO], 2022.

%H A. Burstein, S. Kitaev and T. Mansour, <a href="https://arxiv.org/abs/math/0310379">Independent sets in certain classes of (almost) regular graphs</a>, arXiv:math/0310379 [math.CO], 2003.

%H Guillaume Escamocher and Barry O'Sullivan, <a href="https://cora.ucc.ie/handle/10468/6633">Three-Dimensional Matching Instances Are Rich in Stable Matchings</a>, CPAIOR 2018, pages 182-197.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=1052">Encyclopedia of Combinatorial Structures 1052</a>

%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>

%H Emanuele Munarini, <a href="https://doi.org/10.1515/puma-2015-0028">A generalization of André-Jeannin's symmetric identity</a>, Pure Mathematics and Applications (2018) Vol. 27, No. 1, 98-118.

%H Nathan Sun, <a href="https://arxiv.org/abs/2208.08506">On d-permutations and Pattern Avoidance Classes</a>, arXiv:2208.08506 [math.CO], 2022.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,2).

%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials</a>.

%F a(n) = (1/2)*((1 + sqrt(3))^n + (1 - sqrt(3))^n). - _Benoit Cloitre_, Oct 28 2002

%F G.f.: (1 - x)/(1 - 2*x - 2*x^2).

%F a(n) = a(n-1) + A083337(n-1). A083337(n)/a(n) converges to sqrt(3). - Mario Catalani (mario.catalani(AT)unito.it), Apr 29 2003

%F From _Paul Barry_, May 15 2003: (Start)

%F a(n) = Sum_{k=0..floor(n/2)} C(n, 2k)*3^k;

%F E.g.f.: exp(x)*cosh(sqrt(3)x). (End)

%F a(n) = Sum_{k=0..n} A098158(n,k)*3^(n - k). - _Philippe Deléham_, Dec 26 2007

%F a(n) = upper left and lower right terms of [1, 1; 3, 1]^n. (1 + sqrt(3))^n = a(n) + A083337(n)/(sqrt(3)). - _Gary W. Adamson_, Mar 12 2008

%F a(n) = A080040(n)/2. - _Philippe Deléham_, Nov 19 2008

%F If p[1] = 1, and p[i] = 3, (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) = det A. - _Milan Janjic_, Apr 29 2010

%F a(n) = 2 * A052945(n-1). - _Vladimir Joseph Stephan Orlovsky_, Mar 24 2011

%F a(n) = round((1 + sqrt(3))^n/2) for n > 0. - _Bruno Berselli_, Feb 04 2013

%F G.f.: G(0)/2, where G(k)= 1 + 1/(1 - x*(3*k - 1)/(x*(3*k + 2) - 1/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, May 25 2013

%F a(n) = (-sqrt(2)*i)^n*T(n,sqrt(2)*i/2), with i = sqrt(-1) and the Chebyshev T-polynomials (A053120). - _Wolfdieter Lang_, Feb 10 2018

%e G.f. = 1 + x + 4*x^2 + 10*x^3 + 28*x^4 + 76*x^5 + 208*x^6 + 568*x^7 + ...

%p with(combstruct):ZL0:=S=Prod(Sequence(Prod(a, Sequence(b))), a):ZL1:=Prod(begin_blockP, Z, end_blockP):ZL2:=Prod(begin_blockLR, Z, Sequence(Prod(mu_length, Z), card>=1), end_blockLR): ZL3:=Prod(begin_blockRL, Sequence(Prod(mu_length, Z), card>=1), Z, end_blockRL):Q:=subs([a=Union(ZL2,ZL2,ZL2), b=ZL1], ZL0), begin_blockP=Epsilon, end_blockP=Epsilon, begin_blockLR=Epsilon, end_blockLR=Epsilon, begin_blockRL=Epsilon, end_blockRL=Epsilon, mu_length=Epsilon:temp15:=draw([S, {Q}, unlabelled], size=15):seq(count([S, {Q}, unlabelled], size=n)/3, n=2..27); # _Zerinvary Lajos_, Mar 08 2008

%t Expand[Table[((1 + Sqrt[3])^n + (1 - Sqrt[3])^n)/(2), {n, 0, 30}]] (* _Artur Jasinski_, Dec 10 2006 *)

%t LinearRecurrence[{2, 2}, {1, 1}, 30] (* _T. D. Noe_, Mar 25 2011 *)

%t Round@Table[LucasL[n, Sqrt[2]] 2^(n/2 - 1), {n, 0, 20}] (* _Vladimir Reshetnikov_, Oct 15 2016 *)

%o (PARI) {a(n) = if( n<0, 0, real((1 + quadgen(12))^n))};

%o (Sage) from sage.combinat.sloane_functions import recur_gen2; it = recur_gen2(1,1,2,2); [next(it) for i in range(30)] # _Zerinvary Lajos_, Jun 25 2008

%o (Sage) [lucas_number2(n,2,-2)/2 for n in range(0, 26)] # _Zerinvary Lajos_, Apr 30 2009

%o (Haskell)

%o a026150 n = a026150_list !! n

%o a026150_list = 1 : 1 : map (* 2) (zipWith (+) a026150_list (tail

%o a026150_list))

%o -- _Reinhard Zumkeller_, Oct 15 2011

%o (Maxima) a(n) := if n<=1 then 1 else 2*a(n-1)+2*a(n-2);

%o makelist(a(n),n,0,20); /* _Emanuele Munarini_, Apr 14 2017 */

%o (Magma) [n le 2 select 1 else 2*Self(n-1) + 2*Self(n-2): n in [1..30]]; // _G. C. Greubel_, Jan 07 2018

%Y First differences of A002605.

%Y The following sequences (and others) belong to the same family: A001333, A000129, A026150, A002605, A046717, A015518, A084057, A063727, A002533, A002532, A083098, A083099, A083100, A015519.

%Y Cf. A001075, A001834, A083337, A002605, A143908, A028859, A030195, A106435, A108898, A125145, A053120.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_