Recurrence Relation for Bit String Length n with No Consecutive 0s Consider the following:

Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s.

I am trying to understand the solution to this problem, but I am stuck on this line of the solution:

To obtain a recurrence relation for {an}, note that by the sum rule, the number of bit strings of length n that do not have two consecutive 0s equals the number of such bit strings ending with a 0 plus the number of such bit strings ending with a 1. 

I don't understand why this is the case. For example, what if you have a bit string 000, it ends in 0, but has 2 consecutive 0s. 
Could someone help me understand this? 
 A: This is an old question, but the answer might be helpful to someone. Suppose that $a_n$ gives the number of binary sequences of length $n$ without consecutive 0s. Then we can always add 1 to the end of the sequence to make a sequence of length $n+1$ without consecutive zeros. We can only add a 0 to the end if the sequence ends with a 1, but we can add 10 to the end of any sequence without having consecutive zeros. Hence
$$
 a_{n+1}=a_n+a_{n-1},\quad a_0 = 1, a_1 = 2.
$$
A: So, if you read it carefully, you'll see that it says the following:


*

*there is a certain set $S$ of length-$n$ bit strings that don't contain two consecutive 0s

*each $s\in S$ either ends with 0 or with 1

*thus, if $S_1\subset S$ are those ending in 1 and $S_0\subset S$ are those ending in 0, we have $S = S_0\cup S_1$ as a disjoint union

*so, $|S_1| + |S_2| = |S|$

A: Lets give it a shot:

*

*There are $2^n$ bit-strings of length $n.$

*The number of bit-strings with NO 2 consecutive zeroes is $= 2^n -$ (no of bit-strings with consecutive zeroes)

*Suppose string x of length n has consecutive zeroes

*Then for $1\le k \le n-1$, where $k$ is the position of in bit-string $x$, $x(k) = x(k + 1) = 0$
that is the value of the bit in both these positions is $0.$
We are now assured of a bit-string with at least one pair of consecutive zeroes. Further, we have included all bit-strings with more than one pair of consecutive zeroes.


*Since $k$ can be fixed to any of $n-1$ positions


*And each position value $k$ is associated with $2^{n-2}$ different bit-strings.
We have occupied positions k and k+1 with zeroes and have ($n-2$) free variables(positions).


*By the product rule, the number of bit-strings which surely have at least one pair of consecutive zeros is $(n-1) * 2^{n-2}$
It the product of possible choices for k and the number of bit-strings associated with each choice of k.


*Consequently, the number of bit-strings of length n with NO consecutive zeroes is
$2^n - (n-1)*2^{n-2}.$
Any comments! I would like to know if there are faults in the logic.
