I have some question integrating between combinatorics and recursive formulas.

Generally, I have some difficulty with the concept of recursion, as well as with the recursion in programming unfortunately.

I have some question to solve, and maybe you can guide me:

Find a recursive formula and a terminal condition for the number of words with the length 'n' that can be written by $A, B, C$, such that these combinations won't be shown: $AB, AC, BA, BC$.

Now, I know that if we start from $A$ or $B$ we of course have one option, 'n' $A's$, 'n' $B's$ - which are two combinations.

Now, if we start from $C$, I understand we have more 'n-1' letters to write such that we don't write the illegal ones.

I know that means we have $a_{n-1}$ combinations after $C$.

But that is what I don't understand, what is that $a_{n-1}$, how do we know it really contains only the legal combinations?

I wold love to get some sense of this concept.

Thanks.