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