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