A007909 Expansion of (1-x)/(1-2*x+x^2-2*x^3).

1, 1, 1, 3, 7, 13, 25, 51, 103, 205, 409, 819, 1639, 3277, 6553, 13107, 26215, 52429, 104857, 209715, 419431, 838861, 1677721, 3355443, 6710887, 13421773, 26843545, 53687091, 107374183, 214748365, 429496729, 858993459, 1717986919, 3435973837, 6871947673

Offset: 0

Author

Mogens Esrom Larsen (mel(AT)math.ku.dk)

Keywords

• nonn
• easy

Comments

Equals INVERT transform of (1, 0, 2, 2, 2, ...). - Gary W. Adamson, Apr 28 2009

a(n) is the number of compositions (ordered partitions) of n into parts 1 (one kind), and parts >= 3 of three kinds (no parts 2). - Joerg Arndt, Apr 22 2025

References

• Kenneth Edwards, Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
• M. E. Larsen, Summa Summarum, A. K. Peters, Wellesley, MA, 2007; see p. 38.

Links

• M. F. Hasler, Table of n, a(n) for n = 0..1000 (in replacement of a(0..999) indexed 1..1000 from Vincenzo Librandi).
• Charles K. Cook and Michael R. Bacon, Some identities for Jacobsthal and Jacobsthal-Lucas numbers satisfying higher order recurrence relations, Annales Mathematicae et Informaticae, 41 (2013) pp. 27-39.
• Shanzhen Gao, Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science.
• I. Gessel, Problem 10424, Amer. Math. Monthly, 102 (1995), 70.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 444
• Yüksel Soykan, Properties of Generalized (r, s, t, u)-Numbers, Earthline J. of Math. Sci. (2021) Vol. 5, No. 2, 297-327.
• Index entries for linear recurrences with constant coefficients, signature (2,-1,2).

Crossrefs

Cf. A005251, A007679, A007910.

Programs

Magma

I:=[1, 1, 1]; [n le 3 select I[n] else 2*Self(n-1)-Self(n-2)+2*Self(n-3): n in [1..40]]; // Vincenzo Librandi, Jun 17 2012

Maple

U:=n->(1/5)*(2^(n+1)+3*cos(n*Pi/2)+sin(n*Pi/2)); [seq(U(n),n=0..50)];

Mathematica

CoefficientList[Series[(1-x)/(1-2*x+x^2-2*x^3),{x,0,40}],x] (* Vincenzo Librandi, Jun 17 2012 *)
LinearRecurrence[{2,-1,2},{1,1,1},40] (* Harvey P. Dale, Jul 26 2016 *)

PARI

a(n)=2^(n+1)\5+(n%4<2) \\ M. F. Hasler, Feb 22 2018

Python

def A007909(n): return (2<Chai Wah Wu, Apr 22 2025

Formula

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

a(n) = (1/5)*(2^(n+1)+3*cos(n*Pi/2)+sin(n*Pi/2)).

a(n) = Sum_{k=0..floor((n-1)/3)} binomial(n-k-1, 2*k)*2^k. - Paul Barry, Sep 16 2004

a(n) = (1/5)*(2^(n+1) + (-1)^[(n+1)/2] + 2*(-1)^[n/2]). - Ralf Stephan, Jun 09 2005

a(n) = 2*a(n-1)-a(n-2)+2*a(n-3). Sequence is identical to its half second differences from the second term; a(n)+a(n+2)=2^(n+1). - Paul Curtz, Dec 17 2007

a(n+1) = (2^n)*Sum_{k=1..n} (-1)^floor(k/2)/2^k. - Yalcin Aktar, Jul 20 2008

Extensions

Offset corrected by M. F. Hasler, Feb 22 2018