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

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?

#### Solutions Collecting From Web of "Solve the reccurence $a_n= 4a_{n−1} − 2 a_{n−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.)

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.

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.

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$$