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!
 A: 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$.
A: 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$.
A: 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...
