Solve the reccurence $a_n= 4a_{n−1} − 2 a_{n−2}$

Question

Solve the recurrence $a_n = 4a_{n−1} − 2 a_{n−2}$

Not sure how to solve this recurrence as I don't know which numbers to input to recursively solve?

Answer 1

Hint: Let $r_1,r_2$ be two distinct real roots of the equation $$ r^2-4r+2 $$ then this recurrence equation has a solution of the form $$ C_1 r_1^n+C_2 r_2^n $$ which the constants $C_1,C_2$ can be found by initial values condition.

Answer 2

You can make an "educated guess" and propose the following ansatz: $a_n=p^n$. Your recurrence relation now has the following characteristic equation: $$p^2-4p+2=0\Longleftrightarrow (p-2-\sqrt{2})(p-2+\sqrt{2})=0$$ Therefore there are two roots, at $p=2\pm\sqrt{2}$, and we get: $$a_n=\alpha\left(2+\sqrt{2}\right)^n+\beta\left(2-\sqrt{2}\right)^n$$ where $\alpha$ and $\beta$ are constants that can be obtained from the initial conditions. In particular, we have: $$a_0=\alpha+\beta$$ $$a_1=\alpha\left(2+\sqrt{2}\right)+\beta\left(2-\sqrt{2}\right)$$ This is a system of two equations with two unknowns, that we can solve (it's a bit tedious though) to get: $$\beta=\dfrac{a_0\left(2+\sqrt{2}\right)-a_1}{2\sqrt{2}}$$ $$\alpha=a_0-\beta$$ Thus, the explicit expression for $a_n$ is: $$a_n=\alpha\left(2+\sqrt{2}\right)^n+\beta\left(2-\sqrt{2}\right)^n$$ with $\alpha$ and $\beta$ defined above. (And you can check that it indeed verifies the recurrence relation.)

Answer 3

Assume the solution is $a_n = Ar^n$ then you get:

$$ a_n = Ar^n, a_{n - 1} = A \frac{r^n}{r}, a_{n - 2} = A\frac{r^n}{r^2} $$

Plug this into your recursion relation:

\begin{align} a_n = 4a_{n - 1} - 2a_{n - 2}\\ Ar^n = 4A \frac{r^n}{r} - 2A\frac{r^n}{r^2} \\ Ar^n \big(1 - \frac{4}{r} + \frac{2}{r^2}\big) = 0 \\ Ar^n\left(\frac{r^2 - 4r + 2}{r^2}\right) = 0 \\ r^2 - 4r + 2 = 0 \\ r = \frac{4 \pm \sqrt{16 - 8}}{2} = \frac{4 \pm 2\sqrt{2}}{2} = 2 \pm \sqrt{2} \end{align}

This gives that

$$ a_n = A(2 + \sqrt{2})^n + B(2 - \sqrt{2})^n $$

It's worth noting that this is identical to solving a homogeneous linear differential equation.

Answer 4

We can represent this recursion with matrices:

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

Or $x_n = A\cdot x_{n-1}$ where $x_n$ is the vector specified above. This is a simple difference equation and we can see that

$$ x_n = A^n \cdot x_0 $$

by expanding $x_n = A x_{n-1} = A \cdot A \cdot x_{n-2} = \cdots = A^n \cdot x_0 $

Computing this matrix power is difficult and hard numerically; there's no easy solution that I know of. To get around this, let's use eigenvectors $V$ and the matrix of eigenvalues $\Lambda$.

$$ x_n = (V\Lambda V^{-1})^n x_0 = V \Lambda^n V^{-1}x_0 $$

The computation of $\Lambda^n$ is straightforward. $\Lambda$ is diagonal so the computation of this matrix power is just each term raised to a power.

For this $A$,

$$ \begin{aligned} V &= \begin{bmatrix} 2+\sqrt{2} & 2-\sqrt{2} \\ 1 & 1 \end{bmatrix} \\ \Lambda &= \begin{bmatrix} 2+\sqrt{2} & 0 \\ 0 & 2-\sqrt{2} \end{bmatrix} = \begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix} \end{aligned} $$

Carrying out this computation, we see that

$$ x_n = \frac{1}{\sqrt{8}} \begin{bmatrix} \lambda_1^{n+1} - \lambda_2^{n+1} & \lambda_1^{n+1}\lambda_2 + \lambda_1\lambda_2^{n+1} \\ \lambda_1^n - \lambda_2^n & \lambda_1^n\lambda_2 + \lambda_1 \lambda_2^n \end{bmatrix} \cdot x_0 $$