## A sequence of numbers

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.

## Closed form

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.