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

Question

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 :)

Answer 1

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}$.