Consider the sequence of numbers given by \begin{eqnarray} a_0 & = & 0, \\ a_1 & = & 1, \\ a_n & = & a_{n-1} - 2a_{n-2}~\text{ for } n \geq 2. \end{eqnarray} The first ten terms of this sequence are \[0, 1, 1, -1, -3, -1, 5, 7, -3, -17.\] Could you figure what the value of \(a_{100}\) is?
Certainly, \(a_{100}\) can be found using the recursive definition directly. But doing so requires performing quite a few calculations. A formula that directly computes \(a_k\) given \(k\) would be very appealing.
We now describe how to obtain such a formula. Let \(A = \begin{bmatrix} 1 & -2 \\ 1 & 0\end{bmatrix}\). Let \(x_n = \begin{bmatrix} a_n \\ a_{n-1}\end{bmatrix}\) for \(n \geq 1\). Then \[ Ax_n = \begin{bmatrix} a_n -2 a_{n-1} \\ a_n \end{bmatrix} = \begin{bmatrix} a_{n+1} \\ a_n \end{bmatrix} = x_{n+1}. \] Using this formula, we get that \(x_2 = Ax_1\), \(x_3 = Ax_2 = A(Ax_1)\). In general, \(x_{k} = A^{k-1} x_1\).
Since \(x_1 = \begin{bmatrix} 1 \\ 0\end{bmatrix}\), if we know what the entries in \(A^{k-1}\) are, we will know what \(a_{k+1}\) is exactly. But computing the powers of \(A\) do not seem to be any easier than working with the recursive definition for the sequence.
The magic is to diagonalize \(A\) by writing \(A = PDP^{-1}\) with \(D = \begin{bmatrix} \frac{1+\sqrt{7}i}{2} & 0 \\ 0 & \frac{1-\sqrt{7}i}{2} \end{bmatrix}\) and \(P = \begin{bmatrix} \frac{1+\sqrt{7}i}{2} & \frac{1-\sqrt{7}i}{2} \\ 1 & 1 \end{bmatrix}. \)
Then, \begin{eqnarray} A^2 & = & AA = (PDP^{-1})(PDP^{-1}) = (PD)(P^{-1}P)(DP^{-1}) = (PD)I(DP^{-1}) = P(DD)P^{-1} = PD^2P^{-1} \\ A^3 & = & A^2A = (PD^2P^{-1})(PDP^{-1}) = (PD^2)(P^{-1}P)(DP^{-1}) (PD^2)I(DP^{-1}) = P(D^2D)P^{-1} = PD^3P^{-1} \\ \end{eqnarray} In general, \(A^k = PD^kP^{-1}\). But how does this help us?
Note that \(D^k = \begin{bmatrix} \left(\frac{1+\sqrt{7}i}{2}\right)^k & 0 \\ 0 & \left(\frac{1-\sqrt{7}i}{2}\right)^k \end{bmatrix}.\) (Verify this.)
Using these results, we obtain that \[x_{n+1} = A^n x_1 = PD^nP^{-1}\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} -\frac{i}{\sqrt{7}}\left(\frac{1+\sqrt{7}i}{2}\right)^{n+1} + \frac{i}{\sqrt{7}}\left(\frac{1-\sqrt{7}i}{2}\right)^{n+1} \\ -\frac{i}{\sqrt{7}}\left(\frac{1+\sqrt{7}i}{2}\right)^{n} + \frac{i}{\sqrt{7}}\left(\frac{1-\sqrt{7}i}{2}\right)^{n} \end{bmatrix} \] (The actual calculations have been omitted and are left as an exercise.)
As \(x_{n+1} = \begin{bmatrix} a_{n+1}\\a_n\end{bmatrix}\), we have \(a_n = -\frac{i}{\sqrt{7}}\left(\frac{1+\sqrt{7}i}{2}\right)^{n} + \frac{i}{\sqrt{7}}\left(\frac{1-\sqrt{7}i}{2}\right)^{n} \) for all \(n \geq 1\). Hence, we have \(a_n\) in closed form. One interesting aspect about the formula for \(a_n\) is that it involves complex numbers. Yet every term in the sequence is an integer. This is an example that shows complex numbers are actually quite natural.