Question:
Let $\Sigma =\{1,2,3,4\}$. For $n\ge 1,$ let $S_n$ be the set of all words above $\Sigma$ in which each adjacent chars are different and the last char isn't the same as the first char. E.g.: $3231234\in S_7$. Let $y_n=|S_n|$. Find the recursive function with starting conditions for $y_n$.
$Solution.$ we shall take all calculations around the third char of the string since it is possible to take a smaller string to satisfy the conditions from there.
If the third char is as the last: then the second char is different from the last, therefore, we have: $y_{n-1}$.
If the third char isn't equal to the last: then we can take the sub-word starting with the third char and for that: $3\cdot y_{n-2}$.
In total, $$y_n=y_{n-1}+3y_{n-2},y_1=4,y_2=12$$
I don't know if the solution is correct. I will be glad if you show me how to approach such questions. Thanks!