Prove function is Fibonacci sequence

Question

Stuck on how to finish a question I'm working on. Have to find the number of bitstrings of length n with no odd length maximal runs of ones. For example, when n=3 there are three such bitsrings: 011, 110 and 000. I've figured out n=1 there is 1, n=2 there are 2, n=3 there are 3, n=4 there are 5, and when n=5 there are 8 and so on. This is clearly the Fibonacci sequence. My problem is I don't know how to prove the number of these bitstrings of length n is equal to the number of these bitstrings of length n-1 plus the number of these bitstrings of length n-2.

Long story short, how do I prove that the result of a function is the Fibonacci sequence?

Thanks for any help!!

Answer 1

Let $S_n$ be this number for $n$ length bit string. Then, observe that $S_{n+1}$ will consist of bit strings obtained after appending $0$ or $1$ before the $n$ length bit strings. So, $S_{n+1}$ bit strings will contain the $S_n$ $n$ length bit strings appended with $0$ and also it will contain those $n$ length bit strings which have an odd run of $1$s starting from their MSB and containing no odd run later in the bit string. This clearly means that these $S_{n+1}-S_n$ $n$ length bit strings are the result of appending $1$ before the MSB of all the $n-1$ length bit strings with no odd length run of $1$'s i.e. $S_{n+1}-S_n=S_{n-1}$.

Answer 2

Say that a bit string is good if it has no odd-length maximal run of ones. Let $a_n$ be the number of good strings of length $n$. Suppose that $\sigma$ is a good string of length $n$. If $\sigma=\tau0$, where $\tau$ is the substring consisting of the first $n-1$ bits of $\sigma$, then $\tau$ is a good string of length $n-1$. Conversely, if $\tau$ is any good string of length $n-1$, then $\tau0$ is a good string of length $n$ ending in $0$. Thus, the number of good strings of length $n$ ending in $0$ is $a_{n-1}$.

Now suppose that $\sigma$ ends in $1$. Then $\sigma$ must end in $11$ (why?), so $\sigma=\tau11$ for some string $\tau$ of length $n-2$. Moreover, $\tau$ must be good; why? Conversely, if $\tau$ is a good string of length $n-2$, then $\tau11$ is a good string of length $n$ ending in $1$. Thus, the number of good strings of length $n$ ending in $1$ is $a_{n-2}$. We’ve covered all possibilities, so $a_n=a_{n-1}+a_{n-2}$.