Binary Sequences of length $n$ without $k$ consecutive $1$s or $0$s

Question

Earlier today I saw a question about binary sequences of length $n$ that contain no $3$ consecutive $1$s or $0$s. I want to generalize the problem a little and count the number of sequences that contain no $k$ consecutive $1$s or $0$s. First I made some observations:

• Because of symmetry, exactly half of the sequences end with $0$ and the other half with $1$
• If the sequence of length $n$ ends with $k-1$ consecutive $1$s then these consecutive $1$s must be preceded by a sequence of length $n-k+1$ that ends with $0$
• If the sequence of length $n$ ends with $1$ then this last digit must be preceded by a sequence of length $n-1$ that does not end with $k-1$ consecutive $1$s

Based on these observations and by defining $f_{n}$ as the number of binary sequences of length $n$ that contain no $k$ consecutive $1$s or $0$s we get the following recurrence relation:

$$ f_{n}=2f_{n-1}-f_{n-k} $$

I want to know if the relation I got is correct and I am also interested if there's other way to count the number of sequences.

Answer 1

Well , generally the best method for finding recurrence relation is Goulden-Jackson -Cluster Method. It is very powerful tool to find any recurrence relations. (I want to especially thank to @Markus Scheuer for this beautiful method)

I am putting a link for you : https://arxiv.org/abs/math/9806036 ,you can learn more about it.

Now , i will get in the solution to show you another method.

According to the article , our bad words are $000,111$.

Then , our alphabet is $V= \{0,1\}$

$$A(x)= \frac{1}{1-dx-weight(C)}$$ with $d=|V|=2$ and $weight(C) = weight(C[000])+ weight(C[111])$

Lets calculate $weight(C[000])$ according to the paper such that

$weight(C[000])= -x^3 - (x +x^2)weight(C[000])$

So , $weight(C[000]) = \frac{-x^3}{(1+x +x^2)} $

Lets calculate $weight(C[111])$ according to the paper such that

$weight(C[111])= -x^3 - (x +x^2)weight(C[111])$

So , $weight(C[111]) = \frac{-x^3}{(1+x +x^2)} $

Then , we said that $weight(C) = weight(C[000])+ weight(C[111])$ .Hence , $$weight(C) = \frac{-2x^3}{1+x+x^2} $$

Then , $$A(x) = \frac{1}{1-2x -\frac{-2x^3}{1+x+x^2}} = \frac{1+x+x^2}{1-x-x^2}$$

Now , we will turn this fraction into recurrence relation. See for instance theorem 4.1.1 in Enumerative Combinatorics, Vol. I by R. P. Stanley. (https://www.maa.org/press/maa-reviews/enumerative-combinatorics-vol-i)

According to the book , $$\frac{1+x+x^2}{1-x-x^2}= a_n= a_{n-1} + a_{n-2}$$

Moreover , $$\frac{1+x+x^2}{1-x-x^2}=1+2x+4x^2 +6x^3 + \color{blue}{10x^4} + 16x^5+...$$

This sequence says that there are $10$ binary strings of lenght $4$ that do not contain $3$ zeros or $3$ ones.

You can see the sequence by exapnding wolfram-alpha such that https://www.wolframalpha.com/input/?i=expanded+form+of+%281%2Bx%2Bx%5E2%29%2F%281-x-x%5E2%29

When we come to neither $k$ zeros nor $k$ ones. The system turned out to be

$$A(x) = \frac{1}{1-2x - \frac{-2x^k}{1+x+x^2 +...+x^{k-1}}}$$

where

$weight(C[000])= -x^k - (x +x^2+..+x^{k-1})weight(C[000])$ $weight(C[111])= -x^k - (x +x^2+..+x^{k-1})weight(C[111])$

So , $$A(x) = \frac{1+x+x^2+..x^{k-1}}{1-x-x^2 - ...-x^{k-1}}$$

Then , by the same method ; $$a_{n+k-1}-a_{n+k-2}-a_{n+k-3}-...-a_{k-1}=0$$

Then , for example , if $k=5$ , then $$a_{n+4}-a_{n+3}-a_{n+2}-...-a_{n}=0$$

So , $$a_n=a_{n-1}+a_{n-2}+a_{n-3}+a_{n-4}$$

As a result , for any $k >1 $ ,the number of binary strings that do contain neither $k$ zeros nor $k$ ones is : $$a_n=a_{n-1}+a_{n-2}+...+a_{n-k+1}$$