How many bit strings of length $5$ do not have consecutive $1$'s? How many bit strings of length 5 do not have consecutive 1's?
I'm trying to think of a way to calculate how many ways we can arrange a string of length 5 starting with the first position (or index).
I feel like in this case we would use a permutation because order matters. I also believe repetition is not allowed (hence no consecutive 1's) here? Please correct me if I'm going about this wrong. 
 A: We can solve the problem recursively.
Let $a_n$ denote the number of permissible bit strings of length $n$.
A bit string of length $1$ cannot have two consecutive ones.  Since there are two ways to fill the digit, $a_1 = 2$.
The only bit string of length $2$ that has two consecutive ones is $11$.  Since there are two ways to fill each of the two digits in the bit string, $a_2 = 2 \cdot 2 - 1 = 3$.
Any permissible bit string of length $n + 1$ that ends in $0$ can be formed by by appending a $0$ to the end of a permissible bit string of length $n$, of which there are $a_n$.  
For a bit string of length $n + 1$ to end in a $1$, the entry in the $n$th position must be a zero.  Thus, any permissible bit string of length $n + 1$ that ends in a $1$ can be formed by appending the bit string $01$ to a permissible bit string of length $n - 1$, of which there are $a_{n - 1}$.  
Thus, we have the recurrence relation
\begin{align*}
a_1 & = 2\\
a_2 & = 3\\
a_{n + 1} & = a_n + a_{n - 1}, n \geq 2
\end{align*}
You can use the recurrence relation to determine $a_5$, the number of bit strings of length $5$ that do not have two consecutive ones.
A: Listing all binary strings of length $5$ satisfying the condition should work for a problem of this small a size.  Or, you can find the number of binary strings of length $5$ that have consecutive 1's and subtract that number from $32$.  
A: Suppose there are two $1's$ , and so three $0's$,
the two $1's$ can be inserted at the uparrows in $\binom42$ ways, as shown under:
$\uparrow 0 \uparrow 0 \uparrow 0\uparrow\;\;$ which generalizes to $\binom{n-k+1}{k}$ for $k\;\; 1's$
For $n = 5$, $k$ can be $\le3$, thus $$\text{answer}=\sum_{k=0}^3 \binom{6-k}{k}= 13$$
