A048739 Expansion of 1/((1 - x)*(1 - 2*x - x^2)).

1, 3, 8, 20, 49, 119, 288, 696, 1681, 4059, 9800, 23660, 57121, 137903, 332928, 803760, 1940449, 4684659, 11309768, 27304196, 65918161, 159140519, 384199200, 927538920, 2239277041, 5406093003, 13051463048, 31509019100, 76069501249

Offset: 0

Author

Barry E. Williams

Keywords

• easy
• nice
• nonn

Comments

Partial sums of Pell numbers A000129.

W(n){1,3;2,-1,1} = Sum_{i=1..n} W(i){1,2;2,-1,0}, where W(n){a,b; p,q,r} implies x(n) = p*x(n-1) - q*x(n-2) + r; x(0)=a, x(1)=b.

Number of 2 X (n+1) binary arrays with path of adjacent 1's from upper left to lower right corner. - R. H. Hardin, Mar 16 2002

Binomial transform of A029744. - Paul Barry, Apr 23 2004

Number of (s(0), s(1), ..., s(n+2)) such that 0 < s(i) < 4 and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n+2, s(0) = 1, s(n+2) = 3. - Herbert Kociemba, Jun 16 2004

Equals row sums of triangle A153346. - Gary W. Adamson, Dec 24 2008

Equals the sum of the terms of the antidiagonals of A142978. - J. M. Bergot, Nov 13 2012

a(p-2) == 0 mod p where p is an odd prime, see A270342. - Altug Alkan, Mar 15 2016

Also, the lexicographically earliest sequence of positive integers such that for n > 3, {sqrt(2)*a(n)} is located strictly between {sqrt(2)*a(n-1)} and {sqrt(2)*a(n-2)} where {} denotes the fractional part. - Ivan Neretin, May 02 2017

a(n+1) is the number of weak orderings on {1,...,n} that are weakly single-peaked w.r.t. the total ordering 1 < ... < n. - J. Devillet, Oct 06 2017

References

• Allombert, Bill, Nicolas Brisebarre, and Alain Lasjaunias. "On a two-valued sequence and related continued fractions in power series fields." The Ramanujan Journal 45.3 (2018): 859-871. See Theorem 3, d_{4n+3}.

Links

• T. D. Noe, Table of n, a(n) for n = 0..200
• M. Bicknell, A Primer on the Pell Sequence and related sequences, Fibonacci Quarterly, Vol. 13, No. 4, 1975, pp. 345-349.
• M. Bicknell-Johnson and G. E. Bergum, The Generalized Fibonacci Numbers {C(n)}, C(n)=C(n-1)+C(n-2)+K, Applications of Fibonacci Numbers, 1986, pp. 193-205.
• B. Bradie, Extensions and Refinements of some properties of sums involving Pell Numbers, Miss. J. Math. Sci 22 (1) (2010) 37-43
• M. Couceiro, J. Devillet, and J.-L. Marichal, Quasitrivial semigroups: characterizations and enumerations, arXiv:1709.09162 [math.RA], 2017.
• Jimmy Devillet, On the single-peakedness property, International summer school "Preferences, decisions and games" (Sorbonne Université, Paris, 2019).
• I. M. Gessel, Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5
• A. F. Horadam, Special properties of the sequence W_n(a,b; p,q), Fib. Quart., 5.5 (1967), 424-434.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1065
• Yun-Tak Oh, Hosho Katsura, Hyun-Yong Lee, Jung Hoon Han, Proposal of a spin-one chain model with competing dimer and trimer interactions, arXiv:1709.01344 [cond-mat.str-el], 2017.
• Ahmet Öteleş, On the sum of Pell and Jacobsthal numbers by the determinants of Hessenberg matrices, AIP Conference Proceedings 1863, 310003 (2017).
• Wipawee Tangjai, A Non-standard Ternary Representation of Integers, Thai J. Math (2020) Special Issue: Annual Meeting in Mathematics 2019, 269-283.
• Index entries for two-way infinite sequences
• Index entries for linear recurrences with constant coefficients, signature (3,-1,-1).

Crossrefs

First row of table A083087.

With a different offset, a(4n)=A008843(n), a(4n-2)=8*A001110(n), a(2n-1)=A001652(n).

Cf. A001333, A048654, A048655, A083044, A083047, A083050, A153346.

Programs

Maple

a:=n->sum(fibonacci(i,2), i=0..n): seq(a(n), n=1..29); # Zerinvary Lajos, Mar 20 2008

Mathematica

Join[{a=1,b=3},Table[c=2*b+a+1;a=b;b=c,{n,60}]] (* Vladimir Joseph Stephan Orlovsky, Feb 01 2011 *)
CoefficientList[Series[1/(1-3x+x^2+x^3),{x,0,30}],x] (* or *) LinearRecurrence[{3,-1,-1},{1,3,8},30] (* Harvey P. Dale, Jun 13 2011 *)

PARI

a(n)=local(w=quadgen(8));-1/2+(3/4+1/2*w)*(1+w)^n+(3/4-1/2*w)*(1-w)^n

PARI

vector(100, n, n--; floor((1+sqrt(2))^(n+2)/4)) \\ Altug Alkan, Oct 07 2015

PARI

Vec(1/((1-x)*(1-2*x-x^2)) + O(x^40)) \\ Michel Marcus, May 06 2017

Formula

a(n) = 2*a(n-1) + a(n-2) + 1 with n > 1, a(0)=1, a(1)=3.

a(n) = ((2 + (3*sqrt(2))/2)*(1 + sqrt(2))^n - (2 - (3*sqrt(2))/2)*(1 - sqrt(2))^n )/(2*sqrt(2)) - 1/2.

a(0)=1, a(n+1) = ceiling(x*a(n)) for n > 0, where x = 1+sqrt(2). - Paul D. Hanna, Apr 22 2003

a(n) = 3*a(n-1) - a(n-2) - a(n-3). With two leading zeros, e.g.f. is exp(x)(cosh(sqrt(2)x)-1)/2. a(n) = Sum_{k=0..floor((n+2)/2)} binomial(n+2, 2k+2)2^k. - Paul Barry, Aug 16 2003

-a(-3-n) = A077921(n). - N. J. A. Sloane, Sep 13 2003

E.g.f.: exp(x)(cosh(x/sqrt(2)) + sqrt(2)sinh(x/sqrt(2)))^2. - N. J. A. Sloane, Sep 13 2003

a(n) = floor((1+sqrt(2))^(n+2)/4). - Bruno Berselli, Feb 06 2013

a(n) = (((1-sqrt(2))^(n+2) + (1+sqrt(2))^(n+2) - 2) / 4). - Altug Alkan, Mar 16 2016

2*a(n) = A001333(n+2)-1. - R. J. Mathar, Oct 11 2017

a(n) = Sum_{k=0..n} binomial(n+1,k+1)*2^floor(k/2). - Tony Foster III, Oct 12 2017

Extensions

Corrected and extended by Larry Reeves (larryr(AT)acm.org), Jun 11 2002