Answer to POW #2:

Call a bit string with no consecutive 1s a "good" bit string. We will enumerate the good bit strings of length n in cases, according to the position of the first nonzero entry in the bit string.

There is 1 (good) bit string with no nonzero enties (all zeros).
There is 1 (good) bit string whose first nonzero entry is the last entry (0000...001).
There is 1 good bit string whose first nonzero entry is the second-to-last entry (0000...010).
There are 2 good bit strings whose first nonzero entry is the third-to-last entry (0000...100 and 0000..101).
There are 3=2+1 good bit strings whose first nonzero entry is the fourth-to-last entry (ending with 1000 or 1001 or 1010).
There are 5=3+2 good bit strings whose first nonzero entry is the fifth-to-last entry (ending with 10000 or 10001 or 10010 or 10100 or 10101).

The pattern continues as the Fibonacci sequence; if you look at a "tree" for each case you should be able to see WHY ths pattern is occurring.

Therefore the total number of good bit strings of length n is f(n) = 1 + the sum of the first n Fibonacci numbers.

(Note: It happens that this quantity is also equal to f(n) = the (n+2)th Fibonacci number! You can arrive at this alternate expression of the answer by a slightly different counting argument, where you count the number of good bit strings of length k for successively larger values of k.)

Source: Thinking about POW #1