|
%I #13 Apr 07 2023 11:36:31
%S 0,2,4,8,12,18,26,38,56,84,128,198,310,490,780,1248,2004,3226,5202,
%T 8398,13568,21932,35464,57358,92782,150098,242836,392888,635676,
%U 1028514,1664138,2692598,4356680,7049220,11405840,18454998,29860774,48315706,78176412,126492048,204668388,331160362,535828674
%N Number of binary words w of length n for which s, the longest proper suffix of w that appears at least twice in w, is of length 1 (i.e., either s = 0 or s = 1).
%H Colin Barker, <a href="/A284122/b284122.txt">Table of n, a(n) for n = 1..1000</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2,-1,1).
%F For n >= 2, a(n) = 2F(n-1)+2n-4, where F(n) is the n-th Fibonacci number.
%F From _Colin Barker_, Mar 20 2017: (Start)
%F G.f.: 2*x^2*(1 - x - x^3) / ((1 - x)^2*(1 - x - x^2)).
%F a(n) = 2*(-2+(2^(-1-n)*((1-sqrt(5))^n*(1+sqrt(5)) + (-1+sqrt(5))*(1+sqrt(5))^n)) / sqrt(5) + n) for n>1.
%F a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-4) for n>4.
%F (End)
%e For n = 5, the 12 such strings are {00010,00011,00110,01011,01100,01110} and their binary complements.
%t Rest@ CoefficientList[Series[2 x^2*(1 - x - x^3)/((1 - x)^2*(1 - x - x^2)), {x, 0, 43}], x] (* _Michael De Vlieger_, Mar 20 2017 *)
%t LinearRecurrence[{3,-2,-1,1},{0,2,4,8,12},50] (* _Harvey P. Dale_, Apr 07 2023 *)
%o (PARI) concat(0, Vec(2*x^2*(1 - x - x^3) / ((1 - x)^2*(1 - x - x^2)) + O(x^50))) \\ _Colin Barker_, Mar 20 2017
%K nonn,easy
%O 1,2
%A _Jeffrey Shallit_, Mar 20 2017
|
