Solving Second-Order Linear Homogeneous Recurrence Relations with Constant Coefficients

In this post I will explain how to solve a type of recurrence relation known as Second-Order Linear Homogeneous Recurrence Relations. These types of equations have the form:

a_k = A \cdot a_{k-1} + B \cdot a_{k-2}       (where B\neq 0 and k\geq 2)

Our main objective when approaching this problem is to obtain an explicit formula. The explicit formula is much more valuable than a recurrence relation because if we want to figure out the 100th value we just have to plug 100 into our formula, but if we had a recurrence relation we would need to obtain all 99 values before getting the 100th value.

In order to solve these types of equations we first assume that our explicit formula has the form a_n = t^n where t is some real number and does not equal 0. This means that there is some value of t such that the following sequence:

1, t, t^2, t^3, t^4, t^5, \ldots, t^n

satisfies the recurrence relation. Stated another way, this means that the relation can be written as follows:

t^k = A \cdot t^{k-1} + B \cdot t^{k-2}       (where B\neq 0 and k\geq 2)

What happens when we let k = 2 (something beautiful! :p ). When we let k = 2 our equation turns into the extremely familiar quadratic equation which can be solved by factoring or the quadratic equation. This equation is also known as our characteristic equation of the relation and it has the form:

t^2 = At + B

or

t^2 – At – B = 0

Solving the equation from this point involves the distinct-root theorem which states that if our characteristic equation has the quadratic form and it has two distinct roots {r and s}, then the explicit form can be written in the following form:

a_n = Cr^n + Ds^n

where C and D are to be determined by the values of a_0 and a_1. In order to show you how this works in practice consider the following example.

Given the recurrence relation a_k = 3a_{k-1} + 10a_{k-2} k \geq 2, a_0 = 1  a_1 = 4  what is the explicit formula?

First we suppose our explicit formula can be written in the form:

t^k = 3t^{k-1} + 10t^{k-2}

Let k = 2 in order to generate our quadratic equation:

t^2 = 3t + 10

or

t^2 – 3t – 10 = 0

What follows is just some basic algebra in order to figure out our possible values of t.

(t-5)(t+2) = 0

t = {-2, 5}

Now its time to use the distinct root theorem in order to find our explicit formula!! This is a really simple process and just requires a little bit of algebra (systems of equations) and our base values.

a_n = C 5^n + D (-2)^n

Next let n = 0 (note: a_0 = 1)

1 = C 5^0 + D (-2)^0

1 = C + D

1 – C = D

Now let n = 4 (note: a_1 = 4)

4 = C 5^1 + D (-2)^1

4 = 5C – 2D

4 = 5C – 2(1-C)

(note: we made the substitution from our system of equations)

4 = 5C – 2 + 2C

6 = 7C

C = \frac {6} {7}

Finally we use our newly obtained value of C to solve for D

D = 1 – C

D = 1 – \frac {6} {7}

D = \frac {1} {7}

Thus our final explicit formula is:

a_n = \frac {6} {7} 5^n + \frac {1} {7} (-2)^n

Advertisements

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