Derive a recurrence relation for the numbers wn justify it

Question

Problem:

Let Wn be the number of strings of length n formed from letters A, B, C, and D that do notncontain a substring AA, BA or CA.

For example, for n = 2, all the strings with this property are AB, AC, AD, BB, BC, BD, CB, CC, CD, DA, DB, DC, DD and thus W₂ = 13. (Note that W₀ = 1, because the empty string satisfies the condition.)

(a) Derive a recurrence relation for the numbers Wn. Justify it.

(b) Find the formula for the numbers Wn by solving this recurrence. Show your work.