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?