19. Find a recurrence for the number of strings using the letters a,b,c,d that do not have "cd" nor "dd" in them. (Hint: start at the end.) - Rhea

You can do this by realizing that if the last letter is an a, b, or c you have a_n-1 choices for the first n-1 letters. However, if the last letter is d, you do not want cd or dd, so you can either have an a for the second letter or a b, and after that you have a_n-2 choices for strings. Therefore the recursion is a_n = 3 a_n-1 + 2 a_n-2