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

Author

Gary W. Adamson, Mar 11 2007

Keywords

• nonn
• easy

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

a(n) is the number of binary strings of length n-1 avoiding the substrings 000 and 111. - Allan C. Wechsler, Feb 13 2025

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

Crossrefs

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

Cf. A006355, A055389.

Cf. A014217, A069403, A153819.

Cf. A232642, A242593.

Cf. A038754, A068922.

Main diagonal of A303696.

Programs

GAP

Concatenation([1], List([2..40], n-> 2*Fibonacci(n))); # G. C. Greubel, Jul 10 2019

Haskell

a128588 n = a128588_list !! (n-1)
a128588_list = 1 : cows where
                   cows = 2 : 4 : zipWith (+) cows (tail cows)
-- Reinhard Zumkeller, May 14 2015

Magma

[1] cat [2*Fibonacci(n): n in [2..40]]; // G. C. Greubel, Jul 10 2019

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

PARI

{a(n) = if( n<2, n==1, 2 * fibonacci(n))}; /* Michael Somos, Jul 18 2015 */

Sage

[1]+[2*fibonacci(n) for n in (2..40)] # G. C. Greubel, Jul 10 2019

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

Extensions

New name from Joerg Arndt, Feb 16 2024