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$.
Best Answer
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.