In this problem, a ‘word’ is a string of letters, each of which is A, B, or C.

Question

A word is ‘interesting’ if every letter A must be followed by a B unless the A is
the last letter of the word. Note that there do not have to be any As, however.
For example, the following words are interesting:
BCBC, BCA, CABBCCAB, ABBBA, A
The following words are not interesting:
AAB, AC, ABABAA, ACBA
To make sure this is clear, you should check that there are 7 interesting words
of length 2.
How many interesting words are there of length 10?
One way of doing this is to create a recursively defined sequence. However, you can do this a different way if you prefer.