Introduction to Sequences | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

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

Introduction to Sequences

Discrete Mathematics · Chapter 3: Sequences and SeriesSection 3.1 · lesson 17 of 879 min · free with a free account

← Surjective and Bijective FunctionsNext lesson: Finite vs. Infinite Sequences →

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

Ordered lists of numbers - given directly, or built from what came before.

  • Define a sequence as a function on the natural numbers
  • Contrast a sequence with a set
  • Write explicit and recursive definitions of a sequence
  • Reconcile 0-indexed and 1-indexed descriptions

Transcript

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

Sequences and Series

Introduction to Sequences

Chapter three is about sequences and series. This first section builds the formal idea of a sequence. We'll define a sequence as a function, and contrast it with a set. We'll write sequences two ways, explicitly and recursively. And we'll see how to reconcile the two common indexing conventions, zero-indexed and one-indexed.

The Opening Problem

Index 0 or Index 1?

A log-analysis system records a server's response time, in milliseconds, once every minute. One hundred twenty, ninety-five, one hundred forty, one hundred ten, and so on. The moment a developer refers to the first recorded value in code, a small but consequential question appears. Is that value stored at index zero, or index one? The array itself doesn't care. But every formula written about the data will. This section builds the formal object behind that everyday list of numbers, a sequence, and the notation used to describe it.

Definition

A Sequence Is a Function

A sequence is a function whose domain is the natural numbers. Or, depending on the starting index, a set of the form k, k plus one, k plus two, and so on. Its values come from some set of interest, such as the real numbers. Rather than writing a of n, as with an ordinary function, we write a sub n, and call it the n-th term of the sequence. The sequence as a whole is written with braces around a sub n, or listed out as a zero, a one, a two, and so on. Or starting from a one, depending on convention.

Sequence vs Set

A Sequence Keeps What a Set Discards

Section two point one established that a set has no order, and no meaningful repetition. A sequence is built to do exactly the opposite job. Take the log as a sequence. a one is one hundred twenty, a two is ninety-five, a three is one hundred forty, and a four is one hundred ten. Swap the first two terms, and you get a different sequence. a one is now ninety-five, even though every value that appears is the same. Written as a set, both orderings collapse to the identical four-element set, since a set discards order entirely. In a sequence, order is part of what it is. And a value may recur at several positions, without collapsing into one, the way repeated elements do in a set. A sequence deliberately keeps what a set deliberately discards.

Explicit Definitions

A Formula Straight From n

A sequence is defined explicitly, or given in closed form, when a formula computes a sub n directly from n, with no reference to any other term. Any term can be found by substituting its index into the formula, independent of every other term. Here's a clean example. A savings account earns five percent interest per period, starting from a principal of one thousand dollars. Let a sub n be the balance after n periods. Then a sub n equals one thousand times one point zero five to the n, for n equal to zero, one, two, and so on. Each term is computed straight from n, without needing any balance that came before it.

Figure 3.1.1

The Sequence, Drawn as a Function

This figure draws the compound-interest sequence as the function it is. Each index n on the left maps, via the rule a, to exactly one term on the right. Zero maps to one thousand. One maps to one thousand fifty. Two maps to one thousand one hundred two dollars and fifty cents. And three maps to about one thousand one hundred fifty-seven dollars and sixty-three cents. The same picture applies to any sequence. Only the rule, and the values it produces, change.

Recursive Definitions

Build Each Term From Earlier Ones

A sequence is defined recursively when one or more starting terms are given outright, called the base case. Every later term is then computed from one or more earlier terms, by a fixed rule called the recurrence relation. Finding a sub n this way generally means working through every earlier term the rule depends on. The savings account has a natural recursive description. Each period's balance is one point zero five times the previous balance. So the base case is a zero equals one thousand. And the recurrence is a sub n equals one point zero five times a sub n minus one, for n at least one. Computing forward, a one is one thousand fifty, a two is one thousand one hundred two fifty, and a three is about one thousand one hundred fifty-seven sixty-three. Those match the explicit formula, term for term. The two definitions describe the identical sequence.

More Than One Earlier Term

The Fibonacci Sequence

A recurrence can depend on more than one earlier term. The Fibonacci sequence sets a zero equal to zero and a one equal to one as base cases. Then each term is the sum of the two before it. Zero, one, one, two, three, five, eight, thirteen, and so on. Computed the naive way, finding the thirtieth term recomputes many smaller terms over and over. a thirty needs a twenty-nine and a twenty-eight. And a twenty-nine independently needs a twenty-eight again, and so on. The cost grows rapidly with n, unless earlier results are stored and reused, or an explicit formula is used instead, where one exists.

Table 3.1.1

Explicit vs Recursive

This table compares the two styles. An explicit definition finds a sub n by substituting n into a formula. It needs no earlier terms, and it can jump straight to the hundredth term in one step. A recursive definition applies the rule, starting from the base case. It needs at least one earlier term, and reaching the hundredth term means computing every earlier term it depends on. Both styles can describe the same sequence, just as roster and set-builder notation could describe the same set. They simply trade off differently.

Terms, Indexing, Conventions

0-Indexed or 1-Indexed

The value a sub n is called the n-th term of the sequence, and n is called its index. Whether the first term is a zero or a one is a matter of indexing convention, not a mathematical requirement. Both describe sequences perfectly well. Programming languages such as Python, Java, and C store arrays zero-indexed, so a zero is the first stored value. Everyday counting, first, second, third, matches a one as the first term. That's a frequent source of off-by-one confusion when the two conventions meet. This course uses whichever index keeps a formula cleanest, and states it explicitly each time.

Reindexing

The Off-by-One Trap

The two conventions describe the same data only after an explicit reindexing. Suppose the response-time log is stored zero-indexed as a sub n, so a zero, one hundred twenty, is the first reading. A separate report describes the same data one-indexed as b sub n, where b one is labeled minute one's reading. Since b one and a zero refer to the same value, in general b sub n equals a sub n minus one. Equivalently, a sub n equals b sub n plus one. Mixing up which convention a formula assumes shifts every term by one position, without necessarily producing any error. That's exactly what makes an off-by-one mismatch so hard to catch.

Takeaways

Ordered, Indexed, Defined 2 Ways

To summarize. A sequence is a function from the natural numbers to a set of values. Unlike a set, order matters, and repeated values are meaningful. a sub n denotes the n-th term. An explicit definition computes it directly from n, and a recursive definition builds it from a base case and earlier terms. A recurrence can depend on more than one earlier term, and computing a distant term naively can cost far more than an explicit formula. And starting at zero or one is a convention. Reconciling two descriptions of the same data needs an explicit reindexing formula. Here's something to think about. A colleague says a five is the fifth term. Under which convention is that true, and under which is it the sixth? Describe a concrete way that ambiguity could cause an off-by-one bug, in code that never raises an error.

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 Introduction to Sequences

What is a sequence in discrete math?
A sequence is a function whose domain is the natural numbers (or consecutive integers starting at some k), with values drawn from a set such as the real numbers. Instead of writing a(n), the value at index n is written a_n and called the n-th term. The whole sequence is written \{a_n\} or listed as a_0, a_1, a_2, \ldots.
How is a sequence different from a set?
A sequence keeps order and counts repeated values, while a set ignores both. Swapping the first two terms of 120, 95, 140, 110 gives a different sequence, yet both orderings give the same set \{120, 95, 140, 110\}. A value can also appear at several positions in a sequence without merging into a single term.
What is the difference between an explicit and a recursive definition of a sequence?
An explicit definition computes a_n directly from n, while a recursive definition gives a base case and a rule that builds later terms from earlier ones. For 1000 dollars earning 5% interest per period, the explicit form is a_n = 1000(1.05)^n. The recursive form is a_0 = 1000 and a_n = 1.05\,a_{n-1} for n \ge 1. Both give a_1 = 1050.
How do you convert between 0-indexed and 1-indexed sequences?
Use an explicit reindexing formula. Let a_n be the 0-indexed version, so a_0 is the first value, and let b_n be the 1-indexed version, so b_1 is the first value. Then b_n = a_{n-1}, or equivalently a_n = b_{n+1}. Mixing up the conventions shifts every term by one position, an off-by-one error that may raise no warning.

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 →