Understanding a recurrence relation question.

Question

A computer system considers a bit string a valid codeword if and only if it does not contain $3$ consecutive zeroes. Thus $010010$ is a valid codeword of length $6$ while $011000$ is not. Let $a_n$ be the number of valid codewords of length $n$.

The problem is to find $a_1, a_2, a_3$.

I have found $a_1 = 2$ as $O$ and $1$ are the only possibilities in binary bit strings. Our lecturer has told us that $a_2 = 4$ and $a_3 = 7$, but I am not able to work out how he got those. I have looked around and haven't been able to break down the source of $4$ and $7$ ... Could someone give me a hint? Thank you in advance.

Answer 1

The total amount of possible codewords with $n$ bits, valid or not, is $2^n$. $3$ consecutive zeroes are invalid. $a_2$ doesn't have enough digits to make that happen, so every possibility must be valid.$$2^2=4$$

For $3$ digits the only invalid codeword is $000$. You need $3$ zeroes to be invalid, and your length is $3$, so they must all be $0$ to be invalid. That eliminates one out of your set of all possible codewords of length $3$. $$2^3-1=7$$

Answer 2

There are $2^2=4$ possible 2-bit strings.
They are all valid because no 2-bit string can contain 3 consecutive 0's.
So, $a_2=4$

There are $2^3=8$ possible 3-bit strings.
Only 1 of the possible strings has 3 zeros, namely '000'.
So, $a_3=2^3-1=7$

Answer 3

This has been answered, but to address the general case for $a_n$ I will add the following analysis.

Let $1_n$ denote the number of valid codewords of length $n$ ending with a $1$. Similarly, let $0_n$ denote the number of valid codewords ending with only one zero and $00_n$ those ending with two consecutive zeros. Then we have $$ a_n=1_n+0_n+00_n $$ and $$ \begin{align} 1_n&=a_{n-1}\\ 0_n&=1_{n-1}=a_{n-2}\\ 00_n&=0_{n-1}=a_{n-3} \end{align} $$ so combining these informations we have $$ a_n=a_{n-1}+a_{n-2}+a_{n-3} $$ If we set $a_{-1}=0_1=0$ and $a_0=1_1=1$ and $a_1=2$ we then get $$ \begin{align} a_{-1}&=1\\ a_0&=1\\ a_1&=2\\ a_2&=2+1+1=4\\ a_3&=4+2+1=7\\ a_4&=7+4+2=13\\ &...\\ &\text{etc.} \end{align} $$