# Give a recursion for the number h(n) of strings in S of length n.

Let S be the set of strings on the alphabet {0,1,2,3} that do not contain 12 or 20 as a substring.

Solving this I got: $$h(n) = 4h(n-1) - 2h(n-2)$$ with $h(0) = 1, h(1) = 4,h(2) = 14$. When I did h(2) manually I got 14 and when I plugged in the value in the equation I also got 14. Now the problem is when I try to do h(3) manually I get 33 and when I plug it in the equation I get 48. What am I doing wrong?

• What do the funny lines mean? – mvw Feb 10 '16 at 2:46
• It is just something that helps me visualize. The final answer I got from doing that was $$h(n)=4h(n−1)−2h(n−2)$$ – Jason Thapa Feb 10 '16 at 2:51

I get $49$ of length $3$ by hand count. There are $11$ strings ending in $0$ because we subtract $x20$ and $200$. There are $14$ strings ending in each of $1$ or $3$ because to fail the first two characters must be $12$ or $20$. There are $10$ strings ending in $2$ because we subtract $x12, 122, 202$
Let $d(n)$ be the number of good $n$ character strings ending in $0$
Let $e(n)$ be the number of good $n$ character strings ending in $1$
Let $f(n)$ be the number of good $n$ character strings ending in $2$
Let $g(n)$ be the number of good $n$ character strings ending in $3$ $$h(n)=d(n)+e(n)+f(n)+g(n)\\e(n)=g(n)=h(n-1)\\f(n)=d(n-1)+f(n-1)+g(n-1) \\d(n)=d(n-1)+e(n-1)+g(n-1)\\f(n)=h(n-1)-e(n-1)=h(n-1)-h(n-2)\\ d(n)=h(n-1)-f(n-1)=h(n-1)-h(n-2)+h(n-3)\\h(n)=4h(n-1)-2h(n-2)+h(n-3)$$
$$\begin {array} {r | r | r | r | r| r} n&d&e&f&g&h\\ \hline 0&0&0&0&0&1\\1&1&1&1&1&4\\2&3&4&3&4&14\\3&11&14&10&14&49\\4&39&49&35&49&172\\5&137&172&123&172&604\\6&481&604&432&604&2121\\7&1689&2121&1517&2121&7448\\8&5931&7448&5327&7448&26154\\9&20827&26154&18706&26154&91841\\10&73135&91841&65687&91841&322504\\11&256817&322504&230663&322504&1132488\\12&901825&1132488&809984&1132488&3976785\\13&3166801&3976785&2844297&3976785&13964668\\14&11120371&13964668&9987883&13964668&49037590 \end {array}$$