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.

Advertisements

Published by

Bobby Corpus

Is an IT Architect.

One thought on “A Method To The Madness”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s