UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 8.10 Free with a free account

Solving Linear Recurrence Relations

Discrete Mathematics · Chapter 8: Binomial Probability, Recurrence Relations, and Generating FunctionsSection 8.10 · lesson 55 of 87video coming soon

← First-Order Linear Recurrence Relations Next lesson: Recurrences in Divide-and-Conquer Algorithms →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access

Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Characteristic equations, particular solutions, and a complete closed form.

Solve homogeneous recurrences with distinct roots
Handle a repeated characteristic root
Find a particular solution by undetermined coefficients
Combine them and apply initial conditions

Transcript

Everything said in the video, section by section (1,577 words). Read along, or search it.

Binomial Probability, Recurrence Relations, and Generating Functions

Solving Linear Recurrence Relations

Section eight point nine set up recurrence relations. This section solves them, turning a recurrence into an explicit formula for the n-th term. There are three pieces. The characteristic equation method for homogeneous recurrences, particular solutions for non-homogeneous ones, and a way to combine them into a complete closed form.

The Opening Problem

Will the Echo Fade or Explode?

A real-time audio engine implements a recursive echo effect. Each output sample is computed from a combination of previous output samples. Audio engineers call that a recursive, or I I R, filter. Before shipping it, an engineer needs to know how its output behaves over thousands of samples. Does the echo fade out, grow without bound, or settle into a steady pattern? Simulating millions of samples one at a time is wasteful, when the filter is mathematically just a linear recurrence. Solve it in closed form once, and the long-term behavior can be read directly from the formula.

Order k

Generalizing 8.9's First-Order Form

Section eight point nine covered first-order recurrences, where each term depends on one earlier term. The same idea extends to order k. Each term is a combination of the k previous terms, each times a constant, plus a function f of n. The last constant, c k, isn't zero. An order k recurrence needs k initial conditions, a zero through a k minus one. And, as before, it's homogeneous when f of n is zero for every n.

Theorem 8.10.1

Guess r to the n

The method rests on a single guess. Try a solution of the form a n equals r to the n, for some nonzero constant r, and see what condition makes it work. Substituting into the homogeneous recurrence gives r to the n, equal to c one times r to the n minus one, and so on. Dividing both sides by r to the n minus k leaves a polynomial equation in r, called the characteristic equation. If it has k distinct roots, the general solution is a combination of each root raised to the n, each times its own constant. Those constants are then determined by the initial conditions.

Worked Example 8.10.1

Distinct Roots: 2 and 3

Here's an example. A simplified two-tap feedback filter's gain sequence satisfies a n equals five a n minus one, minus six a n minus two. It starts with a zero equal to two, and a one equal to five. The characteristic equation is r squared minus five r plus six equals zero. It factors as r minus two, times r minus three. So the roots are two and three. The general solution is C one times two to the n, plus C two times three to the n. At n equals zero, C one plus C two is two. At n equals one, two C one plus three C two is five. Subtracting twice the first equation gives C two equal to one, so C one is also one. So a n is two to the n, plus three to the n. Check a two. The recurrence gives twenty-five minus twelve, thirteen. And the formula gives four plus nine, also thirteen.

Theorem 8.10.2

A Repeated Root Needs an Extra n

A repeated root needs a modification. If a root appears twice, a single term, C one r to the n, can't supply enough independent constants to match two initial conditions. For an order two recurrence with a double root r, the conditions force c one to equal two r, and c two to equal minus r squared. Then the general solution is C one plus C two n, all times r to the n. Here's why n r to the n really works. Substitute it into the right-hand side and expand. That gives r to the n minus two, times a bracket. The bracket is n times c one r plus c two, minus c one r, minus two c two. c one r plus c two is r squared, by the characteristic equation. And the leftover, minus c one r minus two c two, is minus two r squared plus two r squared, which is zero. So the right-hand side is exactly n r to the n. Every equality was derived, not assumed.

Worked Example 8.10.2

Repeated Root: 2, Twice

A differently tuned filter satisfies a n equals four a n minus one, minus four a n minus two. It starts with a zero equal to one, and a one equal to six. The characteristic equation is r squared minus four r plus four, which is r minus two, squared. So there's a single repeated root, two. The general solution is C one plus C two n, times two to the n. At n equals zero, that's just C one, which is one. At n equals one, it's C one plus C two, times two, which is six. So C two is two. So a n is one plus two n, times two to the n. Check a two. The recurrence gives twenty-four minus four, twenty. And the formula gives five times four, also twenty.

Figure 8.10.1

Different Growth Shapes

This chart plots both closed forms on a logarithmic vertical scale. A pure exponential, like the dashed two to the n reference, is a straight line on a log scale. That's because its logarithm is n times log r, which is linear in n. The repeated-root sequence has an extra factor of n. Its logarithm adds log of one plus two n, which bends it away from a straight line. That's visual evidence that the two solution forms describe genuinely different growth shapes, not just different constants.

8.10.2 Particular Solutions

Undetermined Coefficients

Now non-homogeneous recurrences. When f of n isn't zero, one new ingredient is needed, a particular solution. That's any single sequence satisfying the full recurrence. It doesn't have to match the initial conditions. That comes later. The standard technique, the method of undetermined coefficients, guesses a trial form shaped like f of n, and solves for its coefficients by substitution. For a constant, try a constant. For a linear polynomial, try A n plus B. For an exponential, d times s to the n, try A times s to the n. But if the trial form already solves the homogeneous recurrence, there's nothing left over to match f of n. So multiply the trial by n. That happens when one is a root for polynomials, or s is a root for exponentials.

Worked Example 8.10.3

A Ramping Correction, 4n

Suppose the engineer adds a steadily ramping correction, so the gain now satisfies a n equals three a n minus one, plus four n. Four n is a linear polynomial. The homogeneous root is three, not one, so no modification is needed. Try A n plus B. Substituting gives A n plus B, equal to three A n minus three A plus three B, plus four n. That's three A plus four, times n, plus three B minus three A. Matching the coefficients of n, A equals three A plus four, so A is minus two. Matching constants, B equals three B minus three A, so B is minus three. So the particular solution is minus two n minus three. It satisfies the recurrence. But at n equals zero it gives minus three, not the required starting value of two. The homogeneous part will absorb that mismatch.

Theorem 8.10.3

Superposition

Here's why the pieces combine. Take the homogeneous general solution, and add any particular solution. Substitute that sum into the right-hand side of the full recurrence. The homogeneous part reproduces itself, because it satisfies the homogeneous recurrence. And the particular part reproduces itself plus f of n, because it satisfies the full recurrence. So the sum satisfies the full recurrence too. And because the homogeneous part keeps all its undetermined constants, they're still free to be solved for, using the actual initial conditions. So the initial conditions are always applied to the sum, never to the particular solution alone.

Worked Example 8.10.4

The Complete Closed Form

Now finish the example, with a zero equal to two. The homogeneous part, with root three, is C times three to the n. Adding the particular solution gives C times three to the n, minus two n, minus three. At n equals zero, that's C minus three. Setting it equal to two gives C equal to five. So a n is five times three to the n, minus two n, minus three. Check a one. The recurrence gives ten, and the formula gives fifteen minus five. And a two, thirty-eight both ways. Back to the audio engineer. The five times three to the n term dominates everything else as n grows. So this configuration's gain grows without bound, instead of settling into a steady echo. It's an unstable filter design. And the characteristic equation revealed it in five short steps, not a long simulation.

Takeaways

Homogeneous Plus Particular

To summarize. Substituting r to the n into a homogeneous recurrence gives the characteristic equation. Distinct roots each contribute a constant times that root to the n. A repeated root needs an extra factor of n, and that was proved to work. A particular solution only needs to satisfy the full recurrence. It's found by matching a trial form to f of n, with an extra n when the form coincides with a homogeneous solution. And the general solution is always homogeneous plus particular, with the initial conditions applied last. Here's something to think about. Suppose the recurrence were a n equals three a n minus one, plus three to the n. Substitute the standard guess, A times three to the n, and simplify both sides. What equation do you get, and why can no value of A satisfy it? What trial form should you use instead? And why does multiplying by an extra factor of n fix exactly the problem you found?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.

Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.

Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.

Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.

Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.

130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversitySigned partner

University of the PeopleSigned partner

Charter Oak State CollegeSigned partner

Strayer UniversitySigned partner

Columbia Southern UniversitySigned partner

Indiana TechSigned partner

Penn StateWorks with NCCRS

Southern New Hampshire UniversityWorks with NCCRS

SUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Solving Linear Recurrence Relations

How do you solve a homogeneous linear recurrence when the characteristic equation has distinct roots?

Substitute a_n = r^n to get the characteristic equation, then write the solution as a sum of constants times each root to the n. For a_n = 5a_{n-1} - 6a_{n-2}, the equation r^2 - 5r + 6 = 0 gives roots 2 and 3, so a_n = C_1 2^n + C_2 3^n. With a_0 = 2 and a_1 = 5, C_1 = C_2 = 1.

What do you do when the characteristic equation has a repeated root?

Multiply the repeated root's term by an extra factor of n. For an order-two recurrence with a double root r, the general solution is (C_1 + C_2 n)r^n. For a_n = 4a_{n-1} - 4a_{n-2} with a_0 = 1 and a_1 = 6, the root is 2 twice. This gives C_1 = 1, C_2 = 2, so a_n = (1+2n)2^n.

How do you find a particular solution using undetermined coefficients?

Guess a trial form shaped like f(n), substitute it into the full recurrence, and match coefficients. For a_n = 3a_{n-1} + 4n, try An + B. Matching gives A = -2 and B = -3, so -2n - 3 works. If the trial already solves the homogeneous recurrence, multiply it by n.

How do you combine the homogeneous and particular solutions and apply the initial conditions?

Add the homogeneous general solution and a particular solution, then apply the initial conditions to the whole sum, not to the particular part alone. For a_n = 3a_{n-1} + 4n with a_0 = 2, write a_n = C\cdot 3^n - 2n - 3. Then C - 3 = 2, so C = 5 and a_n = 5\cdot 3^n - 2n - 3.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?

Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

How much does Discrete Mathematics cost and what is included?

$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.

Which universities accept UPI Study credits?

UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.

How long does Discrete Mathematics take?

It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.

How are the exams done?

Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.

How do my credits reach my college?

When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabus Every course with PRO →

Discrete Mathematics
4 credits · NCCRSEnroll →