Assumption about the form of solutions to a recurrence relation Basically, when solving such recurrence relations, we try to find solutions of the form $a_n = r_n$, where $r$ is a constant.
$a_n = r^n$ is a solution of the recurrence relation
$a_n = c_1a_{n-1} + c_2a_{n-2} + … + c_ka_{n-k}$ if and only if
$r^n =  c_1r^{n-1} + c_2r^{n-2} + … + c_kr^{n-k}$.
Divide this equation by $r^{n-k}$ and subtract the right-hand side from the left:
$r^k - c_1r^{k-1} - c_2r^{k-2} - … - c_{k-1}r - c_k = 0$.
This is called the characteristic equation of the recurrence relation.
Why do we think that the solutions are of the form(we try to find solutions of the form)
$a_n = r^n$ and not some other form?
Is there an intuitive explanation?
 A: One clean explanation (and a uniform way to solve such recurrences) is to use generating functions. Say you have:
$\begin{align}
a_{n + k} = c_{k - 1} a_{n + k - 1}
             + \dotsb + c_0 a_n
\end{align}$
Define the generating function $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$ and sum over $n \ge 0$, noting that e.g.:
$\begin{align}
\sum_{n \ge 0} a_{n + s} z^n
  = \frac{A(z) - a_0 - a_1 z - \dotsb - a_{s - 1} z^{s - 1}}{z^s}
\end{align}$
to get:
$\begin{align}
\frac{A(z) - a_0 - \dotsb - a_{k - 1} z^{k - 1}}{z^k}
  = c_{k - 1}
      \frac{A(z) - a_0 - \dotsb - a_{k - 2} z^{k - 2}}{z^{k - 1}}
       + c_{k - 2}
          \frac{A(z) - a_0 - \dotsb - a_{k - 3} z^{k - 3}}{z^{k - 2}}
       + \dotsb
       + c_0 A(z)
\end{align}$
Multiply through by $z^k$ and collect terms to get:
$\begin{align}
A(z) (1 - c_{k - 1} z - \dotsb - c_0 z^k)
  = b_{k - 1} z^{k - 1} + \dotsb + b_0
\end{align}$
Here the $b_i$ are messy combinations of the initial values $a_0$ through $a_{k - 1}$. The critical point is that:
$\begin{align}
A(z)
  = \frac{b_{k - 1} z^{k - 1} + \dotsb + b_0}
         {1 - c_{k - 1} z - \dotsb - c_0 z^k}
\end{align}$
This can be split into partial fractions. By that technique you know that a zero $1/r$ of multiplicity $m$ of the denominator gives rise to terms:
$\begin{align}
\frac{A_m}{(1 - r z)^m} + \dotsb + \frac{A_1}{1 - r z}
\end{align}$
Now, by the generalized binomial theorem, for $s \in \mathbb{N}$:
$\begin{align}
(1 - r z)^{-s}
  &= \sum_{n \ge 0} (-1)^n \binom{-s}{n} r^n z^n \\
  &= \sum_{n \ge 0} \binom{n + s - 1}{s - 1} r^n z^n
\end{align}$
Noting that $\binom{n + s - 1}{s - 1}$ is a polynomial of degree $s - 1$ in $n$, you see that a zero $1/r$ of multiplicity $m$ gives rise to a set of terms that add up to $p(n) r^n$, with $p(n)$ a polynomial of degree (up to) $m - 1$ in $n$ ("up to" as $1 - r z$ might be a factor of the numerator).
In case you have complex zeros, they come in conjugate pairs $r$, $\overline{r}$, and the coefficients of the terms are also conjugates (otherwise the result wouldn't be real). Thus you get a bunch of terms like:
$\begin{align}
\alpha n^s r^n + \overline{\alpha} n^s \overline{r}^n
  = 2 \Re\left(\alpha n^s r^n\right)
\end{align}$
These terms can be expressed in trigonometric terms by expressing the values as complex exponentials.
