How many sequences can be made with 5 digits so that the difference between any two consecutive digits is $1$?

Question

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.

Answer 1

Your approach looks good to me but you have to check the final result somehow. You can do that with 15 lines of code:

#include <iostream>
using namespace std;

int count(int startDigit, int length) {
    if(startDigit < 0 || startDigit > 4) {
        return 0;
    }
    if(length == 1)
        return 1;
    return count(startDigit - 1, length - 1) + count(startDigit + 1, length - 1);
}

int main() {
    cout << count(1, 10) + count(2, 10) + count(3, 10) + count(4, 10);
}

...and the result is 567.

Answer 2

here is your answer. Your approach was absolutely correct.

Answer 3

Your approach is correct, with the above 2 relations mentioned by you: $$a(n) = b(n-1) = c(n)$$ $$b(n) = a(n-1) + 2c(n-1)$$ we can easily get the relation $$x(n)=3x(n-2)$$ Hence $x(10) = 3x(8) = 3^2 x(6) =...= 3^4 x(2)$, where $x(2) = 8$. So, the answer to your question would be $2^3 3^4 = \boldsymbol{648}$