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,2

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

Links

Iain Fox, Table of n, a(n) for n = 0..2500 (first 1001 terms from Vincenzo Librandi)

C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.

C. P. de Andrade, J. P. de Oliveira Santos, E. V. P. da Silva and K. C. P. 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, Gian Maria Negri Porzio, Determinants of Normalized Bohemian Upper Hessemberg Matrices, University of Manchester (England, 2019).

I. M. Gessel, Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 477

S. Kitaev and J. 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).

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] = 2modp(i,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

G.f.: 1 + x + x^2/(2*G(0)-x) where G(k) = 1 - (k+1)/(1 - x/(x +(k+1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Dec 07 2012

G.f.: G(0)*(1-x)/(2*x) + 1 - 1/x, where G(k)= 1 + 1/(1 - x*(2*k-1)/(x*(2*k+1) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 26 2013

G.f.: 1 + G(0)*x/(1-x), where G(k) = 1 + 1/(1 - x*(2*k-1)/(x*(2*k+1) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 19 2013

G.f.: 1 + (1+G(0))/(2-2*x), where G(k) = 2*x*(k+2) - 1 - x + x*(2*k-1)/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Aug 14 2013

G.f.: Q(0), where Q(k) = 1 + (1+x)*x + (2*k+3)*x - x*(2*k+1 + x+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 04 2013

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

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 *)

Prog

(PARI) Vec((1-x^2)/(1-2*x-x^2) +O(x^40)) \\ Charles R Greathouse IV, Nov 20 2011
(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
(Sage) ((1-x^2)/(1-2*x-x^2)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, May 09 2019
(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

Crossrefs

Cf. A052906. Essent. first diffs. of A001333.

Sequence in context: A024740 A025275 A165409 * A163271 A178036 A191625

Adjacent sequences: A052539 A052540 A052541 * A052543 A052544 A052545

Keyword

easy,nonn

Author

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

Status

approved