Combinations and Bit String help

Question

I have a 15 bit string, and I want to find how many combinations there are where there are no consecutive two 0's in a row. If I'm interpreting this right, combinations of 001001001001001 and 101010101010101 are valid, but combinations such as 000010101010101 are not. Am I going about this right? I'm looking for guidance rather than answers.

Answer 1

If you try to take out all combinations that would make it fail it is much easier. For this example imagine an 8 bit string. $$00001111$$ What surrounds $0000$ does not matter therefore you can have any combination for the remaining 4 bits that aren't the $0000$, to figure out the amount of combinations that would be possible around the $0000$ we do $2^4$. Now however imagine we shift the $0000$ to the right $$11100001$$ Now any changes to the right which include a $0$ will be accounted for therefore only the possibility of a $1$ laying to the $0000$ right is not accounted for, thereby we calculate the amount of possibility's to the left of $0000$ we have $2^3$. now imagine we shift the $0000$ to the right again. $$11000011$$ As you can see we have accounted for possibility's apart from if there is $11$ to the right of the $0000$ therefore the amount of combinations that include $000011$ at the leftmost bits is $2^2$

If we were to continue this you get:$$2^0+2^1+2^2+2^3+2^4=\sum_{n=0}^4{2^n}$$ So to figure out the amount of invalid possibility's you can use: $$\sum_{n=1}^m{2^n}$$ Where m is the length of your bit string minus $4$.

Now that you know all combinations that would be rejected, you can calculate all possible combinations, valid or invalid, using $2^k$ where $k$ is the length of your string. Subtract invalid possibility's from all possibility's to obtain the amount of valid combinations, in this case: $$2^8 - (\sum_{n=0}^42^n) = 256 - 31 = 225$$