How to Find Explicit Solution for Reccurence

Wouldn't it be nice to have a systematic way of solving recurrence relations that didn't rely on guess-and-check or iteration?

Jenn, Founder Calcworkshop^®, 15+ Years Experience (Licensed & Certified Teacher)

Well, linear homogeneous recurrence relations are such a class of recurrence relations where we can use a structured, systematic process!

But first, we need to understand what linear homogeneous means as well as degree.

So, a linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form:

Linear Homogeneous Recurrence Relations Formula

This means that the recurrence relation is linear because the right-hand side is a sum of previous terms of the sequence, each multiplied by a function of n. Additionally, all the coefficients of each term are constant.

And the recurrence relation is homogenous because there are no terms that are multiples of previous terms. All this means is that there are no constant terms.

Additionally, the degree of the recurrence relation is k.

Alright, so now it's time to practice and make sure we can determine if a recurrence relation fits our special class. The table below shows examples of recurrence relations where we identify if they are linear, homogeneous, and their degree.

Identify Linear Homogeneous Degree

Okay, so now we're ready to solve linear homogeneous recurrence relations using the Characteristic Root Method.

The characteristic root method is a way for us to identify solutions of the form of a geometric sequence quickly, as the definition below nicely highlights.

Characteristic Root Definition

Now, if we move all the terms to the left-hand side and set the question equal to zero, we create an equation where the sequence has a solution. In fact, this equation, as shown below, is called the characteristic equation, or the auxiliary equation, and the solutions obtained are called the characteristic roots of the recurrence relation.

Formula For Characteristic Equation

So, the steps for solving a linear homogeneous recurrence relation are as follows:

1. Create the characteristic equation by moving every term to the left-hand side, set equal to zero.
2. Solve the polynomial by factoring or the quadratic formula.
3. Determine the form for each solution: distinct roots, repeated roots, or complex roots.
4. Use initial conditions to find coefficients using systems of equations or matrices.

But what are these distinct roots, repeated roots, or complex roots?

These are the types of solutions you can get when solving a polynomial equation, and they relate to the type of closed-form or general formula we will generate for our recurrence relation.

Distinct Real Vs Repeated Real Vs Complex

Please note that most Discrete Math I courses focus on distinct and repeated roots only and leave complex roots for a Discrete Math II course. In this lesson, we will look at all three, so you are well versed in all solving techniques, regardless of the class you are currently enrolled in.

Also, I would like to point out that this should be extremely familiar for anyone who has taken Differential Equations. And for anyone planning on taking Differential Equations in the future, a similar technique will be used again when solving higher order differential equations.

Okay, so let's see this process in action by walking through a few examples of solving the recurrence relation using the characteristic root method.

Example

We are asked to solve the recurrence relation using the characteristic root method.

First, we determine that the given recurrence relation is degree two and is linear homogenous recurrence relation with initial condition. This means we can proceed by finding the characteristic equation.

Solve Degree Two Recurrence Relation

Next, we create our geometric sequence and move all of our terms to the left-hand side so the recurrence relation is set equal to zero, and solve by factoring.

Solve Degree Two Characteristic Equation

Now we use our formula for Distinct Real Roots, and substitute 4 and -2, the solutions of our characteristic equation, into the formula.

Solve Degree Two Distinct Formula

Next, we use our initial conditions to solve for the coefficients. This will require us to employ our Algebra skills for solving systems of equations using the elimination method.

Solve Degree Two Coefficients

Lastly, we plug in our new found coefficients into equation to finalize our explicit solution for the recurrence relation.

Solve Degree Two Recurrence Closed Form

Example

Now that we've seen an example of how to handle distinct roots let's investigate a recurrence relation with repeated roots.

First, we determine that the given recurrence relation is degree two and is linear homogenous recurrence relation with initial condition. This means we can proceed by finding the characteristic equation.

Recurrence Relation Example

Next, we create our geometric sequence and move all of our terms to the left-hand side so the recurrence relation is set equal to zero, and solve by factoring.

Repeated Root Characteristic Equation

Now we use our formula for Repeated Real Roots, and substitute the value we found in our previous step into the formula.

Repeated Root Formula

Next, we use our initial conditions to solve for the coefficients. Once again, we will need to use the elimination method to solve the system of equation.

Repeated Root Formula

Finally, we plug in our new found coefficients into equation to finalize the closed form for the recurrence relation.

Repeated Root Closed Form

Together we will work through numerous examples of solving recurrence relations using the auxiliary equation involving distinct, repeated, and complex roots.

Let's jump right in.

Video Tutorial w/ Full Lesson & Detailed Examples

1 hr 0 min

• Introduction to Video: Solving Recurrence Relations
• 00:00:36 Identifying a linear homogeneous recurrence relation and its degree (Example #1a-i)
• Exclusive Content for Members Only

• 00:18:57 What is the characteristic root method and formulas for distinct—repeated—complex roots?
• 00:29:31 Solve the degree 1 recurrence relation (Example #2)
• 00:34:57 Identify the closed formula with distinct roots (Examples #3-5))
• 01:10:54 Find the closed form with repeated roots (Examples #6-7)
• 01:23:59 Uncover the explicit formula with complex roots (Example #8)
• Practice Problems with Step-by-Step Solutions
• Chapter Tests with Video Solutions

Get access to all the courses and over 450 HD videos with your subscription

Monthly and Yearly Plans Available

Get My Subscription Now

How to Find Explicit Solution for Reccurence

Source: https://calcworkshop.com/combinatorics/recurrence-relation/

Share this post