A284122 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).

0, 2, 4, 8, 12, 18, 26, 38, 56, 84, 128, 198, 310, 490, 780, 1248, 2004, 3226, 5202, 8398, 13568, 21932, 35464, 57358, 92782, 150098, 242836, 392888, 635676, 1028514, 1664138, 2692598, 4356680, 7049220, 11405840, 18454998, 29860774, 48315706, 78176412, 126492048, 204668388, 331160362, 535828674

Offset: 1

Author

Jeffrey Shallit, Mar 20 2017

Keywords

• nonn
• easy

Examples

			For n = 5, the 12 such strings are {00010,00011,00110,01011,01100,01110} and their binary complements.
		

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

Programs

Mathematica

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 *)
LinearRecurrence[{3,-2,-1,1},{0,2,4,8,12},50] (* Harvey P. Dale, Apr 07 2023 *)

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

Formula

For n >= 2, a(n) = 2F(n-1)+2n-4, where F(n) is the n-th Fibonacci number.

From Colin Barker, Mar 20 2017: (Start)

G.f.: 2*x^2*(1 - x - x^3) / ((1 - x)^2*(1 - x - x^2)).

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.

a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-4) for n>4.

(End)