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:

If you think carefully about it, you can express the sum of the first n integers as a recurrence relation. If you denote 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

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 be the amount of money we have after n years, then we can write the compounding of interest as a recurrence relation:

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:

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 . If we substitute this to the equation above, we will get

Dividing both sides by we get,

.

This means that is a solution to this recurrence relation if r satisfies the following algebraic equation:

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:

The characteristic equation of this recurrence relation is

**Case of distinct roots**

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

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

Collecting the coefficients:

Using the characteristic equation , we have

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 is the root, the solution to the recurrence relation can be expressed as

.

To see this, substitute this formula to the recurrence relation

**Compound Interest**

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

is

whose characteristic root is

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

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

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

Or substituting 1 million to , we get .

## One thought on “A Method To The Madness”