How many sequences can be made with 5 digits so that the difference between any two consecutive digits is $1$? Using the digits $0$, $1$, $2$, $3$, and $4$, how many ten-digit sequences can be written so that the difference between any two consecutive digits is $1$?
I was wondering if my solution is right.
Let  $a(n)$ be the number of $n$ digit sequences that end with $0$ or $4$ so that the difference between any two consecutive digits is $1$.
$b(n)$ be the number of n digit sequences that end with $1$ or $3$ so that the difference between any two consecutive digits is $1$.
$c(n)$ be the number of n digit sequences that end with $2$ so
that the difference between any two consecutive digits is $1$.
$x(n)$ be the number of n digit sequences so that the difference between any two consecutive digits is $1$.
$x(n) = a(n) + b(n) + c(n)$
$a(n) = b(n-1)$
$b(n) = a(n-1) + 2c(n-1)$
$c(n) = b(n-1)$
By substituting $a(n-1)$ and $c(n-1)$ in the formula for $b(n)$ we get $b(n) = 3b(n-2)$
We know that $b(1) = 2, b(2) = 4$.
The characteristic equation for this recursion is $x^2-3 = 0$ with have the roots $3^{1/2}$ and $-3^{1/2}$, so $b(n) = A{(3^{1/2})}^{n} + B{(-3^{1/2})}^{n}$ where $A = {(3^{1/2}+2)}/{3}$ and $B = {(2-3^{1/2})}/{3}$. I think this is an integer.
We get $x(n) = 2b(n-1) + 3b(n-2)$ and by substituting we get something.


here is your answer. Your approach was absolutely correct.
