0
$\begingroup$

Consider all $n$ bit binary sequences such that there are no two consecutive $1$'s.

Is it possible to get a closed form expression for the number of such sequences in terms of $n$? For example, when $n=3$, the permissible sequences are $000, 010, 101, 001$ and $100$.

To give you some headway, after grinding a lot, I got a recursive solution which I am not sure is correct and is certainly not neat.

Let $f_0(n-1)$ represents the number of such sequences of $(n-1)$ bits which end with $0$. Similarly, $f_1(n-1)$ represents the number of such sequences which end with $1$. So the task is to form $n$ bit sequences from these. By some simple logic, can we say this? $f_0(n)=f_0(n-1)+f_1(n-1)$ and $f_1(n)=f_0(n-1)$.

To stop the recursion, $f_0(2)=2$ and $f_1(2)=1$. But somehow the method seems too roundabout to me. While it is easy to write a code snippet for the solution, is it possible to express our solution, i.e. $f_0(n)+f_1(n)$ in a closed form expression?

$\endgroup$
2
$\begingroup$

You're almost there. All you need is to insert your expression $f_1(n)=f_0(n-1)$ to get $$ f_0(n) = f_0(n-1) + f_0(n-2)$$ which you should recognize as the recurrence that produces the Fibonacci numbers.

We also have $f_0(1)=1$ and $f_0(2)=2$, so the sequence is just offset by one position from the usual Fibonacci sequence, so you have $$ f_0(n) = F_{n+1} $$ and the total number of allowed sequences of length $n$ is $$ f_0(n) + f_1(n) = f_0(n) + f_0(n-1) = F_{n+1}+F_n = F_{n+2} $$

Now you can use any of the well-known methods for computing Fibonacci numbers; for example Binet's formula (which is in closed form but requires precise arithmetic on irrationals as $n$ grows large) or computing powers of the matrix $({}^1_1\,{}^1_0)$ by repeated squaring (which is a good way to compute exact results reasonably fast if you have a bignum library handy).

$\endgroup$
  • $\begingroup$ Thanks a lot. I should have recognised the Fibonacci pattern, so silly of me. $\endgroup$ – Della Nov 20 '16 at 11:28
  • $\begingroup$ The matrix approach is particularly appropriate for this problem: $$\begin{pmatrix}f_0\\f_1\end{pmatrix}_{n}=\begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}f_0\\f_1\end{pmatrix}_{n-1}=\cdots\begin{pmatrix}1&1\\1&0\end{pmatrix}^n\begin{pmatrix}1\\1\end{pmatrix}$$ $\endgroup$ – Yves Daoust Nov 20 '16 at 11:35
  • 1
    $\begingroup$ @YvesDaoust: ... and for every other system of coupled first-order linear recurrences. (It is arguably a detour to even go to the Fibonacci recurrence here instead of writing down the matrix directly, except that the Fibonacci numbers are famous enough that there's lot of specialized material available about them in particular). $\endgroup$ – Henning Makholm Nov 20 '16 at 11:43
1
$\begingroup$

Substituting $f_1$ in the first equation, you get the Fibonacci recurrence

$$f_0(n)=f_0(n-1)+f_0(n-2),$$ esasy as that.

$\endgroup$

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.