1
$\begingroup$

• $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!

$\endgroup$
2
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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". $\endgroup$ – Avocado Oct 23 '17 at 5:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Avocado Oct 23 '17 at 9:16
  • $\begingroup$ @Avocado i am glad I could help. If your problem was solved consider accepting an answer, so as to flag this as solved. $\endgroup$ – RGS Oct 23 '17 at 21:24
0
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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...

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ $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. $\endgroup$ – N. F. Taussig Oct 17 '17 at 9:58
  • $\begingroup$ Right. The "usual " one starts 1,1, I believe. .. $\endgroup$ – Chris Custer Oct 17 '17 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.