# A Method To The Madness

In the previous post on recurrence relations, we derived a general method to solve divide and conquer relations. In another article, we derived the formula of the sum of the first n non-negative integers:

$\displaystyle \sum_{i=0}^n i = \frac{n(n+1)}{2}$

If you think carefully about it, you can express the sum of the first n integers as a recurrence relation. If you denote $s_n$ to be the sum of the first n integers, then it is just equal to n plus the sum of the first n-1 integers. Symbolically, we write this as

$\displaystyle s_n = s_{n-1} + n$

A good question now comes to mind: Is there also a method to solve this kind of recurrence relation? Surprise! Surprise! The answer is YES! But first, let us handle the easier cases.

A good example of a recurrence relation we frequently encounter is in our financial life, when we compute how much money we will get at the end of one year when we put it in a bank. Suppose, you deposit 1 million bucks in a bank with 10% interest compounded yearly. How much money will you get after 10 years? If we let $P_n$ be the amount of money we have after n years, then we can write the compounding of interest as a recurrence relation:

$\displaystyle P_n = P_{n-1} + 0.1\cdot P_{n-1} = 1.1 \cdot P_{n-1}$

The recurrence relation above is just an example of a more general form called the Linear Homogeneous Recurrence Relation With Constant Coefficients. That’s a pretty long name for a seemingly simple concept. What this means is that your recurrence relation has the following form:

$\displaystyle a_{n} = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k}$

To solve this recurrence relation, we invoke the method of “Lucky Guess”, that is, we will guess that the solution of the above recurrence relation is of the form $a_n = r^n$. If we substitute this to the equation above, we will get

$\displaystyle r^n = c_1 r^{n-1} + c_2 r^{n-2} + \ldots + c_k r^{n-k}$

Dividing both sides by $r^{n - k}$ we get,

$\displaystyle r^k = c_1 r^{k-1} + c_2 r^{k-2} + \ldots + c_k$.

This means that $a_n = r^n$ is a solution to this recurrence relation if r satisfies the following algebraic equation:

$\displaystyle r^k - c_1 r^{k-1} - c_2 r^{k-2} - \ldots - c_k = 0$

This is called the Characteristic Equation and the roots of this equation are called characteristic roots. To make things look simpler, let’s suppose we have a recurrence relation of degree 2:

$\displaystyle a_n = c_1 a_{n-1} + c_2 a_{n-2}$

The characteristic equation of this recurrence relation is

$\displaystyle r^2 - c_1 r - c_2 = 0$

Case of distinct roots

Suppose the roots of the above equation are $r_1$ and $r_2$, respectively. Then

$\displaystyle a_n = \alpha_1 r_1^n + \alpha_2 r_2^n$

is a solution of the recurrence relation, where $\alpha_1$ and $\alpha_2$ are constants. To prove this, substitute the solution to the recurrence relation

$\displaystyle c_1 a_{n-1} + c_2 a_{n-2} = c_1 (\alpha_1 r_1^{n-1} + \alpha_2 r_2^{n-1}) + c_2 (\alpha_1 r_1^{n-2} + \alpha_2 r_2^{n-2})$
$\displaystyle = c_1\alpha_1 r_1^{n-1} + c_1 \alpha_2 r_2^{n-1} + c_2 \alpha_1 r_1^{n-2} + c_2\alpha_2 r_2^{n-2}$

Collecting the $\alpha$ coefficients:

$\displaystyle = \alpha_1 ( c_1 r_1^{n-1} + c_2 r_1^{n-2}) + \alpha_2 (c_1 r_2^{n-1} + c_2 r_2^{n-2})$
$\displaystyle = \alpha_1 r_1^{n-2} (c_1 r_1 + c_2) + \alpha_2 r_2^{n-2} (c_1 r_2 + c_2)$
$\displaystyle = \alpha_1 r_1^{n-2} r_1^2 + \alpha_2 r_2^{n-2} r_2^2$

Using the characteristic equation $r^2=c_1 r + c_2$, we have

$\displaystyle = \alpha_1 r_1^n + \alpha_2 r_2^2$
$\displaystyle = a_n$

as was to be shown.

Case of Repeated Roots

If the roots of the characteristic equation is repeated, that is, the quadratic equation is a perfect square, then if $r_1$ is the root, the solution to the recurrence relation can be expressed as

$\displaystyle a_n = \alpha_1 r_1^n + n\alpha_2 r_1^n$.

To see this, substitute this formula to the recurrence relation

$\displaystyle c_1 a_{n-1} + c_2 a_{n-2} = c_1 (\alpha_1 r_1^{n-1} + n\alpha_2 r_1^{n-1}) + c_2 (\alpha_1 r_1^{n-2} + n\alpha_2 r_1^{n-2})$
$\displaystyle = \alpha_1 ( c_1 r_1^{n-1} + c_2 r_1^{n-2}) + n\alpha_2 (c_1 r_1^{n-1} + c_2 r_1^{n-2})$
$\displaystyle = \alpha_1 r_1^{n-2} ( c_1 r_1 + c_2) + n \alpha_2 r_1^{n-2} (c_1 r_1 + c_2)$
$\displaystyle = \alpha_1 r_1^n + n \alpha_2 r_1^n$
$\displaystyle = a_n$

Compound Interest

Applying this to our compound interest recurrence relation, we see that the characteristic equation of

$\displaystyle P_n = P_{n-1} + 0.1\cdot P_{n-1} = 1.1 \cdot P_{n-1}$

is

$\displaystyle r - 1.1 = 0$

whose characteristic root is

$\displaystyle r = 1.1$

Therefore, the solution to the compound interest recurrence relation has the form

$\displaystyle P_n = \alpha \cdot 1.1^n$

If at n=0, the amount of money you have in the bank is $P_0$, we can solve for $\alpha$:

$\displaystyle P_0 = \alpha \cdot 1.1^0 = \alpha \cdot 1 = \alpha$

This means that at the end of period n, the amount of money you have in the bank is

$\displaystyle P_n = 1.1^n \cdot P_0$

Or substituting 1 million to $P_0$, we get $P_{10} = 2593742$.