Recurrence relations of strings?

Question

I am having a problem with understanding where I went wrong in solving the following recurrence relations problem:

Let S be the set of strings on the alphabet {0, 1, 2, 3} 
that do not contain 12 or 20 as a substring. 
Give a recursion for the number t(n) of strings in S of length n.

My reasoning:

Strings end in either: 0 1 2 3
0 -> 00 10 20 30 (20 is a problem, so we have t(n-1) - t(n-2))
1 -> 01 11 21 31 (all are good, so t(n-1))
2 -> 02 12 22 32 (12 is a problem, so we have t(n-1) - t(n-2))
3 -> 03 13 23 33 (all are good so t(n-1))
Therefore, the answer should be 4t(n-1) - 2t(n-2)

Why does the solution manual state that it is 4t(n-1)-2t(n-2)+t(n+3)? I have no idea where the last part came from.

Answer 1

Your first case, strings ending in $0$, is the source of the error: the actual count is

$$t(n-1)-\big(t(n-2)-t(n-3)\big)=t(n-1)-t(n-2)+t(n-3)\;.$$

You can see why if you look at the third case, strings ending in $2$: there aren’t $t(n-2)$ strings of length $n-1$ ending in $2$, but rather only $t(n-2)-t(n-3)$, because the substring $12$ is ruled out.