Understanding a recurrence relation 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.
 A: 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}
$$
A: 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$$
A: 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$
