Cfrgtkky

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.

EDIT: a little clarification.

We will define $a_k$ to be the number of legal strings of length $k$. So, by definition, $a_{n-1}$ counts the number of legal strings of length $n-1$. The idea of recursion here is to use $a_k$ for smaller values of $k$ (here, $k = n-1$) to get the value for $a_n$. This comes to play in the fact that, if I have any legal string of length $n$, then removing the first letter has to result in a legal string of length $n-1$. Additionally, starting from any legal string of length $n-1$, we can always add $C$ to the beginning to get a legal string of length $n$.

Your observations above are correct. In particular, if the string starts with $A$, it must be the string which only contains $A$'s. Likewise if it starts with $B$; these give exactly $2$ strings. Suppose now that the string starts with $C$. Then the entire $n$-letter string is legal iff the rest of the string is legal, i.e. there are $a_{n-1}$ choices for the rest of the string. This gives us the recurrence:
$$
a_n = a_{n-1} + 2
$$
Finally, it should be clear that $a_1 = 3$ (none of these strings is illegal).

To check that this works, we note that this recurrence gives the closed form $a_n = 2n + 1$. We can count the number of strings directly. If you are familiar with regular expressions, every string is of the form $C^*(A^*|B^*)$, i.e. it starts with all $C$'s, then switches to either all $A$'s or all $B$'s. Such a string of length $n$ can then be constructed in 2 steps: Choose how many $C$'s there are (between $0$ and $n$) and then choose whether the rest of the string is $A$'s or $B$'s. There are $(n+1) cdot 2$ such strings, but actually, if we have $n$ $C$'s, it makes no difference if we choose $A$ or $B$, so we overcounted by one. This gives a total of $2n+1$ strings of length $n$, as desired.