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)
0 Comments