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
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).
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
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.
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 *)
PROG
(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
(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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Jeffrey Shallit, Oct 06 2014
STATUS
approved