Develop the the following Recurrence Relation I am attempting to solve the following relation of recurrence:

Knowing that $S_n$ is the number of binary strings of length $n$ that
  does not contain the pattern $111$. Develop the relation of recurrence
  for $S_1, S_2, ..., S_n$ and the initial conditions that defines the
  succession of $S$.

I know that if $n$ is the length of the string and every character could only have two possible values then the number of combinations is $2^n$.
But these types of worded questions are not my strong points. Where do I begin and how do I proceed?
 A: For n > 2, the binary sting with length n either ends with "0", "01" or "011". Hence the recurrence for $S_n$ is:
$$S_n = S_{n-1} + S_{n-2} + S_{n-3}$$
With base cases
$S_0 = 1, S_1 = 2, S_2 = 4$.
Here I tried to divide the answer into several cases, each of which is of smaller length. And that was done by considering the position of the last zero in the string.
A: Sorry, my previous answer answered the wrong question (and was wrong anyway! lol). I shouldnt do math 15 seconds after waking up. Anyway
Since we are developing a recurrence relation, we want to look at how $S_n$ changes compared to a previous $S_n$. Here it's pretty straight forward. If we increase $n$ by one we have twice as many possible strings. We'll still have any string from $S_{n-1}$ that contained a $111$, so we don't need to figure out those again, we just need to figure out what new strings contain a $111$ that didn't before.
Assuming we are adding the bit to the front (it doesnt change the answer if we add it to the back). If that bit is a $0$ obviously we can't be adding any $111$ sequence that we didn't already count. If we add a $1$, now any sequence before that started out $110...$ that didn't already contain a $111$ will now be $1110...$ and now need to be counted. So how many strings of $S_{n-1}$ started $110...$ and don't contain a $111$ arleady?
It's just the number of strings of length $(n-1)-3$ that don't contain a $111$ (since we were looking at strings of length $n-1$ and now we are chopping of the three bits that start $110$). Since any string of length $n-4$ that doesn't contain a $111$ we could now just stick a $110$ in front of and have a string of length $n-1$ that doesn't contains a $111$ which is what we are looking for.
So if we increase $n$ we have twice the total number of strings, and we have to remove from the count the number that was $S_{n-4}$. Thus $S_n = 2S_{n-1} - S_{n-4}$
hopefully thats right this time, heh.
