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

1, 2, 4, 10, 24, 58, 140, 338, 816, 1970, 4756, 11482, 27720, 66922, 161564, 390050, 941664, 2273378, 5488420, 13250218, 31988856, 77227930, 186444716, 450117362, 1086679440, 2623476242, 6333631924, 15290740090, 36915112104, 89120964298, 215157040700

Offset: 0

Author

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Keywords

• easy
• nonn

Comments

Apart from the initial 1, this sequence is simply twice the Pell numbers, A000129. - Antonio Alberto Olivares, Dec 31 2003

Image of 1/(1-2x) under the mapping g(x) -> g(x/(1+x^2)). - Paul Barry, Jan 16 2005

The intermediate convergents to 2^(1/2) begin with 4/3, 10/7, 24/17, 58/41; essentially, numerators = A052542 and denominators = A001333. - Clark Kimberling, Aug 26 2008

a(n) is the number of generalized compositions of n+1 when there are 2*i-2 different types of i, (i=1,2,...). - Milan Janjic, Aug 26 2010

Apart from the initial 1, this is the p-INVERT transform of (1,0,1,0,1,0,...) for p(S) = 1 - 2 S. See A291219. - Clark Kimberling, Sep 02 2017

Conjecture: Apart from the initial 1, a(n) is the number of compositions of two types of n having no even parts. - Gregory L. Simay, Feb 17 2018

For n>0, a(n+1) is the length of tau^n(10) where tau is the morphism: 1 -> 101, 0 -> 1. See Song and Wu. - Michel Marcus, Jul 21 2020

The above conjecture is true, as the g.f. can be written as 1/(1 - (2*x)/(1 - x^2)). - John Tyler Rascoe, Jun 01 2024

Links

• Iain Fox, Table of n, a(n) for n = 0..2500 (first 1001 terms from Vincenzo Librandi)
• Cyril Banderier and Donatella Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.
• Cecília Pereira de Andrade, José Plínio de Oliveira Santos, Elen Viviani Pereira da Silva, and Kênia Cristina Pereira Silva, Polynomial Generalizations and Combinatorial Interpretations for Sequences Including the Fibonacci and Pell Numbers, Open Journal of Discrete Mathematics, 2013, 3, 25-32 doi:10.4236/ojdm.2013.31006. - From _N. J. A. Sloane_, Feb 20 2013
• Massimiliano Fasi and Gian Maria Negri Porzio, Determinants of Normalized Bohemian Upper Hessemberg Matrices, University of Manchester (England, 2019).
• Sela Fried, Even-up words and their variants, arXiv:2505.14196 [math.CO], 2025. See p. 4.
• Ira M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 477
• Sergey Kitaev and Jeffrey Remmel, The 1-box pattern on pattern avoiding permutations, arXiv:1305.6970 [math.CO], 2013.
• Haocong Song and Wen Wu, Hankel determinants of a Sturmian sequence, arXiv:2007.09940 [math.CO], 2020. See p.2 and 4.
• Index entries for linear recurrences with constant coefficients, signature (2,1).

Crossrefs

Cf. A052906. Essentially first differences of A001333.

Programs

GAP

a:=[2,4];; for n in [3..40] do a[n]:=2*a[n-1]+a[n-2]; od; a; # G. C. Greubel, May 09 2019

Haskell

a052542 n = a052542_list !! n
a052542_list = 1 : 2 : 4 : tail (zipWith (+)
               (map (* 2) $ tail a052542_list) a052542_list)
-- Reinhard Zumkeller, Feb 24 2015

Magma

I:=[2,4]; [n le 2 select I[n] else 2*Self(n-1) +Self(n-2): n in [1..40]]; // G. C. Greubel, May 09 2019

Maple

spec := [S,{S=Sequence(Prod(Union(Z,Z),Sequence(Prod(Z,Z))))},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);
A052542 := proc(n)
    option remember;
    if n <=2 then
        2^n;
    else
        2*procname(n-1)+procname(n-2) ;
    end if;
end proc: # R. J. Mathar, Sep 23 2016
A052542List := proc(m) local A, P, n; A := [1,2]; P := [1,1];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(A), P[-2]]);
A := [op(A), P[-1]] od; A end: A052542List(31); # Peter Luschny, Mar 26 2022

Mathematica

Join[{1}, LinearRecurrence[{2, 1}, {2, 4}, 40]] (* Vladimir Joseph Stephan Orlovsky, Feb 22 2012 *)

PARI

Vec((1-x^2)/(1-2*x-x^2) +O(x^40)) \\ Charles R Greathouse IV, Nov 20 2011

Sage

((1-x^2)/(1-2*x-x^2)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, May 09 2019

Formula

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

Recurrence: a(0)=1, a(2)=4, a(1)=2, a(n) + 2*a(n+1) - a(n+2) = 0;

a(n) = Sum_{alpha = RootOf(-1+2*x+x^2)} (1/2)*(1-alpha)*alpha^(-n-1).

a(n) = 2*A001333(n-1) + a(n-1), n > 1. A001333(n)/a(n) converges to sqrt(1/2). - Mario Catalani (mario.catalani(AT)unito.it), Apr 29 2003

Binomial transform of A094024. a(n) = 0^n + ((1 + sqrt(2))^n - (1 - sqrt(2))^n)/sqrt(2). - Paul Barry, Apr 22 2004

a(n) = Sum_{k=0..floor(n/2)} binomial(n-k-1, k)2^(n-2k). - Paul Barry, Jan 16 2005

If p[i] = 2*(i mod 2) 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, May 02 2010

a(n) = round(sqrt(Pell(2n) + Pell(2n-1))). - Richard R. Forberg, Jun 22 2014

a(n) = 2*A000129(n) + A000007(n) - Iain Fox, Nov 30 2017

a(n) = A000129(n) - A000129(n-2). - Gregory L. Simay, Feb 17 2018