How many sequnces 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 recurssion 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)$ – Shubham Johri Dec 18 '18 at 7:26
• thanks, i edited it – Lazar Ionut Radu Dec 18 '18 at 8:06
• Looks correct to me – Shubham Johri 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. here is your answer. Your approach was absolutely correct.