Contents

## Problem

Suppose we only use the digits of the set $$A = \{1,2,3,4,5 \}$$. How many numbers of $$n$$ digits can be formed with the set $$A$$, if all adjacent digits differ exactly by $$1$$? We denote the number we are looking for with $$a(n)$$.

Hint
If $$n = 1$$ we have the integers $$1,2,3,4,5$$.
If $$n = 2$$ we have the integers $$12,21,23,32,34,43,45,54$$.
As the number of digits increases, counting becomes complex.
Denote with $$a(n,i)$$ the total of numbers ending with the digit $$i$$. Look for a recurrence equation for $$a (n,1)$$, and then compute $$a(n)$$.

### Solution

The following recurrence equations are obvious:

$\begin{array}{l} a(n,1) = a(n-1,2) \\ a(n,2) = a(n-1,1) + a(n-1,3) \\ a(n,3) = a(n-1,2) + a(n-1,4) \\ a(n,4) = a(n-1,3) + a(n-1,5) \\ a(n,5) = a(n-1,4) \end{array}$

Obviously we have

$a(n) = a(n, 1) + a(n, 2) + a(n, 3) + a(n, 4) + a(n,5)$

We can see that to solve the problem it’s enough to be able to compute the value $$a (n, 1)$$, for each $$n$$. In fact the other values ​​are:

$\begin{array}{l} a(n,5) = a(n,1) \\ a(n,3) = a(n,1) + a(n,5) \\ a(n,2) = a(n-1,1) + a(n-1,3) \\ a(n, 4) = a(n,2) \end{array}$

To calculate the value of $$a (n, 1)$$ we observe that the following relations also apply:

$\begin{array}{l} a(n,3) = 2 \cdot a(n, 1) \quad \text{by symmetry} \\ a(n,1) = a(n-1,2) \\ a(n,1) = a(n-2,1) + a(n-2,3) = 3 \cdot a(n-2,1) \end{array}$

For simplicity we denote by $$x_{n} = a(n, 1)$$. We can therefore write the following recurrence equation:

$x_{n} – 3x_{n-2} = 0$

This is a second order linear finite difference equation. For the methods to solve the recurrences you can see for example [1].

To solve it we have to find the solution of the characteristic equation: $$\lambda ^ {2} – 3 = 0$$. By doing the calculations, you will find:

$x_{n} = A \cdot (\sqrt{3})^{n} + B\cdot (-1)^{n}(\sqrt {3})^{n} = A\cdot 3^{\frac{n}{2}} + B\cdot(-1)^{n} 3^{\frac{n}{2}}$

where $$A, B$$ are two constants to be determined by the initial conditions

$x_{2} = a(2,1) = 1 \quad \text{and} \quad x_{3} = a(3,1) = 2$

By completing the somewhat laborious calculations we obtain the following values ​​for the constants:

$\begin{array}{l} A = \dfrac{3^{\frac{3}{2}} + 6}{6 \cdot 3^{\frac{3}{2}}} \\ \\ B = \dfrac{3^{\frac{1}{2}} -2} {2 \cdot 3^{\frac{3}{2}}} \end{array}$

It’s better to express the final solution by distinguishing the cases of $$n$$ even and $$n$$ odd. Substituting the found values of $$A, B$$ we obtain the following solutions:

$\begin{array}{l} x_{n} = 3^{k-1} \quad (n = 2k) \\ x_{n} = 2 \cdot 3^{k-1} \quad (n = 2k + 1, \quad n \gt 1) \end{array}$

Once the general expression for $$x_{n} = a(n, 1)$$ has been calculated, we can calculate $$a (n)$$ with the formula

$a(n) = a(n,1) + a(n,2) + a(n,3) + a(n,4) + a(n,5)$

and the relationships described above.

## Bibliography

[1]M. Spiegel – Finite differences and difference equations (Schaum’s Outline Series)