A128588 Expansion of g.f. x*(1+x+x^2)/(1-x-x^2).

1, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422, 57314, 92736, 150050, 242786, 392836, 635622, 1028458, 1664080, 2692538, 4356618, 7049156, 11405774, 18454930, 29860704, 48315634, 78176338

Offset

1,2

Comments

Previous name was: A007318 * A128587.

a(n)/a(n-1) tends to phi, 1.618... = A001622.

Regardless of initial two terms, any linearly recurring sequence with signature (1,1) will yield an a(n)/a(n+1) ratio tending to phi (the Golden Ratio). - Harvey P. Dale, Mar 29 2017

Apart from the initial term, double the Fibonacci numbers. O.g.f.: x*(1+x+x^2)/(1-x-x^2). a(n) gives the number of binary strings of length n-1 avoiding the substrings 000 and 111. a(n) also gives the number of binary strings of length n-1 avoiding the substrings 010 and 101. - Peter Bala, Jan 22 2008

Row lengths of triangle A232642. - Reinhard Zumkeller, May 14 2015

Links

Reinhard Zumkeller, Table of n, a(n) for n = 1..2500

J.-P. Allouche and T. Johnson, Narayana's Cows and Delayed Morphisms.

Andrei Asinowski and Cyril Banderier, On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) Leibniz International Proceedings in Informatics (LIPIcs) Vol. 159, 1:1-1:16.

Elena Barcucci, Antonio Bernini, Stefano Bilotta, and Renzo Pinzani, Non-overlapping matrices, arXiv:1601.07723 [cs.DM], 2016. See 1st column of Table 2 p. 11.

Jean-Luc Baril, Nathanaël Hassler, Sergey Kirgizov, and José L. Ramírez, Grand zigzag knight's paths, arXiv:2402.04851 [math.CO], 2024.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009, page 52.

B. Winterfjord, Binary strings and substring avoidance.

Index entries for linear recurrences with constant coefficients, signature (1,1).

Formula

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

Binomial transform of A128587; a(n+2) = a(n+1) + a(n), n>3.

a(n) = A068922(n-1), n>2. - R. J. Mathar, Jun 14 2008

For n > 1: a(n+1) = a(n) + if a(n) odd then max{a(n),a(n-1)} else min{a(n),a(n-1)}, see also A038754. - Reinhard Zumkeller, Oct 19 2015

E.g.f.: 4*exp(x/2)*sinh(sqrt(5)*x/2)/sqrt(5) - x. - Stefano Spezia, Feb 19 2023

Maple

a:= n-> `if`(n<2, n, 2*(<<0|1>, <1|1>>^n)[1, 2]):
seq(a(n), n=1..50);  # Alois P. Heinz, Apr 28 2018

Mathematica

nn=40; a=(1-x^3)/(1-x); b=x*(1-x^2)/(1-x); CoefficientList[Series[a^2 /(1-b^2), {x, 0, nn}], x]  (* Geoffrey Critzer, Sep 01 2012 *)
LinearRecurrence[{1, 1}, {1, 2, 4}, 40] (* Harvey P. Dale, Mar 29 2017 *)
Join[{1}, 2*Fibonacci[Range[2, 40]]] (* G. C. Greubel, Jul 10 2019 *)

Prog

(Haskell)
a128588 n = a128588_list !! (n-1)
a128588_list = 1 : cows where
                   cows = 2 : 4 : zipWith (+) cows (tail cows)
-- Reinhard Zumkeller, May 14 2015
(PARI) {a(n) = if( n<2, n==1, 2 * fibonacci(n))}; /* Michael Somos, Jul 18 2015 */
(Magma) [1] cat [2*Fibonacci(n): n in [2..40]]; // G. C. Greubel, Jul 10 2019
(Sage) [1]+[2*fibonacci(n) for n in (2..40)] # G. C. Greubel, Jul 10 2019
(GAP) Concatenation([1], List([2..40], n-> 2*Fibonacci(n))); # G. C. Greubel, Jul 10 2019

Crossrefs

Cf. A000045, A001622, A128587, A128586, A007318.

Cf. A006355, A055389.

Cf. A014217, A069403, A153819.

Cf. A232642, A242593.

Cf. A038754, A068922.

Main diagonal of A303696.

Sequence in context: A094985 A336662 A364580 * A023613 A306293 A307795

Adjacent sequences: A128585 A128586 A128587 * A128589 A128590 A128591

Keyword

nonn,easy

Author

Gary W. Adamson, Mar 11 2007

Extensions

New name from Joerg Arndt, Feb 16 2024

Status

approved