1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.