A248425 Number of "squares" (repeated identical blocks) in the n-th Fibonacci word.

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

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: A002940 A356620 A030196 * A356621 A130103 A000295

Adjacent sequences: A248422 A248423 A248424 * A248426 A248427 A248428

Keyword

nonn

Author

Jeffrey Shallit, Oct 06 2014

Status

approved