How many n bit sequences of 0's and 1's are there without two consecutive 1's?
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 Answers
$\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$ 3 $\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$ 0More in general
"Zoraya ter Beek, age 29, just died by assisted suicide in the Netherlands. She was physically healthy, but psychologically depressed. It's an abomination that an entire society would actively facilitate, even encourage, someone ending their own life because they had no hope. Th…"
