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.