Regarding recurrences, why do characteristic polynomials work, and why do we look for the roots? I'll use an example recurrence but my question is meant to be generalized.
Let's say we had some recurrence, such as:
$$F(n) = -8F(n-1) + 9F(n-2) + 92F(n-3) - 140F(n-4)$$
where we already know the first few base constants $F(0), F(1), F(2), F(3)$ so the entire recurrence is defined for all integers $n \geq 0$.
Normally we convert this to some kind of characteristic polynomial:
$$x^n = -8 x^{n-1} + 9 x^{n-2} + 92 x^{n-3} - 140x^{n-4}$$
Divide everything by $x^{n-4}$ and put everything on one side:
$$x^4  +8 x^3 - 9 x^2 - 92 x + 140 = 0$$
This polynomial can be factored:
$$(x - 2)^2 (x + 5) (x + 7) = 0$$
And now we know that the roots are $2, -5, -7$. The $2$ root has multiplicity $2$, whereas the $-5$ and $-7$ roots each have multiplicity $1$.
From this we can say that:
$$F(n) = a  \cdot (2)^n + b \cdot n \cdot  (2)^n + c \cdot (-5)^n + d \cdot (-7)^n$$
And then we use the original four values of $F$ that we do know to solve a short system of equations and solve for $a, b, c, d$ to finish up the closed form.
The short version of my question is basically "Why does this work?"
Why can we use a "characteristic polynomial" (what is this, exactly) instead of a recurrence? 
Why does that polynomial's roots directly correspond to the closed-form of that recurrence?
Why do we need to add an additional term with another power of $n$ for roots of multiplicity $>1$? 
 A: Two explanations.
First, if you have $c_k a_{n + k} + \dotsb + c_0 a_n = 0$, a (not unreasonable, simple) idea is to try $a_n = \alpha^n$. Substituting, you get that it has to be $c_k \alpha^k + \dotsb + c_0 = 0$. Furthermore, the equation  is linear, i.e., multiplying a solution by a constant or adding two solutions gives a solution. If $\alpha$ is a multiple zero of the characteric equation, again trying $n \alpha^n$, $n^2 \alpha^n$, ... shows it "works".
A "more scientific" (can be extended in several directions) technique is to use generating functions: Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$ and sum over $n \ge 1$, to get after recognizing some sums:
$\begin{align*}
c_k \sum_{n \ge 0} a_{n + k} z^n + \dotsb + c_0 \sum_{n \ge 0} a_n z^n
  &= 0 \\
c_k \frac{A(z) - a_0 -a_1 z - \dotsb - a_{k - 1} z^{k - 1}}{z^k}
  + \dotsb + c_0 A(z)
  &= 0
\end{align*}$
If you now multipĺy this mess by $z^k$, and solve for $A(z)$, you get:
$\begin{align*}
A(z)
  &= \frac{p(z)}{c_k z^k + \dotsb + c_0}
\end{align*}$
here $p(z)$ is a polynomial. This in turn can be written as partial fractions,  the terms of which are of one of the forms, for some $r \ge 1$:
$\begin{equation*}
\frac{1}{(1 - \alpha z)^r}
\end{equation*}$
You want the coefficients of $z^n$ in such. By the (extended) binomial theorem:
$\begin{align*}
(1 - \alpha z)^{-r}
  &= \sum_{n \ge 0} (-1)^n \binom{-r}{n} \alpha^r z^r \\
  &= \sum_{n \ge 0} \binom{n + r - 1}{r - 1} \alpha^r z^r
\end{align*}$
Note that the binomial coefficient $\binom{n + r - 1}{r - 1}$ is a polynomial of degree $r - 1$ in $n$, the $\alpha$ is seen to be a zero of the characteristic polynomial.
