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.