I am given such a problem: Find the number $a_n$ of n-element ternary sequences (composed only of 0s, 1s and 2s), where:
a) There are no repetitions of 1 (two 1s cannot stand next to each other)
b) There are no repetitions of 1 and no repetitions of 2 (two 1s cannot stand next to each other, same for 2s)
I've managed to solve part a and got the following formula: $$a_n = a_n = 2\cdot a_{n-1} + 2\cdot a_{n-2}$$
However, when I attempt to solve part b, I cannot find a way to do it properly. I solved part a by assuming a 1-element sequence, and if the only element is 0 or 2 i can join any proper sequence of length $n-1$, else if the only element is 1, i can join either 0 or 2, and then join any proper sequence of length $n - 2$. Thanks for any help.
I’ll take you through my attack on the problem. As I’ll point out in places, it isn’t the most efficient, but it does illustrate a reasonable approach.
Let $a_n$ be the number of good strings of length $n$, $b_n$ the number of those that end in $0$, $c_n$ the number of them that end in $1$, and $d_n$ the number of them that end in $2$. Clearly $$a_n=b_n+c_n+d_n\;.$$
Since a $0$ can be appended to any good string to get another good string, we must have $b_n=a_{n-1}$. A $1$ can be appended to a good string that ends in $0$ or $2$ to get a good string, so $c_n=b_{n-1}+d_{n-1}=a_{n-2}+d_{n-1}$. Similarly, $$d_n=b_{n-1}+c_{n-1}=a_{n-2}+c_{n-1}\;.$$ Note that $$c_n+d_n=2a_{n-2}+c_{n-1}+d_{n-1}\;;$$ this suggests that we should combine the strings ending in $1$ and $2$ by defining $e_n=c_n+d_n$ and observing that $e_n=2a_{n-2}+e_{n-1}$. We now have only two variables, $a_n$ and $e_n$, with recurrences
$$a_n=b_n+e_n=a_{n-1}+2a_{n-2}+e_{n-1}\tag{1}$$
and
$$e_n=2a_{n-2}+e_{n-1}\;.\tag{2}$$
Here’s where we’ll do something a little tricky. We can rewrite $(1)$ as
$$e_{n-1}=a_n-a_{n-1}-2a_{n-2}$$
and shift the index down $1$ to get
$$e_{n-2}=a_{n-1}-a_{n-2}-2a_{n-3}\;.\tag{3}$$
Shifting the index down in $(2)$ yields $e_{n-1}=2a_{n-3}+e_{n-2}$, which we can combine with $(3)$ to express $e_{n-1}$ entirely in terms of $a_k$s with $k<n$:
$$e_{n-1}=2a_{n-3}+a_{n-1}-a_{n-2}-2a_{n-3}=a_{n-1}-a_{n-2}\;.$$
Now we can substitute this back into $(1)$ to get a recurrence for $a$:
$$a_n=a_{n-1}+2a_{n-2}+a_{n-1}-a_{n-2}=2a_{n-1}+a_{n-2}\;.$$
And this is so simple that it’s worth considering how we might have arrived at it directly. If we have a good string of length $n-1$ that ends in $d$, we can always append one of the two ternary digits different from $d$; that automatically gives us $2a_{n-1}$ good strings of length $n$. If $d=0$, we can also append a $0$. And how many good strings of length $n-1$ end in $0$? One for every good string of length $n-2$, since we could have appended a $0$ to any of them! Had we reasoned that way to begin with, we’d have arrived at the recurrence
$$a_n=2a_{n-1}+a_{n-2}$$
almost immediately.