Find a recursive relation for the case of a length $n$ binary string where there are no three consecutive $0$'s.

Question

Find a recursive formula for the following example. The number of binary strings of length $n$, such that there are no $3$ consecutive $0's$.

I started by considering the length $n$ as a block ($1$ row) with $n$ many columns. I started off by considering only the last column, marked $x$. Here's my working:

Int the case that the very last string is $0$, I think my working out is correct. Now, if the last string is $1$, then I'm left with $n-1$ without any further complications. Therefore, $a_n= 2a_{(n-1)}+a_{(n-2)}+a_{(n-3)}$. Is this correct?

Answer 1

Critique

The diagram in the question is correct, but the recursion drawn from it is slightly off. In the diagram, it is shown that each of the $a_n$ strings of length $n$ with out a '$000$' can be classified as follows:

It ends in a '$\boldsymbol{1}$':$\phantom{00}$ $\overbrace{\boxed{\phantom{0\times\times\times\times000\times}}\boxed{\times\vphantom{0}}}^{n-1}\!\,\boxed{1\vphantom{\times}}$ There are $a_{n-1}$ of these.

It ends in a '$\boldsymbol{10}$':$\phantom{0}$ $\overbrace{\boxed{\phantom{0\times\times00\times\times}}\boxed{\times\vphantom{0}}}^{n-2}\!\,\boxed{1\vphantom{\times}}\boxed{0\vphantom{\times}}$ There are $a_{n-2}$ of these.

It ends in a '$\boldsymbol{100}$': $\overbrace{\boxed{\phantom{0\times\times\times\times}}\boxed{\times\vphantom{0}}}^{n-3}\!\,\boxed{1\vphantom{\times}}\boxed{0\vphantom{\times}}\boxed{0\vphantom{\times}}$ There are $a_{n-3}$ of these.

Therefore, adding these cases up, we get $$ a_n=a_{n-1}+a_{n-2}+a_{n-3}\tag1 $$ In the question, it seems that the intermediate tree node, i.e. $\overbrace{\boxed{\phantom{0\times\times\times\times}}\boxed{\times\vphantom{0}}}^{n-1}\!\boxed{0\vphantom{\times}}$, is being included in the counting, but that node is counted in the leaves below it.

---

Generating Function Approach

Let $x$ represent the atom '$1$', $x^2$ represent the atom '$10$', and $x^3$ represent the atom '$100$'.

$\left(x+x^2+x^3\right)^k$ counts the strings made up of $k$ atoms; the coefficient of $x^n$ telling the how many strings of length $n$ can be made from $k$ atoms. After adding up the contributions from all numbers of the atoms, we handle the strings starting with '$0$' and '$00$' by multiplying by $\left(1+x+x^2\right)$ to get the generating function for the number of strings that can be made up from any number of atoms is $$ \begin{align} \left(1+x+x^2\right)\sum_{k=0}^\infty\left(x+x^2+x^3\right)^k &=\left(1+x+x^2\right)\sum_{k=0}^\infty\left(\frac{x-x^4}{1-x}\right)^k\\ &=\left(1+x+x^2\right)\frac1{1-\frac{x-x^4}{1-x}}\\ &=\left(1+x+x^2\right)\frac{1-x}{1-2x+x^4}\\[3pt] &=\frac{1+x+x^2}{1-x-x^2-x^3}\\[9pt] &=1+2x+4x^2+7x^3+13x^4+24x^5+\dots \end{align} $$ The denominator of $1-x-x^2-x^3$ gives the recurrence $a_n=a_{n-1}+a_{n-2}+a_{n-3}$.

Answer 2

To gather the comments:

• You are leaving out the $a$'s. There is a difference between the meaning of $a_{n-1}$ and the value $(n-1)$. On the one hand $a_{n-1}$ is the number of valid length $n-1$ strings we are wanting to count. On the other hand $(n-1)$ is merely the length of a length $n-1$ string... not the count of them.

• You have a rogue $2$ which appeared which shouldn't have, perhaps from reading your image incorrectly. It feels like when you went to break into cases you broke into the case where the final digit was a $1$ which accounts for $a_{n-1}$ of the total, and where you broke into where the final digit was a $0$. You broke this second case down into two further subcases of sizes $a_{n-2}$ and $a_{n-3}$ respectively and added... It felt like maybe you accidentally added a value intended to be for the second case before it was broken into subcases as well but this was unnecessary as we were adding the values for the subcases already so it should already by covered.

Additionally:

• You haven't written any initial conditions yet.

For initial conditions, a tip: it can be easier to deal with zero as it is far more convenient. You can work with as one of the initial conditions that $a_0 = 1$. It is worth making sure you fully understand why $a_0=1$, that there is in fact a unique length zero valid string, namely " ".

If that is too abstract for you to accept (though, you really should learn to come to terms with it sooner rather than later), then go ahead and count with your fingers how many valid strings there are of length $1$, $2$, and $3$ manually. I discourage this however as it can be easy to make a mistake, especially for larger harder problems.

The fact that "0" is a valid string of length $1$ is also worth taking into account as otherwise this might have been missed by the formula (as I had done before my edit).

So... our final answer should have read:

$$a_n = a_{n-1}+a_{n-2}+a_{n-3}~~~~~\text{for all }n>2\\a_0 = 1~~~~a_1 = 2~~~~~a_2=4$$