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

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.