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.
 A: 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.
A: 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...
A: Let $a_n$ be the number of such sequences ending in 0 or 4, $b_n$ the number of such sequences ending in 1 or 3, $c_n$ the number of those ending in 2.
The recursion is $a_{n+1}=b_n$, $b_{n+1}=a_n+2c_n$, $c_{n+1}=b_n$ for $n\ge 1$.
It follows that $a_n=c_n$ for $n\ge2$, hence $a_{n+1}=b_n$, $b_{n+1}=3a_n$ for $n\ge 2$. Finally $a_{n+2}=b_{n+1}=3a_n$ for $n\ge 2$.
We compute the fiurst few values: $a_1=2$, $b_1=2$, $c_1=1$, then $a_2=c_2=2$, $b_2=4$, next $a_3=c_3=4$, $b_3=6$.
Using $a_{n+2}=b_{n+1}=3a_n$ for $n\ge 2$, we conclude $a_{2k+2}=3^ka_2=2\cdot 3^k$ and $a_{2k+3} = 3^k a_3 = 4\cdot 3^k$ for $k\in \mathbb N_0$.
Hence $b_{2k+2}=a_{2k+3} =4\cdot 3^k$ and $b_{2k+3} = a_{2k+4} = 6\cdot 3^k$ because $b_n=a_{n+1}$.
What we are actually looking for is $d_n:=a_n+b_n+c_n$.
We find $d_1=5$, $d_2=8$, and for $n\ge 3$,
$$d_n=\begin{cases}14\cdot3^{\frac{n-3}2}&n\mathrm{\ odd}\\8\cdot3^{\frac{n-2}2}&n\mathrm{\ even}\end{cases}.$$
By coincidence, the generic formula is also correct for $d_2$ and almost correct for $d_1$ ($14\cdot3^{\frac{1-3}2}=\frac{14}3\approx 5$).
