Number of length $8$ binary strings with no consecutive $0$'s How many $8$ bit strings are there with no consecutive $0$'s?
I just sat an exam, and the only question I think I got wrong was the above(The decider for a high-distinction or a distinction :SSS)
I took Number with consecutive $0$'s
1 zero $0$
2 zeros $\frac{7!}{6!}$
3 zeros above + $\frac{6!}{5!}$
4 zeroes above + $\frac{5!}{4!}$
5 zeros above + $\frac{4!}{3!}$
6 zeroes above + $\frac{3!}{2!}$
7 zeroes above + $\frac{2!}{1!}$
8 zeroes above + $1$
$(7*7)+(6*6)+(5*5)+(4*4)+(3*3)+(2*2)+1=140$
and we have $2^8 - 140=116$
Is this correct?

(Edited): 
The number of $n$-bit strings with no consecutive zeros is the Fibonacci number $F_{n+2}$.  There are $F_{n+1}$ of these strings ending in $1$ and $F_{n}$ ending in $0$ (prove by induction).
