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

%I #138 Jun 04 2024 12:11:39

%S 1,2,4,10,24,58,140,338,816,1970,4756,11482,27720,66922,161564,390050,

%T 941664,2273378,5488420,13250218,31988856,77227930,186444716,

%U 450117362,1086679440,2623476242,6333631924,15290740090,36915112104,89120964298,215157040700

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

%C Apart from the initial 1, this sequence is simply twice the Pell numbers, A000129. - _Antonio Alberto Olivares_, Dec 31 2003

%C Image of 1/(1-2x) under the mapping g(x) -> g(x/(1+x^2)). - _Paul Barry_, Jan 16 2005

%C 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

%C 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

%C 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

%C 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

%C 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

%C 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

%H Iain Fox, <a href="/A052542/b052542.txt">Table of n, a(n) for n = 0..2500</a> (first 1001 terms from Vincenzo Librandi)

%H C. Banderier and D. Merlini, <a href="http://algo.inria.fr/banderier/Papers/infjumps.ps">Lattice paths with an infinite set of jumps</a>, FPSAC02, Melbourne, 2002.

%H C. P. de Andrade, J. P. de Oliveira Santos, E. V. P. da Silva and K. C. P. Silva, <a href="http://dx.doi.org/10.4236/ojdm.2013.31006">Polynomial Generalizations and Combinatorial Interpretations for Sequences Including the Fibonacci and Pell Numbers</a>, Open Journal of Discrete Mathematics, 2013, 3, 25-32 doi:10.4236/ojdm.2013.31006. - From _N. J. A. Sloane_, Feb 20 2013

%H Massimiliano Fasi and Gian Maria Negri Porzio, <a href="http://eprints.maths.manchester.ac.uk/2709/">Determinants of Normalized Bohemian Upper Hessemberg Matrices</a>, University of Manchester (England, 2019).

%H I. M. Gessel and Ji Li, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Gessel/gessel6.html">Compositions and Fibonacci identities</a>, J. Int. Seq. 16 (2013) 13.4.5.

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

%H S. Kitaev and J. Remmel, <a href="http://arxiv.org/abs/1305.6970">The 1-box pattern on pattern avoiding permutations</a>, arXiv:1305.6970 [math.CO], 2013.

%H Haocong Song and Wen Wu, <a href="https://arxiv.org/abs/2007.09940">Hankel determinants of a Sturmian sequence</a>, arXiv:2007.09940 [math.CO], 2020. See p.2 and 4.

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

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

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

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

%F 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

%F Binomial transform of A094024. a(n) = 0^n + ((1 + sqrt(2))^n - (1 - sqrt(2))^n)/sqrt(2). - _Paul Barry_, Apr 22 2004

%F a(n) = Sum_{k=0..floor(n/2)} binomial(n-k-1, k)2^(n-2k). - _Paul Barry_, Jan 16 2005

%F 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

%F a(n) = round(sqrt(Pell(2n) + Pell(2n-1))). - _Richard R. Forberg_, Jun 22 2014

%F a(n) = 2*A000129(n) + A000007(n) - _Iain Fox_, Nov 30 2017

%F a(n) = A000129(n) - A000129(n-2). - _Gregory L. Simay_, Feb 17 2018

%p spec := [S,{S=Sequence(Prod(Union(Z,Z),Sequence(Prod(Z,Z))))},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);

%p A052542 := proc(n)

%p option remember;

%p if n <=2 then

%p 2^n;

%p else

%p 2*procname(n-1)+procname(n-2) ;

%p end if;

%p end proc: # _R. J. Mathar_, Sep 23 2016

%p A052542List := proc(m) local A, P, n; A := [1,2]; P := [1,1];

%p for n from 1 to m - 2 do P := ListTools:-PartialSums([op(A), P[-2]]);

%p A := [op(A), P[-1]] od; A end: A052542List(31); # _Peter Luschny_, Mar 26 2022

%t Join[{1}, LinearRecurrence[{2, 1}, {2, 4}, 40]] (* _Vladimir Joseph Stephan Orlovsky_, Feb 22 2012 *)

%o (PARI) Vec((1-x^2)/(1-2*x-x^2) +O(x^40)) \\ _Charles R Greathouse IV_, Nov 20 2011

%o (Haskell)

%o a052542 n = a052542_list !! n

%o a052542_list = 1 : 2 : 4 : tail (zipWith (+)

%o (map (* 2) $ tail a052542_list) a052542_list)

%o -- _Reinhard Zumkeller_, Feb 24 2015

%o (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

%o (Sage) ((1-x^2)/(1-2*x-x^2)).series(x, 40).coefficients(x, sparse=False) # _G. C. Greubel_, May 09 2019

%o (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

%Y Cf. A052906. Essentially first differences of A001333.

%K easy,nonn

%O 0,2

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