Solve the difference equation $x_n-4x_{n-1}+3x_{n-2}=0$, $x_0 = 2$, $x_1 = 5$

Question

Solve the following difference equation to the specific $x$ values

• $x_0 = 2$
• $x_1 = 5$
• $x_n-4x_{n-1}+3x_{n-2}=0$

I need some help and guidance to get this problem started and to understand the proper way to solve these equations.

Answer 1

Given a linear second order recurrence relation, $x_n = a\cdot x_{n-1} + b\cdot x_{n-2}$ (where $a$ and $b$ are constants), we can do the following:

$x_n - a\cdot x_{n-1} - b\cdot x_{n-2}=0$

Form the characteristic polynomial by replacing the above with the following:

$x^2-ax-b=0$

---

(as an aside, this is the same characteristic polynomial as for if we were to have described this scenario using matrix equation that describes the same thing: $\det\left(\begin{bmatrix} a&b\\1&0\end{bmatrix}-xI\right)$

---

Finding the roots of the characteristic polynomial to be $\lambda_1, \lambda_2$, we have two possibilities:

$\begin{cases} a_n = c_1(\lambda_1)^n + c_2(\lambda_2)^n&\text{if}~\lambda_1\neq \lambda_2\\ a_n = c_1(\lambda_1)^n + c_2n(\lambda_2)^n&\text{if}~\lambda_1=\lambda_2\end{cases}$

for some values $c_1$ and $c_2$ which will be determined later.

---

In your specific example, you have the characteristic polynomial:

$x^2-4x+3=0$ which factors as $(x-3)(x-1)$

Since these are different roots, you have that it should satisfy the closed form $x_n = c_1 (3)^n + c_2 (1)^n$

Taking your initial conditions, we then have the following system of equations:

$\begin{cases} x_0 = c_1(3)^0 + c_2(1)^0\\ x_1 = c_1(3)^1+c_2(1)^1\end{cases}$

Plugging in the initial conditions, $x_0=2,~x_1=5$, you have a linear system of two equations with two unknowns which can be solved using your favorite method to figure out the values of $c_1$ and $c_2$.

---

This technique can be generalized to linear recurrence relations of higher orders as well. Repeated roots to the characteristic polynomial will appear as many times as it is repeated, each with an additional power of $n$ being multiplied. For example, if the characteristic polynomial factored as $(x+3)^3(x-1)$, you would have the recurrence $x_n = c_1(-3)^n + c_2n(-3)^n + c_3n^2(-3)^n + c_4(1)^n$

Answer 2

$$x_n-4x_{n-1}+3x_{n-2}=0$$

$$x_{n+1} = 4x_{n} - 3x_{n-1}$$

So

$$\begin{bmatrix} x_{n+1} \\ x_{n} \end{bmatrix} = \begin{bmatrix} 4 & -3 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} x_{n} \\ x_{n-1} \end{bmatrix}$$

So

$$\begin{bmatrix} x_{n+1} \\ x_{n} \end{bmatrix} = \begin{bmatrix} 4 & -3 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} x_{1} \\ x_{0} \end{bmatrix}$$

That is a closed form (IMO the best closed form). You can further diagonalize the matrix:

$$ \begin{bmatrix} 4 & -3 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ \frac 13 & 1 \end{bmatrix} \begin{bmatrix} 3 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ \frac 13 & 1 \end{bmatrix}^{-1}$$

So

$$\begin{bmatrix} x_{n+1} \\ x_{n} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ \frac 13 & 1 \end{bmatrix} \begin{bmatrix} 3 & 0 \\ 0 & 1 \end{bmatrix}^n \begin{bmatrix} 1 & 1 \\ \frac 13 & 1 \end{bmatrix}^{-1} \begin{bmatrix} 5 \\ 2 \end{bmatrix}$$

$$\begin{bmatrix} x_{n+1} \\ x_{n} \end{bmatrix} = \begin{bmatrix} \frac{3^{n+2} + 1}{2} \\ \frac{3^{n+1} + 1}{2} \end{bmatrix}$$

Answer 3

You can also approach this with generating functions. If $F(y)=\sum\limits_{n\ge0}x_ny^n$ is the generating function for $x_n$, then you can sum both sides appropriately and solve for $F(y)$: $$\begin{align*} x_n-4x_{n-1}+3x_{n-2}&=0\\[1ex] \sum_{n\ge2}x_ny^n-4\sum_{n\ge2}x_{n-1}y^n+3\sum_{n\ge2}x_{n-2}y^n&=0\\[1ex] \bigg(F(y)-5y-2\bigg)-4y\bigg(F(y)-2\bigg)+3y^2F(y)&=0\\[1ex] F(y)&=\frac{-3y+2}{3y^2-4y+1}=\frac{1}{2(1-y)}+\frac{3}{2(1-3y)} \end{align*}$$ Recalling that for $|x|<1$, $$\sum_{n\ge0}p^n=\frac{1}{1-p}$$ the final solution is not hard to reach.