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
Examples
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.
Links
- G. C. Greubel, Table of n, a(n) for n = 1..1000
- 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.
- Index entries for linear recurrences with constant coefficients, signature (4,-4,-2,4,0,-1).
Programs
-
Magma
A248425:= func< n | n le 3 select 0 else (2/5)*(2*(n-6)*Fibonacci(n) - (n-5)*Fibonacci(n-1)) + n >; [A248425(n): n in [1..50]]; // G. C. Greubel, Oct 02 2024
-
Mathematica
A248425[n_]:= 2*(2*(n-6)*Fibonacci[n] -(n-5)*Fibonacci[n-1])/5 +n +3*Boole[n ==1] + Boole[n==3]; Table[A248425[n], {n,50}] (* G. C. Greubel, Oct 02 2024 *)
-
SageMath
def A248425(n): return (2/5)*(2*(n-6)*fibonacci(n) - (n-5)*fibonacci(n-1)) + n + 3*int(n==1) + int(n==3) [A248425(n) for n in range(1,51)] # G. C. Greubel, Oct 02 2024
Formula
a(n) = (4/5)*(n-1)*F(n) - (2/5)*(n+5)*F(n-1) - 4*F(n-2) + n, for n >= 4, where F(n) = Fibonacci(n).
G.f.: x^5*(1-x^2+x^4)/((1-x)*(1-x-x^2))^2. - Colin Barker, Oct 07 2014
E.g.f.: 2*exp(x/2)*(5*(5 + 2*x)*cosh(sqrt(5)*x/2) - 29*sqrt(5)*sinh(sqrt(5)*x/2))/25 + x^3/6 + (3 + exp(x))*x - 2. - Stefano Spezia, May 23 2025
Comments