Find Recursive definition for a $n$ characters string of ${1,2,3,4,5}$ so sum of neighbors digits won't divide by 3

Question

I'm trying to find a Recursive formula for a string to have $n$ characters and be built of the digits ${1,2,3,4,5}$ without having any occurrence where the sum of two neighbors digits can be divided by $3$. For every $n$ I want the formula to give me all the strings with $n$ length that can be built and those rules apply to them.

Answer 1

There are $5$ strings of length $1$ (since in those strings, the single digit has no neighbour).

Now, if a string with more than one digit ends with $1$, the previous digit must have been $1, 3$, or $4$.

If it ends with $2$, the previous digit must have been $2,3,$ or $5$.

If it ends with $3$, the previous digit could have been anything other than $3$.

Similar rules apply for $4$ and $5$. Thus you can draw up a table: $$\quad\text{ ends with}\\\begin{array}{c|ccccc}&1&2&3&4&5\\\hline 1&1&1&1&1&1\\2&3&3&4&3&3\\3\end{array}$$

The first number in the new row must be $3+4+3=10$ because you add the last row's numbers from columns $1,3,$ and $4$.

If you continue the table, a pattern will appear from which you can derive a formula.

Answer 2

Let $a_n$ be the number of valid strings with $n$ characters, and

let $c_n$ be the number of valid strings with $n$ characters which end with a $3$.

Then $c_{n+1}=a_n-c_n\;$ (since a valid string of length $n+1$ which ends in a $3$ is preceded by any valid string ${\hspace 1.5 in}$of length $n$ which does not end in a $3$),

and $a_{n+1}=3a_n+c_n\;$ (since a valid string of length $n$ has 3 possibilities for the next digit, except in the case ${\hspace 1.5 in}$when the last digit is a 3, when there are 4 possibilities);

so substituting $c_n=a_{n+1}-3a_n$ in the first equation gives

$\hspace{.25 in}a_{n+2}-3a_{n+1}=a_n-(a_{n+1}-3a_n)$ or

$\hspace{.25 in}\color{blue}{a_{n+2}=2a_{n+1}+4a_n}$.