MHB Find a recursive formula for the number of combinations

[CStudent]

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.

 

[Opalg]

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.

If $a_n$ is the number of permissible words of length $n$, then you have shown that $a_n = 2 + a_{n-1}$. (In fact, there is only one word starting with A, one word starting with B, and $a_{n-1}$ words starting with C.) That is the recursive formula. To complete the definition, you need to add that $a_1 = 3$. I'm guessing that this is what the question means by a terminal condition, though I would call it the initial condition. It simply says that there are three words of length 1, namely A, B and C.

 

[CStudent]

If $a_n$ is the number of permissible words of length $n$, then you have shown that $a_n = 2 + a_{n-1}$. (In fact, there is only one word starting with A, one word starting with B, and $a_{n-1}$ words starting with C.) That is the recursive formula. To complete the definition, you need to add that $a_1 = 3$. I'm guessing that this is what the question means by a terminal condition, though I would call it the initial condition. It simply says that there are three words of length 1, namely A, B and C.

Yes, but I have an obstacle in understanding the concept of the recursion...

Again, I don't understand how we can leap to $a_{n−1}$. Okay, after the first C, we have n-1 places, how does it tells us that has $a_{n−1}$? How do we know what is this $a_{n−1}$ at all?

Thank you.

 

[Opalg]

Yes, but I have an obstacle in understanding the concept of the recursion...

Again, I don't understand how we can leap to $a_{n−1}$. Okay, after the first C, we have n-1 places, how does it tells us that has $a_{n−1}$? How do we know what is this $a_{n−1}$ at all?

Thank you.

If the first letter is a C then there is no restriction on what the next letter can be. In other words, it's exactly equivalent to starting again, but with only $n-1$ places instead of $n$.