Recurrence relations - binary substrings Let $S_n$ be the number of binary strings of length = $n$ which do not contain the sub-string $010$.
Find a recurrence relation for $S_n$.
edit:
I tried for $n=4$. There are two positions in string, how to place $010$. 
[]010 or 010[] ... so last place is choosen from 2 possible numbers -> $2^1$ and multiplied by $2!$ because of permutation of two items.
Number of all strings is $2^4$.
Number of string with $010$ for $n=4$ is $2^1*2! = 4$.
Result is 12 strings doesn't containt substring.
It is ok for $n=3$ but failed for $n=5$.
 A: The comment at the OEIS entry looks pretty easy to me. Maybe this is a tiny bit simpler. 
Any such string must end in exactly one of the following: 1; 110; 1100; 11000; etc. 
So $$a_n=a_{n-1}+a_{n-3}+a_{n-4}+a_{n-5}+\cdots$$
Now replace $n$ everywhere with $n-1$, and subtract the  new equation from the old one. 
EDIT: Maybe I should expand on this somewhat. 
Suppose we have a string of length $n$ with no 010. It could end in 1. In that case, it's a string of length $n-1$ with no 010, with a 1 tacked on at the end. There are $a_{n-1}$ such things. 
Or, it could end in a 0. In that case, it might end in any number of zeros. If it isn't all zeros, then it ends in a 1 followed by those ending zeros, and it can't end in 01 followed by those zeros (since that would give a 010), so it must end in 11 then zeros; it must end in 110, or 1100, or 11000, etc., etc. 
If it ends in 110, it's a sequence of length $n-3$ with no 010, with 110 tacked on at the end; the number of these is $a_{n-3}$. 
If it ends in 1100, it's a sequence of length $n-4$ with no 010, with 1100 tacked on at the end; there are $a_{n-4}$ of these. 
And so on. So we get $$a_n=a_{n-1}+a_{n-3}+a_{n-4}+a_{n-5}+\cdots$$ 
But $n$ is arbitrary. Replacing it with $n-1$ everywhere, we get $$a_{n-1}=a_{n-2}+a_{n-4}+a_{n-5}+a_{n-6}+\cdots$$ 
Now subtracting the last equation from the one before, we get $$a_n-a_{n-1}=a_{n-1}-a_{n-2}+a_{n-3}$$ All the other terms cancel. So we are left with the recurrence, $$a_n=2a_{n-1}-a_{n-2}+a_{n-3}$$ 
Let's check it. It's easy to see $a_1=2,a_2=4,a_3=7$. Also, $a_4=12$, because there are 16 strings of length 4 of which we must omit 4, namely, 0100, 0101, 0010, and 1010. Putting $n=4$ into the formula yields $$12=(2)(7)-4+2$$ which is correct, so maybe the answer is right. 
A: From http://oeis.org/A000253:

$a_n = 2a_{n-1}-a_{n-2}+a_{n-3}+2^{n-1}$
...
number of binary strings of length $n+2$ containing the pattern $010$

And subtract.
A: It is easier to set up computing the number of strings that do contain $010$, and subtract from $2^n$, the total.
To do the above, you have four cases: Strings that already contain $010$, can extend them in any way; strings that don't contain $010$ are of three types: need to add $010$, adding $1$ have one of the same; end in $0$, still require $10$ (add $0$, get one of these); end in $01$, need $0$ (add $1$, you are back at the "still missing $010$" case). So you can set up a system of recurrences and solve.
Computer Science types will recognize this as the construction of a deterministic finite automaton.
