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

1, 1, 4, 10, 28, 76, 208, 568, 1552, 4240, 11584, 31648, 86464, 236224, 645376, 1763200, 4817152, 13160704, 35955712, 98232832, 268377088, 733219840, 2003193856, 5472827392, 14952042496, 40849739776

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

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

a(n+1)/a(n) converges to 1 + sqrt(3) = 2.732050807568877293.... - Philippe Deléham, Jul 03 2005

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

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

Inverse binomial transform of A001075: (1, 2, 7, 26, 97, 362, ...). - Gary W. Adamson, Nov 23 2007

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

[1, 3; 1, 1]^n * [1,0] = [a(n), A002605(n)]. - Gary W. Adamson, Mar 21 2008

(1 + sqrt(3))^n = a(n) + A002605(n)*(sqrt(3)). - Gary W. Adamson, Mar 21 2008

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

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

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

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

(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

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

Starting from a(1), first differences of A005665. - Ivan N. Ianakiev, Nov 22 2019

Number of 3-permutations of n elements avoiding the patterns 231, 312. See Bonichon and Sun. - Michel Marcus, Aug 19 2022

Examples

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

References

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

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
• Martin Burtscher, Igor Szczyrba, Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
• C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.
• C. Bautista-Ramos and C. Guillen-Galvan, Fibonacci numbers of generalized Zykov sums, J. Integer Seq., 15 (2012), Article 12.7.8.
• Nicolas Bonichon and Pierre-Jean Morel, Baxter d-permutations and other pattern avoiding classes, arXiv:2202.12677 [math.CO], 2022.
• A. Burstein, S. Kitaev and T. Mansour, Independent sets in certain classes of (almost) regular graphs, arXiv:math/0310379 [math.CO], 2003.
• Guillaume Escamocher and Barry O'Sullivan, Three-Dimensional Matching Instances Are Rich in Stable Matchings, CPAIOR 2018, pages 182-197.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1052
• Tanya Khovanova, Recursive Sequences
• Emanuele Munarini, A generalization of André-Jeannin's symmetric identity, Pure Mathematics and Applications (2018) Vol. 27, No. 1, 98-118.
• Nathan Sun, On d-permutations and Pattern Avoidance Classes, arXiv:2208.08506 [math.CO], 2022.
• Index entries for linear recurrences with constant coefficients, signature (2,2).
• Index entries for sequences related to Chebyshev polynomials.

Crossrefs

First differences of A002605.

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

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

Programs

Haskell

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

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

Maple

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

Mathematica

Expand[Table[((1 + Sqrt[3])^n + (1 - Sqrt[3])^n)/(2), {n, 0, 30}]] (* Artur Jasinski, Dec 10 2006 *)
LinearRecurrence[{2, 2}, {1, 1}, 30] (* T. D. Noe, Mar 25 2011 *)
Round@Table[LucasL[n, Sqrt[2]] 2^(n/2 - 1), {n, 0, 20}] (* Vladimir Reshetnikov, Oct 15 2016 *)

Maxima

a(n) := if n<=1 then 1 else 2*a(n-1)+2*a(n-2);
makelist(a(n),n,0,20); /* Emanuele Munarini, Apr 14 2017 */

PARI

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

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

Sage

[lucas_number2(n,2,-2)/2 for n in range(0, 26)] # Zerinvary Lajos, Apr 30 2009

Formula

a(n) = (1/2)*((1 + sqrt(3))^n + (1 - sqrt(3))^n). - Benoit Cloitre, Oct 28 2002

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

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

From Paul Barry, May 15 2003: (Start)

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

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

a(n) = Sum_{k=0..n} A098158(n,k)*3^(n - k). - Philippe Deléham, Dec 26 2007

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

a(n) = A080040(n)/2. - Philippe Deléham, Nov 19 2008

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

a(n) = 2 * A052945(n-1). - Vladimir Joseph Stephan Orlovsky, Mar 24 2011

a(n) = round((1 + sqrt(3))^n/2) for n > 0. - Bruno Berselli, Feb 04 2013

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

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