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

1, 3, 7, 13, 23, 39, 65, 107, 175, 285, 463, 751, 1217, 1971, 3191, 5165, 8359, 13527, 21889, 35419, 57311, 92733, 150047, 242783, 392833, 635619, 1028455, 1664077, 2692535, 4356615, 7049153, 11405771, 18454927, 29860701, 48315631, 78176335

Offset

0,2

Comments

Number of run occurrences in the (n + 4)-th Fibonacci word A061107(n). (A run occurrence in a word x = x[1..t] is a pair (i, j) with 1 <= i <= j <= t such that x[i..j] has minimal period p, t >= 2*p, and neither x[i-1..j] nor x[i..j+1], if they exist, have period p.) - Jeffrey Shallit, Apr 09 2026

References

M. Crochemore, L. Ilie, and W. Rytter, Repetitions in strings: algorithms and combinatorics, Theoret. Comput. Sci. 410 (2009), 5227-5235. See Theorem 7.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

M. Crochemore, L. Ilie, and W. Rytter, Repetitions in strings: algorithms and combinatorics. (Preprint version of TCS paper given in the References.) See Theorem 7.

Tomislav Došlić and Biserka Kolarec, On Log-Definite Tempered Combinatorial Sequences, Mathematics (2025) Vol. 13, Iss. 7, 1179.

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

Formula

a(n+1) - a(n) = A006355(n+3) = A055389(n+3).

a(n) = A066629(n-1) + A066629(n).

a(n) = A006355(n+4) - 3 = A078642(n+1) - 3.

a(n+1) = a(n) + 2*A000045(n+2). - Reinhard Zumkeller, Nov 17 2013

From Colin Barker, Feb 01 2017: (Start)

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

a(n) = 2*a(n-1) - a(n-3) for n>2. (End)

a(n) = 2*Fibonacci(n+3) - 3. - Greg Dresden, Oct 10 2020

E.g.f.: 4*exp(x/2)*(5*cosh(sqrt(5)*x/2) + 2*sqrt(5)*sinh(sqrt(5)*x/2))/5 - 3*exp(x). - Stefano Spezia, Apr 09 2025

Maple

A154691 := proc(n) coeftayl( (1+x+x^2)/(1-x-x^2)/(1-x), x=0, n) ; end proc:

Mathematica

Fibonacci[Range[3, 60]]*2 -3 (* Vladimir Joseph Stephan Orlovsky, Mar 19 2010 *)
CoefficientList[Series[(1 + x + x^2)/((1 - x - x^2)(1 - x)), {x, 0, 40}], x] (* Vincenzo Librandi, Dec 18 2012 *)

Prog

(Haskell)
a154691 n = a154691_list !! n
a154691_list = 1 : zipWith (+)
                   a154691_list (drop 2 $ map (* 2) a000045_list)
-- Reinhard Zumkeller, Nov 17 2013
(PARI) Vec((1+x+x^2) / ((1-x-x^2)*(1-x)) + O(x^60)) \\ Colin Barker, Feb 01 2017
(Magma)
A154691:= func< n | 2*Fibonacci(n+3) - 3 >;
[A154691(n): n in [0..40]]; // G. C. Greubel, Jan 18 2025
(Python)
def A154691(n): return 2*fibonacci(n+3) - 3
print([A154691(n) for n in range(41)]) # G. C. Greubel, Jan 18 2025

Crossrefs

Cf. A000045, A001595, A006355, A055389, A061107, A066629, A078642, A166863.

Sequence in context: A155339 A122886 A385088 * A306902 A227121 A078447

Adjacent sequences: A154688 A154689 A154690 * A154692 A154693 A154694

Keyword

easy,nonn

Author

R. J. Mathar, Jan 14 2009

Status

approved