Second-order difference equation solution

Question

Say we have a second-order difference equation:

$$x_n = x_{n-1} + x_{n-2} $$

Many of the notes that I have found online regarding how to solve this type of equation will have a step such as "guess" $x_n=Ar^n$.

What is the intuition behind this procedure? How would one know to "guess" that $x_n=Ar^n$?

Answer 1

We can transform the recurrence relation into a linear algebraic problem.

Let $\vec{a}_n= \begin{pmatrix} x_n\\ x_{n+1}\\ \end{pmatrix}$, $\vec{a}_0= \begin{pmatrix} 0\\ 1 \end{pmatrix}$.
Then $\vec{a}_{n+1}= \begin{pmatrix} x_{n+1}\\ x_{n}+x_{n+1} \end{pmatrix}=A\vec{a}_n $ where $A =\begin{pmatrix} 0 & 1\\ 1 & 1\\ \end{pmatrix}$

In this way, we can easily see that $\vec{a}_n=A^n\vec{a}_0$ by induction.

(Note that if you know $\vec{a}_n$, then you can recover $x_n$ by looking at its first coordinate)

So it remains to compute $A^n\vec{a}_0$ in a more efficient way. It turns out that if we can find a number $\lambda$ such that $A\vec{x}=\lambda \vec{x}$ for special values of $\vec{x}$ then the problem can be easily solved.

The value $\lambda$ is called eigenvalue and it's corresponding value $\vec{x}$ is called eigenvector.
The eigenvalue $\lambda$ can be found by solving the characteristic equation $\det(\lambda I-A)=0$
In this case, we have $\det(\lambda I-A)=\lambda^2-\lambda-1=0$
Hence the eignvalues are $\frac{1+\sqrt{5}}{2}$ and $\frac{1-\sqrt{5}}{2}$

For the eigenvalue $\frac{1+\sqrt{5}}{2}$, to find its eignevector, we have to solve $A\vec{x}=\frac{1+\sqrt{5}}{2}\vec{x}$
This is the same as finding $Ker(A-\frac{1+\sqrt{5}}{2}I)$
Since $A-\frac{1+\sqrt{5}}{2}I= \begin{pmatrix} -\frac{1+\sqrt{5}}{2} & 1\\ 1 & \frac{1-\sqrt{5}}{2} \end{pmatrix}$, we see that $\displaystyle Ker(A-\frac{1+\sqrt{5}}{2}I)=\mathbb{R}(1,\frac{1+\sqrt{5}}{2})$
Similarly, we have $Ker(A-\frac{1-\sqrt{5}}{2}I)=\mathbb{R}(1,\frac{1-\sqrt{5}}{2})$
Denote $\vec{v}_1=(1,\frac{1+\sqrt{5}}{2})$, $\vec{v}_2=(1,\frac{1-\sqrt{5}}{2})$.
When $\vec{x}$ is a multiple of $\vec{v}_1$, then $A\vec{x}=\frac{1+\sqrt{5}}{2}\vec{x}$ and so $A^n\vec{x}=\left(\frac{1+\sqrt{5}}{2}\right)^n\vec{x}$
Similar for the $\frac{1-\sqrt{5}}{2}$ case.

This gives us intuition to express $\vec{a}_0$ as a linear combination of $\vec{v}_1$ and $\vec{v}_2$:
$$\vec{a}_0= \frac{1}{\sqrt{5}}\vec{v}_1-\frac{1}{\sqrt{5}}\vec{v}_2 $$ Thus,

$$\begin{align*} \vec{a}_n&=A^n(\frac{1}{\sqrt{5}}\vec{v}_1-\frac{1} {\sqrt{5}}\vec{v}_2)\\ &=\frac{1}{\sqrt{5}}(A^n\vec{v}_1-A^n\vec{v}_2)\\ &=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n \vec{v}_1-\left(\frac{1-\sqrt{5}}{2}\right)^n\vec{v}_n\right) \end{align*}$$

Finally, we pick the first coordinate and get: $$x_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n \right) $$

Answer 2

One explanation is given by generating functions. Say you have the recurrence:

$\begin{align*} \sum_{0 \le r \le k} c_r a_{n + r} &= f_n \end{align*}

Define generating functions:

$\begin{align*} A(z) &= \sum_{n \ge 0} a_n z^n \\ F(z) &= \sum_{n \ge 0} f_n z^n \end{align*}$

Multiply the recurrence by $z^n$, sum over $n \ge 0$, recogize resulting sums:

$\begin{align*} \sum_{1 \le r \le k} c_r \sum_{n \ge 0} a_{n +r} z^n &= \sum_{n \ge 0} f_{n +r} z^n \\ \sum_{1 \le r \le k} c_r \frac{A(z) - a_0 - \dotsb - a_{r - 1} z^{z^{r -1}}} {z^r} &= F(z) \end{align*}$

If you solve for $A(z)$, you'll get an equation like:

$\begin{align*} A(z) z^k c(z) &= p(z) + z^k F(z) \end{align*}$

Here $c(z) = \sum_r c_r z^{-r}$, p(z) is a polynomial of degree at most $k - 1$ that depends on the initial values. Let the zeros of $\sum_r c_r z^r$ be $\rho_r$ for $1 \le r \le k$, then we can factor:

$\begin{align*} z c(z) &= \prod_{1 \le r \le k} (z - \rho_k) \end{align*}$

If $F(z) = u(z) / v(z)$ is a rational function, with $u$ and $v$ polynomials, we can write:

$\begin{align*} A(z) &= \frac{p(z) v(z) + z^k u(z) c(z)} {z c(z) v(z)} \end{align*}$

That is, $A(z)$ is a rational function of $z$, whose denominator is the polinomial $z c(z) v(z)$. This can be divided into partial fractions, terms of the form:

$\begin{align*} &\frac{C}{(1 - \rho z)^m} \end{align*}$

here $\rho$ is a zero of the denominator (zeros of the characteristic equation $c_r \rho^r + \dotsb + c_0$ and of $v(z)$). Now, by the generalized binomial theorem:

$\begin{align*} (1 - \rho z)^{-m} &= \sum_{s \ge 0} (-1)^s \binom{-m}{s} \rho^s z^s \\ &= \sum_{s \ge 0} \binom{s + m - 1}{m - 1} \rho^s z^s \end{align*}$

We are interested in the coefficient of $z^s$. It turns out $\binom{s + m - 1}{m - 1}$ is a polynomial of degree $m - 1$ in $s$, thus the part of the solution due to $\rho$ is a polynomial of degree $m - 1$ in $s$ multiplied by $\rho^s$. If $\rho$ is of multiplicity one, $\rho^s$ it is.