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 h (n) of strings in S of length n. Hint: Check your recursion by manually computing h (1), h (2), h (3), and h (4).

h (n) = 4h (n - 1) - 2h (n - 2) + h (n - 3)

Step-by-step explanation:

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)

Checking recursion manually,

when h (1) ⇒ d (1) = 1, e (1) = 1, f (1) = 1, g (1) = 1, h (1) = 4

h (2) ⇒ d (2) = 3, e (2) = 4, f (2) = 3, g (2) = 4, h (2) = 14

h (3) ⇒ d (3) = 11, e (3) = 14, f (3) = 10, g (3) = 14, h (3) = 49

h (4) ⇒ d (4) = 39, e (4) = 49, f (4) = 35, g (4) = 49, h (4) = 172

Note:

Sum of the four values gives "h (n)

Since e (n) = g (n), the values are the same