# 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$.

-
I've tried use combinatorics to determine how many string containt this substring and then subtract. – Ondrej Janacek Nov 28 '11 at 20:09
Please edit your question to show some of this work, and some thoughts about how that would have led to a recurrence relation. – Henning Makholm Nov 28 '11 at 20:12
Ok, check my question again, it is edited. – Ondrej Janacek Nov 28 '11 at 20:24

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.

-
+1. You omitted the case it's all $0$s. This adds $1$ to each of $a_n$ and $a_{n-1}$, which then cancel, yielding the same result. You also omitted the case the string is $100$: how to deal with that? – msh210 Nov 30 '11 at 18:18
@msh210, you are right, I have been careless. For every $n$, there is the string of $n$ zeros, and also the string with a 1 followed by $n-1$ zeros. So it should be $a_n=2+a_{n-1}+a_{n-3}+\cdots$ (except when $n=1$; then $a_1=1+a_0$), but as in your comment the $+2$ cancels when we do $a_n-a_{n-1}$. – Gerry Myerson Dec 1 '11 at 5:53

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

-
This answer assumes the asker is actually seeking a recurrence relation: it provides one. If, OTOH, the asker is actually seeking help with homework (as I suspect), then he'll (presumably) need to explain why the recurrence relation holds. In that case, he can check the proof in the OEIS comment. – msh210 Nov 28 '11 at 20:11
I do not need help with homework, I just missed last seminar and I have absolutely no idea, how to solve problem like this. – Ondrej Janacek Nov 28 '11 at 20:14
@Andrew: Like I said: the OEIS comment indicates how to do so. – msh210 Nov 28 '11 at 20:16
I think there should be easier solution. Still, it is first example from seminar. Second is much more complicated. – Ondrej Janacek Nov 28 '11 at 20:37

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.

-