Recurrence series with matrix for $a_n=a_{n-1}-2a_{n-2}$

Question

$a_0=0$, $a_1=1$, $a_n=a_{n-1} - 2a_{n-2}$ for $n\ge2$. Find a closed form for $a_n$.

So if I compute $a_2=1-0=1$, $a_3=1-2=-1$: $$\begin{bmatrix} a_n\\a_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & -2 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} a_{n-1} \\ a_{n-2}\end{bmatrix}$$ I think this matrix is true for $n\ge2$. But the idea is to find a matrix that satisfy $n\ge1$?

I can see that $\begin{bmatrix} 1 \\0\end{bmatrix}$ is base case? And if they ask to find general term of $a_n$, I should find expression that satisfy the recurrence or the base case?

I suppose that $\begin{bmatrix} a_n\\a_{n-1} \end{bmatrix} $ = $x_n$ and $\begin{bmatrix} a_{n-1} \\ a_{n-2}\end{bmatrix}=x_{n-1}$

$$x_{n}=Ax_{n-1}$$ $$x_{n-1}=A^{-1}x_n$$ clearly do not satisfy the equation, and what is the purpose of finding a matrix for this problem?

The right pattern is $x_n=A^{n-1}x_1$, I was confused why it has always to be $x_1$ and how can I find it? thanks

Answer 1

So if I compute $a_2=1-0=1$, $a_3=1-2=-1$: $$\begin{bmatrix} a_n\\a_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & -2 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} a_{n-1} \\ a_{n-2}\end{bmatrix}$$

Good start. Now continue that....

$$\begin{align} \begin{bmatrix} a_{n} \\ a_{n - 1} \end{bmatrix} &= \begin{bmatrix} 1 & -2 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} a_{n - 1} \\ a_{n - 2} \end{bmatrix} \\ &= \begin{bmatrix} 1 & -2 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 1 & -2 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} a_{n - 2} \\ a_{n - 3} \end{bmatrix} \\ &= \begin{bmatrix} 1 & -2 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 1 & -2 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 1 & -2 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} a_{n - 3} \\ a_{n - 4} \end{bmatrix} \\ &= \dots \end{align}$$

In summary $$\begin{bmatrix} a_{n + 1} \\ a_{n} \end{bmatrix} = \begin{bmatrix} 1 & -2 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} a_1 \\ a_0 \end{bmatrix}$$

I think this matrix is true for $n\ge2$. But the idea is to find a matrix that satisfy $n\ge1$?

Well lets look at $n=1$:

$$\begin{bmatrix} a_1 \\a_{0} \end{bmatrix} = \begin{bmatrix} 1 & -2 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} a_{0} \\ a_{-1}\end{bmatrix}$$

So the $n = 1$ case is the equation $a_1 = a_{0} - 2a_{-1}$. Since we have no information about $a_{-1}$, this is neither provable nor useful. So $n \ge 2$ is fine.

what is the purpose of finding a matrix for this problem?

Because it let's you reach $$\begin{bmatrix} a_{n + 1} \\ a_{n} \end{bmatrix} = \begin{bmatrix} 1 & -2 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} a_1 \\ a_0 \end{bmatrix}$$ after which you can use all kinds of nice matrix properties to say more things about the sequence. For example, you could diagonalize $\begin{bmatrix} 1 & -2 \\ 1 & 0 \end{bmatrix}$ to get

$$\begin{bmatrix} 1 & -2 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ \frac{2}{1 - \sqrt{-7}} & \frac{2}{1 + \sqrt{-7}} \end{bmatrix} \begin{bmatrix} \frac{1 - \sqrt{-7}}2 & 0 \\ 0 & \frac{1 + \sqrt{-7}}2 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ \frac{2}{1 - \sqrt{-7}} & \frac{2}{1 + \sqrt{-7}} \end{bmatrix}^{-1}$$

so

$$\begin{align} \begin{bmatrix} a_{n + 1} \\ a_{n} \end{bmatrix} &= \left( \begin{bmatrix} 1 & 1 \\ \frac{2}{1 - \sqrt{-7}} & \frac{2}{1 + \sqrt{-7}} \end{bmatrix} \begin{bmatrix} \frac{1 - \sqrt{-7}}2 & 0 \\ 0 & \frac{1 + \sqrt{-7}}2 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ \frac{2}{1 - \sqrt{-7}} & \frac{2}{1 + \sqrt{-7}} \end{bmatrix}^{-1}\right)^n \begin{bmatrix} a_1 \\ a_0 \end{bmatrix} \\ &= \begin{bmatrix} 1 & 1 \\ \frac{2}{1 - \sqrt{-7}} & \frac{2}{1 + \sqrt{-7}} \end{bmatrix} \begin{bmatrix} \frac{1 - \sqrt{-7}}2 & 0 \\ 0 & \frac{1 + \sqrt{-7}}2 \end{bmatrix}^n \begin{bmatrix} 1 & 1 \\ \frac{2}{1 - \sqrt{-7}} & \frac{2}{1 + \sqrt{-7}} \end{bmatrix}^{-1} \begin{bmatrix} a_1 \\ a_0 \end{bmatrix} \end{align}$$

Ugh, this sequence doesn't simplify into anything pretty because of all the complex numbers. But it is a straightforward way of deriving a formula of the form $a_{n} = C_1 \phi^n + C_2 {\varphi}~^n$

Also matrices keep the problem only involving integers instead of complex numbers, so computation is so much nicer.

The right pattern is $x_n=A^{n-1}x_1$, I was confused why it has always to be $x_1$ and how can I find it? thanks

It is a bit cleaner to do $x_{n+1} = A^n x_1$. You use $x_1$ as the base case because $a_1$ and $a_0$ is what you were given in the statement of the problem. You can use any convenient $x$ that you can calculate as the base case, but why not just use the one given to you?

Answer 2

You don't need matrices to solve your equation. The matrix approach for second degree recurrences is useful for determining limits or asymptotics.

This kind of linear equations can be solved as linear differential equations. You need to find two linearly independent solutions to the equation, with this you can write the general solution and then find the coefficients from the initial values.

Try with a solution of the form $a_n:=r^n$ for some non zero constant $r$. Substitution gets

$$r^2-r+2=0,$$

This means that two possible values of $r$ are given by $$r_{\pm}:=\frac{1\pm i\sqrt{7}}{2},$$

I.e. two solutions to your equation are

$$a_n^+ = (r_+)^n, a_n^-=(r_-)^n.$$

General solution can be written as

$$a_n=\alpha a_n^+ + \beta a_n^-$$

for some complex values $ \alpha,\beta$ which you can determine from your initial values.