Let S,, be the number of strings of length n formed from letters A, B, C...

 

Transcribed Image Text:

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. 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.