# Determining the number of bit strings of length n that contains no adjacent 0s

• $C_n =$ this number of bit strings

• A binary string with no adjacent 0s is constructed by

• Adding “1” to any string w of length $n-1$ satisfying the condition, or
• Adding “10” to any string v of length $n-2$ satisfying the condition

I still don't find that intuitive at all. Why adding up $C_{n-1} + C_{n-2}$ results in $C_n$? I have tried my best and asked my friends for help, but they find the formula unintuitive as well. Could anyone here come up with a clear explanation? Thanks!

The point of the formula $C_{n-2} + C_{n-1} = C_n$ is to make you realize that each bit string of length $n$ can be uniquely paired up with a bit string of length $n-1$ or a bit string of length $n-2$.

We go about doing this by thinking this way: If I have a bit string, what ways do I have to make it bigger, that will surely preserve the condition that no 2 zeroes are consecutive? Well, if $s$ (a bit string of length $k$) has no consecutive zeroes, appending a $1$ to the end of it will certainly not create two consecutive zeroes, so a bit string of length $k$ can be transformed into a bit string of length $k+1$. On the other hand, if $s$ has no consecutive zeroes, then appending $10$ to the end of it will certainly not create two consecutive zeroes, and thus a string of length $k$ can be transformed into a bit string of length $k+2$.

This shows that you can make strings bigger; also, if $s_1 \neq s_2$, then their transformations will also be different (convince yourself of that).

On the other hand, if $s$ is a bit string, either $s$ ends with a $1$ or $s$ ends with a $0$. If $s$ ends with a $0$, then it actually ends with $10$, because it cannot have two consecutive zeroes. If $s$ ends with a $1$, you can reduce it to make a bit string of length $k-1$. If $s$ ends with $10$, you can reduce it to make a bit string of length $k-2$. This shows that if you have a valid bit string, you can make one bit string that is shorter. Also, if $s_1\neq s_2$ have the same length, their reductions are also different. Convince yourself of that.

Thus you have created a pairing between the strings of lengths $k-2,k-1$ and the strings of length $k$. This implies that $C_{k-2} + C_{k-1} = C_k$.

• Thanks for the explanation. I didn't really get the "created a pairing between the strings..." part. We just came up with rules to reduce and transform the bit strings taking our restriction into account. I still can't see the relationship between the possible number of different strings and these "rules". – Avocado Oct 23 '17 at 5:49
• I actually got it now. I should have just thought about the last digit(s) as a fixed one (1) or one-zero (10). I also didn't first realize that these k-1 and k-2 are possible to add up because they represent mutually exclusive cases. – Avocado Oct 23 '17 at 9:16
• @Avocado i am glad I could help. If your problem was solved consider accepting an answer, so as to flag this as solved. – RGS Oct 23 '17 at 21:24

Generating Function Approach

If we use the representations $x\mapsto1$ and $x^2\mapsto01$, we get the generating function $$\sum_{k=0}^\infty(x+x^2)^k=\frac1{1-x-x^2}$$ which is the generating function for the Fibonacci Sequence.

To see why this is so, let $$\frac1{1-x-x^2}=\sum_{k=0}^\infty a_kx^k$$ Then we have \begin{align} 1 &=\left(1-x-x^2\right)\sum_{k=0}^\infty a_kx^k\\ &=\underbrace{\ \ \ \ \ a_0\ \ \ \ \ }_1+\underbrace{(a_1-a_0)}_0\,x+\sum_{k=2}^\infty\underbrace{(a_k-a_{k-1}-a_{k-2})}_0\,x^k \end{align}

Recursive Approach

Consider a string of length $n$. It can be a string of length $n-1$ with a $1$ appended, or it can be a string of length $n-2$ with a $10$ appended. It depends on whether the string of length $n$ ends in a $1$ or a $0$.

Thus, the number of strings of length $n$ is the number of strings of length $n-1$ plus the number of strings of length $n-2$.

You have essentially given the explanation already: all the possibilities for $C_n$ can be derived from those for $C_{n-1}$ and $C_{n-2}$... you add either $1$ if it has length $n-1$ or $10$ to the strings of length $n-2$... This covers the strings ending in $1$ and ending in $0$...

The Fibonacci sequence satisfies this recursion, yes indeed...

• $C_1 = 2$ since both bit strings of length $1$ do not have two consecutive zeros. $C_2 = 3$ since any bit string of length two is permissible except $00$. Therefore, $C_n$ is a shifted Fibonacci sequence. – N. F. Taussig Oct 17 '17 at 9:58
• Right. The "usual " one starts 1,1, I believe. .. – Chris Custer Oct 17 '17 at 15:04