Finding a recurrence for $t_n$ that holds true for a set of integers

Question

I know the answer but I have no idea how to explain it

Question A $t_3 =$ ['aaa', 'abb', 'acc', 'bba', 'cca'] ($5$ elements)

$t_4 =$ ['aaaa', 'aabb', 'aacc', 'abba', 'acca', 'bbaa', 'bbbb', 'bbcc', 'ccaa', 'ccbb', 'cccc'] ($11$ elements)

$t_5 =$ ['aaaaa', 'aaabb', 'aaacc', 'aabba', 'aacca', 'abbaa', 'abbbb', 'abbcc', 'accaa', 'accbb', 'acccc', 'bbaaa', 'bbabb', 'bbacc', 'bbbba', 'bbcca', 'ccaaa', 'ccabb', 'ccacc', 'ccbba', 'cccca'] ($21$ elements)

$t_6 = 43$ elements

From handwriting a tonne of permutations, I know that the recurrence is: $t_n = t_{n-1} + 2t_{n-2}$

What is the correct way to explain why my recurrence gives $t_n$?

Answer 1

To make a string of length $n$ you can start with a string of length $n-1$ and add an $a$, or you can start with a string of length $n-2$ and add $bb$ or $cc$. Every string of length $n$ is accounted for this way and no string is counted twice.

Answer 2

The key idea in a question of recursion, is that one may form legal words, by attaching legal phrases (as prefix/suffix) to already legal words of smaller length. This helps in the calculation.

For example, it is easy to see that every legal word of length $n$ must end with either $a$ or $bb$ or $cc$, because otherwise we would have a problem with the regulations of the question. For example, if it ended with $ab$, say, then the phrase $"ab"$ must be the suffix of a legal phrase, or $"b"$ must be a legal phrase alone, neither of which is the case (and similarly one may argue for all other illegal phrases of length two).

Therefore, every legal word of length $n > 2$ arises in exactly one of these ways:

• Taking a legal word of length $n-1$ and adding an $a$ at the end.

• Taking a legal word of length $n-2$ and adding a $bb$ at the end.

• Taking a legal word of length $n - 2$ and adding a $cc$ at the end.

Now you see the answer : $t(n) = t(n-1) + 2t(n-2)$, since the number of ways in which the first case occurs is $t(n-1)$ and the number of ways in which the second and third cases occur is $t(n-2)$. Furthermore, exactly one of the cases always occurs.

Of course, this approach also lets you make words. So say you want all four letter legal words. Take all three letter legal words and add an $a$ at the end, and then take all two letter legal words and add a $bb$ at the end , then $cc$ at the end to give the complete list.