Second-order difference equation solution 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$?
 A: 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) $$
A: 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.
