3.6: An Application to Linear Recurrences

It often happens that a problem can be solved by finding a sequence of numbers \(x_{0}, x_{1}, x_{2}, \dots\) where the first few are known, and subsequent numbers are given in terms of earlier ones. Here is a combinatorial example where the object is to count the number of ways to do something.

Example \(\PageIndex{1}\)

An urban planner wants to determine the number \(x_{k}\) of ways that a row of \(k\) parking spaces can be filled with cars and trucks if trucks take up two spaces each. Find the first few values of \(x_{k}\).

Solution

Clearly, \(x_{0} = 1\) and \(x_{1} = 1\), while \(x_{2} = 2\) since there can be two cars or one truck. We have \(x_{3} = 3\) (the \(3\) configurations are ccc, cT, and Tc) and \(x_{4} = 5\) (cccc, ccT, cTc, Tcc, and TT). The key to this method is to find a way to express each subsequent \(x_{k}\) in terms of earlier values. In this case we claim that

\[\label{eq:recurrenceequation} x_{k+2} = x_k + x_{k+1} \mbox{ for every } k \geq 0 \]

Indeed, every way to fill \(k + 2\) spaces falls into one of two categories: Either a car is parked in the first space (and the remaining \(k + 1\) spaces are filled in \(x_{k+1}\) ways), or a truck is parked in the first two spaces (with the other \(k\) spaces filled in \(x_{k}\) ways). Hence, there are \(x_{k+1} + x_{k}\) ways to fill the \(k + 2\) spaces. This is Equation \ref{eq:recurrenceequation}.

The recurrence in Equation \ref{eq:recurrenceequation} determines \(x_{k}\) for every \(k \geq 2\) since \(x_{0}\) and \(x_{1}\) are given. In fact, the first few values are

\[\begin{array}{cllll} x_0 &=& 1 \\ x_1 &=& 1 \\ x_2 &=& x_0 + x_1 &=& 2 \\ x_3 &=& x_1 + x_2 &=& 3 \\ x_4 &=& x_2 + x_3 &=& 5 \\ x_5 &=& x_3 + x_4 &=& 8 \\ \vdots & &\vdots & & \vdots \end{array} \nonumber \]

Clearly, we can find \(x_{k}\) for any value of \(k\), but one wishes for a “formula” for \(x_{k}\) as a function of \(k\). It turns out that such a formula can be found using diagonalization. We will return to this example later.

A sequence \(x_{0}, x_{1}, x_{2}, \dots\) of numbers is said to be given recursively if each number in the sequence is completely determined by those that come before it. Such sequences arise frequently in mathematics and computer science, and also occur in other parts of science. The formula \(x_{k+2} = x_{k+1} + x_{k}\) in Example \(\PageIndex{1}\) is an example of a linear recurrence relation of length 2 because \(x_{k+2}\) is the sum of the two preceding terms \(x_{k+1}\) and \(x_{k}\); in general, the length is \(m\) if \(x_{k+m}\) is a sum of multiples of \(x_{k}, x_{k+1}, \dots , x_{k+m-1}\).

The simplest linear recursive sequences are of length 1, that is \(x_{k+1}\) is a fixed multiple of \(x_{k}\) for each \(k\), say \(x_{k+1} = ax_{k}\). If \(x_{0}\) is specified, then \(x_{1} = ax_{0}, x_{2} = ax_{1} = a^{2}x_{0}\), and \(x_{3} = ax_{2} = a^{3}x_{0}, \dots\). Continuing, we obtain \(x_{k} = a^{k}x_{0}\) for each \(k \geq 0\), which is an explicit formula for \(x_{k}\) as a function of \(k\) (when \(x_{0}\) is given).

Such formulas are not always so easy to find for all choices of the initial values. Here is an example where diagonalization helps.

Example \(\PageIndex{2}\)

Suppose the numbers \(x_{0}, x_{1}, x_{2}, \dots\) are given by the linear recurrence relation

\[x_{k+2} = x_{k+1} +6x_k \mbox{ for } k \geq 0 \nonumber \]

where \(x_{0}\) and \(x_{1}\) are specified. Find a formula for \(x_{k}\) when \(x_{0} = 1\) and \(x_{1} = 3\), and also when \(x_{0} = 1\) and \(x_{1} = 1\).

Solution

If \(x_{0} = 1\) and \(x_{1} = 3\), then

\[x_{2} = x_{1} + 6x_{0} = 9, \quad x_{3} = x_{2} + 6x_{1} = 27, \quad x_{4} = x_{3} + 6x_{2} = 81 \nonumber \]

and it is apparent that

\[x_k = 3^k \mbox{ for } k = 0, 1, 2, 3, \mbox{ and } 4 \nonumber \]

This formula holds for all \(k\) because it is true for \(k = 0\) and \(k = 1\), and it satisfies the recurrence \(x_{k+2} = x_{k+1} + 6x_{k}\) for each \(k\) as is readily checked.

However, if we begin instead with \(x_{0} = 1\) and \(x_{1} = 1\), the sequence continues

\[x_{2} = 7, \quad x_{3} = 13, \quad x_{4} = 55, \quad x_{5} = 133, \quad \dots \nonumber \]

In this case, the sequence is uniquely determined but no formula is apparent. Nonetheless, a simple device transforms the recurrence into a matrix recurrence to which our diagonalization techniques apply.

The idea is to compute the sequence \(\mathbf{v}_{0}, \mathbf{v}_{1}, \mathbf{v}_{2}, \dots\) of columns instead of the numbers \(x_{0}, x_{1}, x_{2}, \dots,\) where

\[\mathbf{v}_k = \left[ \begin{array}{c} x_k \\ x_{k+1} \end{array}\right] \mbox{ for each } k \geq 0 \nonumber \]

Then \(\mathbf{v}_0 = \left[ \begin{array}{c} x_0 \\ x_1 \end{array} \right] = \left[ \begin{array}{c} 1 \\ 1 \end{array}\right]\) is specified, and the numerical recurrence \(x_{k+2} =x_{k+1} + 6x_{k}\) transforms into a matrix recurrence as follows:

\[\mathbf{v}_{k+1} = \left[ \begin{array}{c} x_{k+1} \\ x_{k+2} \end{array}\right] = \left[ \begin{array}{c} x_{k+1} \\ 6x_k + x_{k+1} \end{array}\right] = \left[ \begin{array}{rr} 0 & 1 \\ 6 & 1 \end{array}\right] \left[ \begin{array}{c} x_k \\ x_{k+1} \end{array}\right] = A \mathbf{v}_k \nonumber \]

where \(A = \left[ \begin{array}{rr} 0 & 1 \\ 6 & 1 \end{array}\right]\). Thus these columns \(\mathbf{v}_{k}\) are a linear dynamical system, so Theorem 3.5.1 applies provided the matrix \(A\) is diagonalizable.

We have \(c_{A}(x) = (x -3)(x + 2)\) so the eigenvalues are \(\lambda_{1} = 3\) and \(\lambda_{2} = -2\) with corresponding eigenvectors \(\mathbf{x}_1 = \left[ \begin{array}{c} 1\\ 3 \end{array}\right]\) and \(\mathbf{x}_2 = \left[ \begin{array}{r} -1\\ 2 \end{array}\right]\) as the reader can check. Since \(P = \left[ \begin{array}{cc} \mathbf{x}_1 & \mathbf{x}_2 \end{array}\right] = \left[ \begin{array}{rr} 1 & -1 \\ 3 & 2 \end{array} \right]\) is invertible, it is a diagonalizing matrix for \(A\). The coefficients \(b_{i}\) in Theorem 3.5.1 are given by \(\left[ \begin{array}{c} b_1 \\ b_2 \end{array} \right] = P^{-1} \mathbf{v}_0 = \left[ \def\arraystretch{1.25}\begin{array}{r} \frac{3}{5} \\ \frac{-2}{5} \end{array}\right]\), so that the theorem gives

\[\left[ \begin{array}{c} x_k \\ x_{k+1} \end{array}\right] = \mathbf{v}_k = b_1 \lambda_1^k \mathbf{x}_1 + b_2 \lambda_2^k \mathbf{x}_2 = \frac{3}{5} 3^k \left[ \begin{array}{c} 1 \\ 3 \end{array}\right] + \frac{-2}{5} (-2)^k \left[ \begin{array}{r} -1 \\ 2 \end{array}\right] \nonumber \]

Equating top entries yields

\[x_k = \frac{1}{5} \left[ 3^{k+1} - (-2)^{k+1} \right] \mbox{ for } k \geq 0 \nonumber \]

This gives \(x_{0} = 1 = x_{1}\), and it satisfies the recurrence \(x_{k+2} = x_{k+1} + 6x_{k}\) as is easily verified. Hence, it is the desired formula for the \(x_{k}\).

Returning to Example \(\PageIndex{1}\), these methods give an exact formula and a good approximation for the numbers \(x_{k}\) in that problem.

Example \(\PageIndex{3}\)

In Example \(\PageIndex{1}\), an urban planner wants to determine \(x_{k}\), the number of ways that a row of \(k\) parking spaces can be filled with cars and trucks if trucks take up two spaces each. Find a formula for \(x_{k}\) and estimate it for large \(k\).

Solution

We saw in Example \(\PageIndex{1}\) that the numbers \(x_{k}\) satisfy a linear recurrence

\[x_{k+2} = x_k + x_{k+1} \mbox{ for every } k \geq 0 \nonumber \]

If we write \(\mathbf{v}_k = \left[ \begin{array}{c} x_k \\ x_{k+1} \end{array}\right]\) as before, this recurrence becomes a matrix recurrence for the \(\mathbf{v}_{k}\):

\[\mathbf{v}_{k+1} = \left[ \begin{array}{c} x_{k+1} \\ x_{k+2} \end{array}\right] = \left[ \begin{array}{c} x_{k+1} \\ x_k + x_{k+1} \end{array}\right] = \left[ \begin{array}{rr} 0 & 1 \\ 1 & 1 \end{array}\right] \left[ \begin{array}{c} x_k \\ x_{k+1} \end{array}\right] = A \mathbf{v}_k \nonumber \]

for all \(k \geq 0\) where \(A = \left[ \begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array}\right]\). Moreover, \(A\) is diagonalizable here. The characteristic polynomial is \(c_{A}(x) = x^{2} - x - 1\) with roots \(\frac{1}{2} \left[ 1 \pm \sqrt{5} \right]\) by the quadratic formula, so \(A\) has eigenvalues

\[\lambda_1 = \frac{1}{2} \left( 1 + \sqrt{5} \right) \mbox{ and }\lambda_2 = \frac{1}{2} \left( 1 - \sqrt{5} \right) \nonumber \]

Corresponding eigenvectors are \(\mathbf{x}_1 = \left[ \begin{array}{c} 1 \\ \lambda_1 \end{array}\right]\) and \(\mathbf{x}_2 = \left[ \begin{array}{c} 1 \\ \lambda_2 \end{array}\right]\) respectively as the reader can verify. As the matrix \(P = \left[ \begin{array}{cc} \mathbf{x}_1 & \mathbf{x}_2 \end{array} \right] = \left[ \begin{array}{cc} 1 & 1 \\ \lambda_1 & \lambda_2 \end{array} \right]\) is invertible, it is a diagonalizing matrix for \(A\). We compute the coefficients \(b_{1}\) and \(b_{2}\) (in Theorem 3.5.1) as follows:

\[\left[ \begin{array}{c} b_1 \\ b_2 \end{array}\right] = P^{-1} \mathbf{v}_0 = \frac{1}{-\sqrt{5}} \left[ \begin{array}{rr} \lambda_2 & -1 \\ -\lambda_1 & 1 \end{array} \right] \left[ \begin{array}{c} 1 \\ 1 \end{array}\right] = \frac{1}{\sqrt{5}} \left[ \begin{array}{r} \lambda_1 \\ -\lambda_2 \end{array}\right] \nonumber \]

where we used the fact that \(\lambda_{1} + \lambda_{2} = 1\). Thus Theorem 3.5.1 gives

\[\left[ \begin{array}{c} x_k \\ x_{k+1} \end{array}\right] = \mathbf{v}_k = b_1 \lambda_1^k \mathbf{x}_1 + b_2 \lambda_2^k \mathbf{x}_2 = \frac{\lambda_1}{\sqrt{5}} \lambda_1^k \left[ \begin{array}{c} 1\\ \lambda_1 \end{array}\right] - \frac{\lambda_2}{\sqrt{5}} \lambda_2^k \left[ \begin{array}{c} 1 \\ \lambda_2 \end{array}\right] \nonumber \]

Comparing top entries gives an exact formula for the numbers \(x_{k}\):

\[x_k = \frac{1}{\sqrt{5}} \left[ \lambda_1^{k+1} - \lambda_2^{k+1} \right] \mbox{ for } k \geq 0 \nonumber \]

Finally, observe that \(\lambda_{1}\) is dominant here (in fact, \(\lambda_{1} = 1.618\) and \(\lambda_{2} = -0.618\) to three decimal places) so \(\lambda_2^{k+1}\) is negligible compared with \(\lambda_1^{k+1}\) is large. Thus,

\[x_k \approx \frac{1}{\sqrt{5}} \lambda_1^{k+1} \mbox{ for each } k \geq 0. \nonumber \]

This is a good approximation, even for as small a value as \(k = 12\). Indeed, repeated use of the recurrence \(x_{k+2} = x_{k} + x_{k+1}\) gives the exact value \(x_{12} = 233\), while the approximation is \(x_{12} \approx \frac{(1.618)^{13}}{\sqrt{5}} = 232.94\).

The sequence \(x_{0}, x_{1}, x_{2}, \dots\) in Example 3.6.3 was first discussed in 1202 by Leonardo Pisano of Pisa, also known as Fibonacci,¹ and is now called the Fibonacci sequence. It is completely determined by the conditions \(x_{0} = 1\), \(x_{1} = 1\) and the recurrence \(x_{k+2} = x_{k} + x_{k+1}\) for each \(k \geq 0\). These numbers have been studied for centuries and have many interesting properties (there is even a journal, the Fibonacci Quarterly, devoted exclusively to them). For example, biologists have discovered that the arrangement of leaves around the stems of some plants follow a Fibonacci pattern. The formula \(x_k = \frac{1}{\sqrt{5}} \left[ \lambda_1^{k+1} - \lambda_2^{k+1} \right]\) in Example 3.6.3 is called the Binet formula. It is remarkable in that the \(x_{k}\) are integers but \(\lambda_{1}\) and \(\lambda_{2}\) are not. This phenomenon can occur even if the eigenvalues \(\lambda_{i}\) are nonreal complex numbers.

We conclude with an example showing that nonlinear recurrences can be very complicated.

Example \(\PageIndex{4}\)

Suppose a sequence \(x_{0}, x_{1}, x_{2}, \dots\) satisfies the following recurrence:

\[x_{k+1} = \left\lbrace \begin{array}{ll} \frac{1}{2} x_k & \mbox{if } x_k \mbox{ is even} \\ 3x_k + 1 & \mbox{if } x_k \mbox{ is odd} \end{array} \right. \nonumber \]

If \(x_{0} = 1\), the sequence is \(1, 4, 2, 1, 4, 2, 1, \dots\) and so continues to cycle indefinitely. The same thing happens if \(x_{0} = 7\). Then the sequence is

\[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, \ldots \nonumber \]

and it again cycles. However, it is not known whether every choice of \(x_{0}\) will lead eventually to 1. It is quite possible that, for some \(x_{0}\), the sequence will continue to produce different values indefinitely, or will repeat a value and cycle without reaching 1. No one knows for sure.

---

1. Fibonacci was born in Italy. As a young man he travelled to India where he encountered the “Fibonacci” sequence. He returned to Italy and published this in his book Liber Abaci in 1202. In the book he is the first to bring the Hindu decimal system for representing numbers to Europe.