Principles of Mathematical Induction | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

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

Principles of Mathematical Induction

Discrete Mathematics · Chapter 4: Mathematical InductionSection 4.1 · lesson 25 of 879 min · free with a free account

← Practice: Arithmetic and Geometric SeriesNext lesson: Constructing Proofs by Induction →

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

Proving a statement for every positive integer - with a finite amount of work.

  • State the base case and inductive step
  • Explain why induction is valid, using well-ordering
  • Describe what makes induction "weak"
  • Write a complete induction proof

Transcript

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

Mathematical Induction

Principles of Mathematical Induction

Chapter four is about mathematical induction, a technique for proving a statement about every positive integer, using only a finite amount of work. This section lays out its two-part structure, and explains why that structure is logically valid, rather than merely convenient. Then it works through one complete proof. Section four point two takes on harder examples, and a stronger version of the technique.

The Opening Problem

A Pattern in a Nested Loop

A developer profiling a sorting routine notices a pattern in a nested loop. On its first pass, the inner loop runs once. On the second, twice. On the third, three times, and so on, through n passes. Counting the total by hand is easy for small cases. One, then one plus two is three, then six, then ten. Each matches the formula n times n plus one, over two. So it's tempting to conclude the formula is simply correct. But the routine might process an input of size ten thousand, or ten million, and nobody has checked those by hand. Matching a formula against a handful of small examples, though, isn't the same as knowing it holds for every positive integer. And a claim that fails even once, for some large untested n, is false as a general statement, however many small cases it passed.

Definition

The Principle of Mathematical Induction

Let P of n stand for a statement whose truth depends on a positive integer n. For instance, one plus two, up to n, equals n times n plus one over two. Induction proves P of n for every integer n from some starting value n zero onward, by establishing exactly two things. First, the base case. Show directly that P of n zero is true. Second, the inductive step. For an arbitrary k, at least n zero, show that if P of k is true, then P of k plus one is also true. The assumption that P of k is true is called the inductive hypothesis. Neither piece is optional, and neither is enough alone. The base case by itself is a true statement about one number. It says nothing about the next. And the inductive step by itself is a conditional. It never asserts that any particular case actually holds, so it has nothing to attach to. Only once the base case supplies one confirmed instance does the chain of implications have somewhere to start.

The Chain

One Anchor, Endless Links

Picture it as a chain. The base case anchors the chain at P of one. Each arrow is one application of the inductive step. P of one gives P of two, which gives P of three, and so on. But any picture only ever shows finitely many links. So what actually justifies concluding that P holds for every positive integer? That rests on a basic property of the positive integers.

Why Induction Works

The Well-Ordering Principle

The well-ordering principle says every nonempty set of positive integers has a least element. It's taken as a foundational property. Here's why the base case and inductive step guarantee P for every n. Suppose both are established, but suppose P is nonetheless false for some integer. Let C be the set of all integers, at least n zero, where P fails. By supposition, C isn't empty. So by well-ordering, it has a least element. Call it m. The base case says P of n zero is true, so m isn't n zero. That means m minus one is at least n zero. And since m is the least element of C, m minus one isn't in C. So P of m minus one is true. Now the inductive step, applied at m minus one, says P of m is true. That contradicts m being in C, where P is false. So C must be empty, and P holds for every n. That's why induction is a legitimate proof technique, not a convenient shortcut.

Weak Induction

Each Step Leans on One Predecessor

The version of induction just defined is called weak induction. The name refers to what the inductive step may assume. In proving P of k plus one, weak induction uses only the single previous statement, P of k. Not all the earlier cases, even though they've all been established. A physical image helps. Picture a row of dominoes, each tall enough to knock over only the domino directly in front of it. Knocking over the first domino is the base case. Each domino knocking over the next is the inductive step. And a domino's fall depends only on the one directly behind it, not the whole history of dominoes that already fell. Each step leans on exactly one predecessor. Some statements genuinely need several earlier cases at once. Section four point two introduces strong induction for those.

A Fully Worked Proof

The Sum of the First n Integers

Now a complete proof, of the claim from the opening. For every positive integer n, one plus two, up to n, equals n times n plus one, over two. Let P of n be that statement. The base case is n equal to one. The left side is one. The right side is one times two, over two, which is also one. They're equal, so P of one is true. For the inductive step, let k be an arbitrary positive integer, and assume P of k. One plus two, up to k, equals k times k plus one, over two. We must show P of k plus one. One plus two, up to k plus one, equals k plus one times k plus two, over two.

The Inductive Step

Use the Hypothesis, Then Factor

Start from the left side of P of k plus one, and group the first k terms. That's the sum up to k, plus k plus one. The inductive hypothesis replaces the bracketed sum with k times k plus one, over two. Now factor k plus one out of both terms. That leaves k plus one, times k over two plus one, which is k plus one times k plus two, over two. That's exactly the right side of P of k plus one. So the inductive step is established, for an arbitrary k. Both the base case and the inductive step hold. So by the principle of mathematical induction, the formula is true for every positive integer n.

Figure 2

A Picture for n = 5

Here's a complementary way to see the same formula, for n equal to five. A staircase of one, two, three, four, and five unit squares, in green, combined with an upside-down copy of itself, in gold, exactly fills a five-by-six rectangle. So twice the sum from one to five equals five times six, matching the formula. But that's a one-picture argument for n equal to five specifically. It isn't a proof for every n. Only the induction argument does that.

Finitely Many Checks vs a Proof

A Different Kind of Argument

Return to the opening with this proof in hand. Running the loop, and printing the total for n from one to a thousand, would confirm the formula in every one of those thousand cases. But that check, however extensive, is still a check of finitely many cases. The induction proof is a fundamentally different kind of argument. One base case and one inductive step, a single finite piece of reasoning that covers every positive integer. That includes every n a running program will ever actually encounter.

Anatomy of an Induction Proof

What Breaks if a Piece Is Missing

This table isolates what each piece of an induction proof is responsible for, and what breaks without it. Without the base case, the inductive step becomes a chain of implications with nothing true to start from. P of k implies P of k plus one may be perfectly valid, and still never fire. Without the inductive step, only P of n zero is known. Nothing connects it to any larger n. And without the well-ordering principle, there's no guarantee that a set of counterexamples would have a smallest member. The contradiction argument would have no logical footing.

Takeaways

A Finite Argument About Infinitely Many Cases

To summarize. Mathematical induction proves P of n for every integer from n zero on, using a base case, and an inductive step for an arbitrary k. Both are necessary, and only together are they sufficient. Induction is valid because of well-ordering. A least counterexample would contradict them both. Weak induction's inductive step uses only the single previous case. And checking many specific values, however many, is never a proof for all n. Here's something to think about. A student objects that assuming P of k, to prove P of k plus one, assumes the very thing we set out to prove. Isn't that circular? Explain precisely why not. Does the inductive step claim that P of k is true, or something else about the relationship between the two? And what role does the base case play?

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 Principles of Mathematical Induction

What are the base case and inductive step in mathematical induction?
Induction proves P(n) for every integer n \ge n_0 by establishing two things. The base case shows directly that P(n_0) is true. The inductive step takes an arbitrary k \ge n_0, assumes P(k) (the inductive hypothesis), and shows P(k+1) follows. Both pieces are required, and neither is enough alone.
Why is mathematical induction a valid proof technique?
Induction is valid because of the well-ordering principle, which says every nonempty set of positive integers has a least element. If P failed somewhere, the set of failures would have a least element m. The base case means m > n_0, so P(m-1) is true. The inductive step then gives P(m), a contradiction.
What makes induction "weak" induction?
Induction is called weak when the inductive step assumes only the single previous statement. To prove P(k+1), it uses just P(k), not the earlier cases P(1), \dots, P(k-1), even though those have all been established. The domino picture fits: each domino knocks over only the one directly in front of it.
How do I write a complete induction proof that 1+2+\cdots+n = \frac{n(n+1)}{2}?
Check the base case, then prove the inductive step. For n=1, both sides equal 1. Assume 1+\cdots+k = \frac{k(k+1)}{2}. Then 1+\cdots+k+(k+1) = \frac{k(k+1)}{2}+(k+1) = (k+1)\left(\frac{k}{2}+1\right) = \frac{(k+1)(k+2)}{2}, which is P(k+1). By induction, the formula holds for every positive integer n.

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 →