Let S,, be the number of strings of length n formed from letters A, B, C that do not contain consecutive pairs of letters CC and AC. For example, for n = 3, all the strings with this property are: AAA, AAB, ABA, ABB, ABC, BAA, BAB, BBA, BBB, BBC, BCA, BCB, CAA, CAB, CBA, CBB, CBC and thus S3 17. (Note that So = 1, because the empty string satisfies the condition.) (a) Derive a recurrence relation for the numbers S. Justify it. (b) Find the formula for the numbers S, by solving this recurrence. Show your work.