How many $n$-words from $A,B,C$ if no two adjacent A's and no two B's are allowed 
How many $n$-words from $A,B,C$ if no two adjacent A's and no two B's are allowed

I am trying to solve this task in use of recursion:
$C_n$ number of $n-words$ which ends with $C$. Similar for $B_n$ and $C_n$
Let see that $A_n= B_n$ so:
$$C_n = C_{n-1} + 2 A_{n-1} \wedge A_n = A_{n-1} + C_{n-1} $$
In use of Iverson's notation I want to fill edge cases:
$$C_n = C_{n-1} + 2 A_{n-1} - 2[n=1] \wedge A_n = A_{n-1} + C_{n-1} - [n=1] $$
Multiplying by $x^n$ I get generating functions:
$$C(x) = xC(x) + 2xA(x) - 2x \wedge A(x)= xA(x) + xC(x) - x $$
We got $$ A(x) = -\frac{-x^2-x}{x^2+2 x-1}, C(x)= \frac{2 x}{x^2+2 x-1}$$
but when I do long division of these terms I got contradiction.
 A: Your generating functions are nearly correct: they are negatives of what they should be, and you have $C_n$ and $A_n$ swapped. The reason that they are negatives of what they should be is that in

$$C_n = C_{n-1} + 2 A_{n-1} - 2[n=1] \text{ and } A_n = A_{n-1} + C_{n-1} - [n=1]$$

you are for some reason subtracting the Iverson brackets instead of adding them. The reason that they are swapped is that the $2$ and $1$ are swapped (we want $A_1 =2$ and $C_1 = 1$, not $C_1 = 2$ and $A_1=1$). Maybe this is one mistake and maybe this is two mistakes, but either way, here is how you should think this through to get the correct terms.
Consider: by default, in generating functions, you will have $A_{-1} = C_{-1} = 0$. By making your base case $n=1$, you have decided that $A_0 = C_0 = 0$ as well. (This is debatable, but we can roll with it.) So without the Iverson brackets, you would have $C_1 = C_0 + 2A_0 = 0$ instead of $C_1 =1$, and $A_1 = A_0 + C_0 = 0$ instead of $A_1 = 2$.
We want to fix this at the $n=1$ stage, so we write $C_n = C_{n-1} + 2A_{n-1} + [n=1]$, and $A_n = A_{n-1} + C_{n-1} + 2[n=1]$ instead. This gives us $C_1 = C_0 + 2A_0 + 1 = 1$ and $A_1 = A_0 + C_0 + 2 = 2$, as desired. The other steps of the recurrence are unaffected.

My personal opinion is that the correct place to fix the recurrence is at the $n=0$ stage instead. Here, we want to figure out what the right values of $A_0$ and $C_0$ are. There is only one word of length $0$: the empty word. Does it end with $A$, $B$, or $C$? That's awkward to answer: but since you can append $A$ or $B$ to the empty word without violating the restriction, we should say that the empty word ends in $C$.
Therefore the initial conditions should be $C_0 = 1$ and $A_0 = 0$ and you can work with the slightly simpler recurrence
$$C_n = C_{n-1} + 2 A_{n-1} + [n=0] \text{ and } A_n = A_{n-1} + C_{n-1}.$$
This won't give you the same generating functions, but the answer will agree with yours in all coefficients except for the coefficient of $x^0$. (So the answer will be the same up to a constant term.)
