Exercise 16.

A ternary string is a sequence of 0's, 1's and 2's. Just like a bit string, but with three symbols.

Let's call a ternary string good provided it never contains a 2 followed immediately by a 0. Let \(G_n\) be the number of good strings of length \(n\text{.}\) For example, \(G_1 = 3\text{,}\) and \(G_2 = 8\) (since of the 9 ternary strings of length 2, only one is not good).

Find, with justification, a recursive formula for \(G_n\text{,}\) and use it to compute \(G_5\text{.}\)

Hint.
in-context