f(n) = (ways to start number with 0) + (ways to start number with 1)

If the number starts with 0, the problem reduces to the n - 1 case. If the number starts with 1, the next bit must be 0, and we reduce to the n - 2 case.

So, for n > 2, f(n) = f(n - 1) + f(n - 2).

If you forbid m adjacent 1-bits, then the permitted n-bit numbers are those that begin with 0,1,...,m-1 adjacent 1s followed by a 0. Hence f(n) = f(n-1) + ... + f(n-m). (That holds for n>=m. For smaller n, you can either say directly that the number is 2^n or else set f(0)=1 and f(anything negative)=0 and use the recurrence for 1 onwards.)

Next question: fix m; then, when n is Very Large, roughly how big is f(n)? There's some nice mathematics behind this...

Peter's correct. The answer is f(n+2) where f(n) is the Fibonacci sequence. (i.e. f(1)=1, f(2)=1, f(3)=2, f(4)=3, f(5)=5 etc..).
For 3 bits: f(3+2) = 5.
For 4 bits: f(4+2) = 8.
etc...

Now the question is, what's the answer for this puzzle if we change it to 3 adjacent bits? 4 adjacent bits? m adjacent bits?

It's a Fibonacci sequence. 1 bit = 2, 2 bits = 3, 3 bits = 5, etc.
If you look at have already calculated the nth # of bits, then n+2 is four groups of the same numbers, each preceded by 00, 01, 10, 11.
The first one is the same as n, the second one will eliminate all numbers that have a 1 in the high order bit. These first two groups, when combined, is the solution to n+1.
The third group gives the same result as n, and in the fourth group, no numbers qualify (11 doesn't qualify by definition). So the third+fourth group = n.
So:

f(n+2) = 1st+2nd+3rd+4th blocks
f(n+2) = (1st+2nd) + (3rd+4th)
f(n+2) = f(n+1) + f(n)
f(n+2) = f(n) + f(n+1)

Which is the definition of the Fibonacci sequence. Sorry about the sloppy mathematical notation.

-Peter

'fraid not...

2^(n-1) + 1