In how many sequences of length $n$, the difference between every 2 adjacent elements is $1$ or $-1$?

How do I find a recursion formula to solve the following question:

In how many sequences of length $n$, with elements from $\{{0,1,2,3,4}\}$, the difference between every 2 adjacent elements is $1$ or $-1$?

I've been trying to solve the problem for the last 5 hours maybe, I'm sure that I'm missing something..

This is a problem in combinatorics, and the solution must be by finding a recursion formula for the problem.

best solution I've come so far is that if we say that $a_n$ is the solution to the question, so let's count how many sequences of size $n-1$ there are that meet the requirement, and we complete the first element to make it a sequence of $n$ elements. so for $n-1$ there $a_{n-1}$ sequences, and for each sequence we have $2$ options to choose the first element (one option is to take a plus $1$ number from the number that start the $n-1$ sequence, and the other option to to take a minus $1$ number from the number that start the $n-1$ sequence), only problem as you figured out is that if the $n-1$ sequnce starts with $0$ or $4$ there is only $1$ option left for the first element in the sequnce.. so $a_n=2a_{n-1}$ won't work.

I think that the solution may involve using $2$ or maybe $3$ recursion formulas.

Hope I was clear enough.

Solution 1:

Let $A_n$ be the number of sequences ending at $0$ or $4$, and $B_n$ the number of sequences ending at $1$ or $3$, and $C_n$ the number of sequences ending at $2$. Then

$$ A_{n+1} = B_n\\ B_{n+1} = A_n + 2C_n\\ C_{n+1} = B_n. $$

We conclude immediately that $A_{n+1} = C_{n+1} = B_n$ for all $n\ge 1$, and so

$$B_{n+2} = 3 A_{n+1} = 3 B_n$$

also for $n\ge 1$. Given $A_1 = B_1 = 2$ and $C_1 = 1$, you can take it from here.

Solution 2:

Consider the column vector $V(n) = (v_0(n), v_1(n), v_2(n),v_3(n), v_4(n))^T$, where $V_i(n)$ is the number of such sequences starting with $i$. This satisfies the equation $$V(n+1) = A V(n)$$ where $A$ is a certain $5 \times 5$ matrix. So $V(n) = A^{n-1} V(1)$. Eigenvalues and eigenvectors will be useful...