login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A248425 Number of "squares" (repeated identical blocks) in the n-th Fibonacci word. 0
0, 0, 0, 0, 1, 4, 11, 26, 57, 118, 235, 454, 857, 1588, 2899, 5228, 9333, 16520, 29031, 50702, 88077, 152290, 262239, 449930, 769461, 1312104, 2231591, 3786456, 6410857, 10832908, 18272195, 30769154, 51733857, 86859598, 145642579, 243907918, 408005393, 681773980, 1138094971, 1898045252, 3162632157, 5265345680 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,6

COMMENTS

Here the Fibonacci words are given by X_0 = 0, X_1 = 1, and X_n = X_{n-1} X_{n-2} where juxtaposition means concatenation.

LINKS

Table of n, a(n) for n=1..42.

A. S. Fraenkel and J. Simpson, The exact number of squares in Fibonacci words, Theoret. Comput. Sci. 218 (1999), 95-106. Note:  the formula given there has a small error, which has been corrected below.

A. S. Fraenkel and J. Simpson, Corrigendum to “The exact number of squares in Fibonacci words”, Theoret. Comput. Sci. 218 (1999), 95-106.

FORMULA

a(n) = (4/5)nF(n+1) - (2/5)(n+6)F(n) - 4F(n-1) + n + 1 (for n >= 3).

Empirical g.f.: x^5*(x^4-x^2+1) / ((x-1)^2*(x^2+x-1)^2). - Colin Barker, Oct 07 2014

EXAMPLE

The 5th Fibonacci word is 10110101, which has the following four squares: 11 starting at position 3, 1010 at position 4, 0101 at position 5, and 101101 at position 1.

CROSSREFS

Cf. A061107.

Sequence in context: A027660 A002940 A030196 * A130103 A000295 A125128

Adjacent sequences:  A248422 A248423 A248424 * A248426 A248427 A248428

KEYWORD

nonn

AUTHOR

Jeffrey Shallit, Oct 06 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 31 03:48 EDT 2020. Contains 333136 sequences. (Running on oeis4.)