Hello and happy new year.
I've been struggling with this question and I really need some help.
The question is, find a recurrence relation that demonstrates how many words of length $n$ can we write with the letters $\{1,2,3,4\}$ such that the difference between 2 adjacent letters is 1?
For example, 121232 is valid
121323 is not.
Clarification: I'm not asking for a direct answer. I'm looking for something like $f(n) = f(n-1)+2f(n-2)$, where $f(n)$ represents the number of valid words of length $n$.
A hint:
Denote by $f(n)$ the number of words of length $n$ ending in $2$ or $3$, and by $g(n)$ the number of words of length $n$ ending in $1$ or $4$. Then $$f(n+1)=g(n)+f(n),\quad g(n+1)=f(n)\ .$$