Let an equal the number of ternary strings of length n made up of Os, .ls, and 2s, such that the substrings 00, 01, 10, and 11 never occur. Prove that an = an-l + 2an-2, (n 2: 2), with ao = 1 and al =3. Then find a formula for