First-Order Linear Recurrence Relations | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

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

First-Order Linear Recurrence Relations

Discrete Mathematics · Chapter 8: Binomial Probability, Recurrence Relations, and Generating FunctionsSection 8.9 · lesson 54 of 879 min · free with a free account

← Recursive Functions and Self-Referential DefinitionsNext lesson: Solving Linear Recurrence Relations →

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

Each step: a fixed multiple of the last value, plus something new.

  • Define a first-order linear recurrence
  • Explain why an initial condition is required
  • Classify recurrences as homogeneous or not
  • Model a word problem with 4 questions

Transcript

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

Binomial Probability, Recurrence Relations, and Generating Functions

First-Order Linear Recurrence Relations

This section defines the simplest and most common kind of recurrence relation. First-order and linear. We'll pin down exactly what that means, sort these recurrences into two types, and build a systematic way to turn a word problem into one. Actually solving them, finding a formula for each term, comes in section eight point ten.

The Opening Problem

Open Alerts, Day by Day

A monitoring system tracks how many alerts remain open at the end of each day. Each night, an automated triage job closes twenty-five percent of that day's open alerts. Meanwhile, a growing user base means that on day n, n new alerts arrive. Start with twenty open alerts. Day one ends with seventy-five percent of those twenty, plus the one new alert. That's sixteen. Day two carries that forward. Seventy-five percent of sixteen, plus two new alerts, is fourteen. Each day's value is a fixed fraction of the previous day's value, plus something new added that day. That shape appears throughout computing. A cache after repeated evictions, a queue's backlog after repeated servicing, or the running time of a procedure that calls itself on a slightly smaller input.

Definition 8.9.1

First-Order and Linear

Here's the definition. A sequence satisfies a first-order linear recurrence if each term equals a constant c, times the previous term, plus a function f of n. It holds for every n from one on, together with a stated starting value, a zero. f of n depends on the index n alone. Never on the previous term, or any other term. The relation is first-order because each term depends on exactly one preceding term. And it's linear because the previous term appears only multiplied by the constant c. It isn't squared, it isn't inside another function, and it isn't multiplied by anything involving n.

Worked Example 8.9.A

The Initial Condition Is Not Optional

The initial condition isn't optional. The equation only relates consecutive terms. Without a starting value, there are infinitely many sequences satisfying it, one for every choice of a zero. Take a n equals three times a n minus one, plus two, with a zero equal to one. Then a one is three times one plus two, which is five. a two is three times five plus two, seventeen. And a three is three times seventeen plus two, fifty-three. Each term needed only the one immediately before it. That confirms the recurrence and its start determine the sequence. But it's not the same as a general formula for a n. And not every relation fits. Squaring the previous term makes it nonlinear. And a n equals a n minus one plus a n minus two is linear, but not first-order. It needs two preceding terms.

Definition 8.9.2

Homogeneous or Non-Homogeneous

First-order linear recurrences come in two types. One is homogeneous if f of n is zero for every n. Then the relation is just a n equals c times a n minus one. It's non-homogeneous if f of n is nonzero for at least one n. That's a universal claim against an existential one. A function either is the zero function or it isn't. So every first-order linear recurrence is exactly one of the two types, never both, and never neither. Classifying one means checking f of n against that distinction. Not glancing at whether the equation looks complicated.

Table 8.9.1

Classifying by f(n)

This table classifies five recurrences by their f of n. Only the first, three times the previous term, has f of n equal to zero. It's homogeneous. The rest are all non-homogeneous, even though their f of n take very different forms. A positive constant, a negative constant, and a quadratic function of n. f of n doesn't have to be a constant, or even simple. It can be any function of n alone. The classification depends only on whether it's the zero function. And the distinction matters. Section eight point ten solves the two types with different techniques.

Figure 8.9.1

The Extra Arrow

This picture shows the two types. Both chains have the same basic structure. Each term receives exactly one arrow from the term before it, scaled by c. The homogeneous chain, on top, has no other input. The non-homogeneous chain adds an extra arrow into every term after a zero, contributing f of n at step n. That extra arrow is exactly what the at-least-one-nonzero condition detects. Notice what kinds of processes produce each type. A quantity that only grows or shrinks by a fixed proportion, with nothing added from outside, is homogeneous. Almost any process with an ongoing outside contribution, like new arrivals, appended records, or incoming requests, becomes non-homogeneous the moment that contribution is nonzero.

8.9.3 Modeling

4 Questions, Every Time

Turning a word problem into a recurrence is a modeling skill, not a computation. It helps to ask the same four questions every time. First, what does a n represent? Identify the quantity, and confirm it's indexed by a discrete step, like a day, a call, a round, or an iteration. Second, what happens to the previous value? If a fixed proportion of it carries over, that proportion is c. Third, what new contribution enters at step n, that didn't come from the previous value at all? That's f of n. It may be zero, a constant, or a function of n. Fourth, what's the value at the start? That's the initial condition. Those four answers are all the definition requires.

A Worked Modeling Example

An Archive That Doubles Daily

Here are the four questions in action. A backup archival system duplicates its entire existing archive every day, for redundancy. It also appends m newly generated log entries each day. a n tracks the total number of archived entries after day n. The entire previous archive is duplicated, fully doubled, so c is two. m new entries are appended each day, however large the archive already is. So f of n is the constant m. And a zero is the archive's size before duplication began. So a n equals two a n minus one, plus m. Since m isn't zero, it's non-homogeneous. Here c is two, bigger than one. The previous term is amplified, not shrunk. The definition places no restriction on c, as long as it's constant.

Worked Examples 8.9.B and 8.9.C

Cache Eviction, and the Alerts

A distributed cache holds five hundred thousand entries when monitoring begins. An eviction policy removes twenty percent of stored entries each cycle, and nothing new is added. So eighty percent carries over, c is zero point eight, f of n is zero, and a zero is five hundred thousand. It's homogeneous. The first two cycles leave four hundred thousand, then three hundred twenty thousand. Now complete the opening alerts. Seventy-five percent carries over, so c is zero point seven five. The new contribution at step n is n alerts, so f of n equals n. And a zero is twenty. That's non-homogeneous, and its f of n isn't even constant. It grows with n. The totals so far, twenty, sixteen, fourteen, are slowly declining. But will that continue, reverse, or level off as more alerts arrive each day? That's a long-run question, and it's exactly what section eight point ten answers.

Takeaways

Carry Over, Add, Start

To summarize. A first-order linear recurrence expresses each term using exactly one preceding term, times a constant, plus a term depending only on n. An initial condition is required alongside it. The equation alone doesn't fix a unique sequence. It's homogeneous exactly when f of n is zero for every n. And setting one up means finding what's tracked, what carries over, what's new, and where it starts. Here's something to think about. Suppose a recurrence has f of one, f of two, and f of three all equal to zero, but f of four equals seven. Is it homogeneous? If someone computed only the first three terms, what wrong conclusion might they draw? And why does classification require examining the formula for f of n itself, rather than a finite list of its values?

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 UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks 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 First-Order Linear Recurrence Relations

What is a first-order linear recurrence relation?
A first-order linear recurrence has the form a_n = c\,a_{n-1} + f(n) for every n \ge 1, where c is a constant and f(n) depends only on n. It is first-order because each term uses one preceding term. It is linear because a_{n-1} is only multiplied by the constant c, not squared or placed inside another function.
Why does a recurrence relation need an initial condition?
An initial condition is needed because the recurrence only links consecutive terms, so without a starting value a_0 infinitely many sequences satisfy it. For a_n = 3a_{n-1} + 2 with a_0 = 1, you get a_1 = 5, a_2 = 17, and a_3 = 53. The relation plus the start determines every term.
How do you tell whether a first-order linear recurrence is homogeneous or non-homogeneous?
Check f(n): the recurrence is homogeneous only if f(n) = 0 for every n, so it reduces to a_n = c\,a_{n-1}. It is non-homogeneous if f(n) is nonzero for at least one n. Nonzero constants, positive or negative, and quadratics in n all make it non-homogeneous. Complicated-looking equations do not decide the type.
How do you turn a word problem into a first-order linear recurrence?
Answer four questions: what a_n represents, what fraction of the previous value carries over (that is c), what new amount enters at step n (that is f(n)), and what the starting value a_0 is. For example, an archive that doubles daily and adds m entries gives a_n = 2a_{n-1} + m, which is non-homogeneous.

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 syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →