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.

• You get $b(n)=3b(n-2)$ Dec 18 '18 at 7:26
• thanks, i edited it
– LIR
Dec 18 '18 at 8:06
• Looks correct to me Dec 18 '18 at 8:14

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.

• I think we should also account for count(0, 10) since it is a sequence and not a number, adding that gives us a result of 648. Jun 22 '21 at 18:44
• Nice touch, thanks! Jun 25 '21 at 13:08 here is your answer. Your approach was absolutely correct.

• $2^3 3^9$ would be the number of 20 digit sequences so that the difference between any two consecutive digits is $1$ i.e. $x(20)$ and not $x(10)$. Jun 22 '21 at 18:23

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}$$