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
- Karen Midterm Practice Questions
