# Find a recurrence relation for the number of strings of length $n$ over $\{1,2,3,4,5\}$ such that :

For $$n\in\mathbb{N^+}$$ we'll denote $$a_n$$ as the number of strings of length $$n$$ over $$\{1,2,3,4,5\}$$ such that the sum of each 2 adjacent characters is not divisible by 3.

Find a recurrence relation of the sequence $$a_n$$. Then, find a closed form of $$a_n$$ for all $$n\ge 1$$

Hey everyone. So I understand that the sequences that are not allowed are $$12, 15$$ | $$21 , 24$$ | $$33$$ | $$42,45$$ | $$51,54$$ . So there is symmetry and the only case which is different is when the sequence starts with a 3. So I define $$b_n$$ as the number of eligible strings that start with a 3. Now I'm quite lost.. Would be happy to get your help. Thanks in advance :)

Let $b_n$ be the number of valid strings ending with $3$, and $c_n$ be the number of valid strings not ending with $3$.

Suppose you have a box of all the $b_n$ strings, and a box of all the $c_n$ strings. How do you make the $b_{n+1}$ strings ending with $3$, and how do you make the other $c_{n+1}$ strings?

Each of the $c_n$ strings can be turned into a $b$-string by adding $3$; there is no other way to make a $b$-string. Thus $b_{n+1}=c_n$. Meanwhile, four new $c$-strings can be made out of each old $b$-string, and two out of each old $c$-string. Thus $c_{n+1}=4b_n+2c_n=2c_n+4c_{n-1}$.

Finally, $a_n=b_n+c_n=c_n+c_{n-1}$. It follows that $a_n$ follows the same rule as $c_n$; that is, $a_n=2a_{n-1}+4a_{n-2}$.