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

%I #26 Oct 02 2024 16:52:58

%S 0,0,0,0,1,4,11,26,57,118,235,454,857,1588,2899,5228,9333,16520,29031,

%T 50702,88077,152290,262239,449930,769461,1312104,2231591,3786456,

%U 6410857,10832908,18272195,30769154,51733857,86859598,145642579,243907918,408005393,681773980,1138094971,1898045252,3162632157,5265345680

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

%C 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.

%H G. C. Greubel, <a href="/A248425/b248425.txt">Table of n, a(n) for n = 1..1000</a>

%H A. S. Fraenkel and J. Simpson, <a href="http://dx.doi.org/10.1016/S0304-3975(98)00252-7">The exact number of squares in Fibonacci words</a>, Theoret. Comput. Sci. 218 (1999), 95-106. Note: the formula given there has a small error, which has been corrected below.

%H A. S. Fraenkel and J. Simpson, <a href="http://dx.doi.org/10.1016/j.tcs.2014.06.011">Corrigendum to “The exact number of squares in Fibonacci words”</a>, Theoret. Comput. Sci. 218 (1999), 95-106.

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (4,-4,-2,4,0,-1).

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

%F G.f.: x^5*(1-x^2+x^4)/((1-x)*(1-x-x^2))^2. - _Colin Barker_, Oct 07 2014

%e 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.

%t A248425[n_]:= 2*(2*(n-6)*Fibonacci[n] -(n-5)*Fibonacci[n-1])/5 +n +3*Boole[n ==1] + Boole[n==3];

%t Table[A248425[n], {n,50}] (* _G. C. Greubel_, Oct 02 2024 *)

%o (Magma)

%o A248425:= func< n | n le 3 select 0 else (2/5)*(2*(n-6)*Fibonacci(n) - (n-5)*Fibonacci(n-1)) + n >;

%o [A248425(n): n in [1..50]]; // _G. C. Greubel_, Oct 02 2024

%o (SageMath)

%o def A248425(n): return (2/5)*(2*(n-6)*fibonacci(n) - (n-5)*fibonacci(n-1)) + n + 3*int(n==1) + int(n==3)

%o [A248425(n) for n in range(1,51)] # _G. C. Greubel_, Oct 02 2024

%Y Cf. A000045, A061107.

%K nonn,easy

%O 1,6

%A _Jeffrey Shallit_, Oct 06 2014