(Alternate Answer To) How Many Binary Strings Of At most Length $6$ have no consecutive zeros This question is giving me a lot of trouble. It's taking a very long time to solve.
My Work
I'll find how many strings have consecutive zeros and then deduct that from the total amount of strings
Case I: The Length of String is $1$
$0$ of these strings have consecutive $0$
Case II: The Length of String is $2$
$1$ string $00$ has consecutive $0$s
Case III: The Length of String is $3$
The string must contain at least $2$ zeros to have consecutive zeros. There are $2$ strings comprised of $1,0,0$ with consecutive zeros. There is one string comprised of $0,0,0$ that will have consecutive zeros. 3 strings.
Case IV: The Length of String is $4$
When there are two zeros and two 1s there are 3 consecutive strings. When there are 3 zeros and one 1s there must be 4 arrangements with consecutive zeros. When there are 4 zeros there are obviously 1 arrangement with 0. $3+4+1 = 8$ strings with consecutive zeros
Case V: The Length of String is $5$
2 0s and 3 1s. There are 4 strings with consecutive zeros. 3 0s and 2 1s there are 9 strings with consecutive zeros. 4 0s there are 5 strings with consecutive zeros. 5 zeros there is one string with consecutive zeros. $4+9+5+1 = 19$ strings with consecutive zeros.
Case VI: The Length of String is $6$
2 zeros there are 5 strings with consecutive zeros. 3 zeros there are 20 strings with consecutive zeros. 4 zeros and two 1s 15 total strings with consecutive zeros. 5 zeros means there are 6 strings with consecutive zeros. Six zeros means there is 1 string with consecutive zeros. $5+20+15+6+1 = 47$ strings with consecutive 0s.
$2^1+2^2+2^3+2^4+2^5+2^6 = 126$
$0+1+3+8+19+47 = 78$
Total Number of Strings Without Consecutive Zeros = 126-78 = 48
My Question:
Is my answer correct and is there a better way to do this question?
 A: A book by Sedgewick and Flajolet, An Introduction to the Analysis of Algorithms, shows a way to count the number of binary strings without consecutive zeros.
Let $\mathcal G$ be a class of binary strings with no two consecutive 0 bits. This kind of a string can either be empty (represented as $\epsilon$), a single 0 bit ($\mathcal{Z}_0$) or a single 1 bit ($\mathcal{Z}_1$) or 01 followed by a string with no two consecutive 0 bits.
This can be symbolically written as
$$ \mathcal{G} = \epsilon + \mathcal{Z}_0 + (\mathcal{Z}_1 + \mathcal{Z}_0 \times \mathcal{Z}_1) \mathcal{G}$$
and by using the generating functions that enumerate these classes (1 for $\epsilon$ and z for $\mathcal Z$) and the rules for their combination ($A(z) + B(z)$ enumerates $\mathcal A + \mathcal B$ and $A(z)B(z)$ enumerates $\mathcal A \times \mathcal B$) one gets an equation for the generating function $G(z)$ enumerating strings in the class $\mathcal G$
$$ G(z) = 1 + z + (z + z^2) G(z) .$$
Solving for $G(z)$ gives
$$ G(z) = \frac{1 + z}{1 - z - z^2} $$
and by observing that the generating function for the Fibonacci sequence can be written as $$F(z) = \frac{z}{1-z-z^2} $$ one can see that the answer (number of binary strings of length $N$ without consecutive zeros) can be written in terms of the Fibonacci numbers
$$ G_N = F_N + F_{N+1} = F_{N+2} .$$
The answer to the original question is then
$$ \sum_{i=0}^6 G_i = \sum_{i=0}^6 F_{i+2} = F_2 + F_3 + F_4 + F_5 + F_6 + F_7 + F_8 $$
$$ = F_4 + F_6 + 2F_8 = 3 + 8 + 2*21 = 53. $$
A: Look at the numbers of strings of each length without consecutive zeroes: 
$$\begin{array}{rcc}
\text{Length:}&0&1&2&3&4&5&6\\
\text{Nr. of strings:}&1&2&3&5&8&13&21
\end{array}\tag{1}$$
That bottom row should look familiar: it’s the Fibonacci numbers. Even if you don’t spot that, you should notice that each number is the sum of the previous two. A little thought reveals the reason. Consider the strings of length $n$ without consecutive zeroes. The ones that end in $1$ can all be obtained by adding a $1$ on the end of an allowable string of length $n-1$, and the ones that end in $0$ can all be obtained by adding $10$ to the end of an allowable string of length $n-2$. Thus, if $a_n$ is the number of strings of length $n$ without consecutive zeroes, we have $a_n=a_{n-1}+a_{n-2}$, the same rule that gives the Fibonacci numbers; only the starting point is different. (In fact, $a_n=F_{n+2}$.)
If you see all of this, you can easily write down the bottom row of $(1)$ and add up the entries to get $53$. However, unless you’ve already had a fair bit of experience, it may very well be just as fast to use your approach (though your number for $n=6$ is off).
