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

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