UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 4.2 Free with a free account
Constructing Proofs by Induction
Discrete Mathematics · Chapter 4: Mathematical InductionSection 4.2 · lesson 26 of 8714 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Discrete Mathematics.
Lesson complete
Earn the 4 college credits for Discrete Mathematics
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Counting Outcomes and Sample Spaces →← Principles of Mathematical InductionNext lesson: Counting Outcomes and Sample Spaces →
In this lesson
From knowing the idea to writing a proof a reviewer will accept.
- Write an induction proof with a complete, standard structure
- Prove divisibility, inequality and series claims
- Use strong induction when the step reaches back further
- Spot the 2 mistakes that quietly invalidate a proof
Transcript
Everything said in the video, section by section (2,084 words). Read along, or search it.
Mathematical Induction
Constructing Proofs by Induction
Section four point one explained why induction works. This section is about doing it, turning the idea into a written proof that someone else will accept as complete. We'll use one standard structure, apply it to three different kinds of claims, and then meet strong induction, for steps that need more than the previous case. And we'll look at two mistakes that let a proof look finished, while establishing nothing at all.
The Opening Problem
A Folder Always One Level Deeper
A backend engineer writes a recursive function, to compute the total storage cost of a nested folder structure. They want to know it returns the correct total, no matter how deeply the folders are nested. Not just for the three test folders sitting in the test suite. Running the function on deeper and deeper test cases never fully answers that. There's always a folder one level deeper than whatever was tested last. Induction is the tool that closes that gap, for infinitely many cases at once. But knowing the two ingredients, a base case and an inductive step, isn't yet the same skill as writing a proof that a grader, or a code reviewer, would accept. That second skill is what this section is about. Along with recognizing when the version of induction from section four point one isn't strong enough.
4.2.1 The Formal Write-Up
A Proof-Writing Template
Every rigorous induction proof follows the same written structure, whatever it's proving. First, state the claim. Write the precise statement P of n, and the range of integers it covers. Second, the base case. Verify P of n zero directly, at the actual starting value. Not automatically at n equals one. Third, the inductive hypothesis. Write, assume P of k is true, for some fixed, arbitrary integer k, at least n zero. Fourth, the inductive step. Show that P of k plus one follows. And explicitly flag the line where the hypothesis is used, with a note like I H, so a reader can check it was really invoked. Fifth, the conclusion. Close with an explicit sentence. Therefore, by the principle of mathematical induction, P of n holds for all integers from n zero on.
Phrasing Habits
Fixed k, and Every Line Has a Reason
Two phrasing habits in that template deserve a closer look. First, the inductive hypothesis is always about a fixed k. Think of k as a specific but unlabeled integer, not a variable ranging over everything at once. It's never, P of n is true for all n. That would assume the very thing being proved. Second, the inductive step should read as a derivation, not an assertion. Every line follows from the one before it, by a stated reason. Algebra, a definition, or the inductive hypothesis. This isn't a stylistic preference. As we'll see at the end of this section, most invalid induction proofs fail because one of these parts was skipped, misphrased, or never actually used.
Worked Example 4.2.1
A Divisibility Claim
The same template applies unchanged, whether the claim is about divisibility, an inequality, or a series. Only the algebra inside the step changes. The first example is a divisibility claim. For every integer n, at least one, six divides seven to the n, minus one. Facts like this, a fixed base raised to a power, minus one, always divisible by a fixed number, are used to double-check computations in hashing and cryptographic routines. Base case. Seven to the first, minus one, is six, and six divides six. Inductive hypothesis. For some fixed, arbitrary k, six divides seven to the k, minus one. Writing that as an equation, seven to the k, minus one, equals six m, for some integer m. The goal is to show that six divides seven to the power k plus one, minus one.
Worked Example 4.2.1
Rewrite So the Hypothesis Appears
Start with seven to the power k plus one, minus one. That's seven times seven to the k, minus one. Now the key move. Rewrite that as seven times the quantity seven to the k minus one, plus six. Expand it, and you'll see it's the same number. Why do that? Because now the expression from the hypothesis appears inside. So by the inductive hypothesis, it's seven times six m, plus six. And that factors as six times the quantity seven m plus one. Since seven m plus one is an integer, six divides seven to the power k plus one, minus one. That completes the step. So by the principle of mathematical induction, six divides seven to the n, minus one, for every n from one on.
Worked Example 4.2.2
An Inequality with a Surprising Start
The second example is an inequality. For every integer n, at least five, n squared is less than two to the n. Why start at five? Checking small cases first shows why it matters. At n equals one, one is less than two. True. But at two, four isn't less than four. At three, nine isn't less than eight. And at four, sixteen isn't less than sixteen. All false. At five, twenty-five is less than thirty-two. And from there on, it stays true. So the base case that must actually be verified is n equals five. Five squared is twenty-five, two to the fifth is thirty-two, and twenty-five is less than thirty-two.
Worked Example 4.2.2
An Algebraic Fact, Then a Chain
The hypothesis is that k squared is less than two to the k, for a fixed, arbitrary k, at least five. The goal is k plus one, squared, less than two to the power k plus one. First, an algebraic fact. Two k squared, minus k plus one squared, simplifies to k times k minus two, minus one. At k equals five, that's fourteen. And it only grows as k increases. So for every k from five on, two k squared is bigger than k plus one, squared. Now chain that fact with the hypothesis. k plus one, squared, is less than two k squared. And multiplying both sides of the hypothesis by two, two k squared is less than two times two to the k, which is two to the power k plus one. So k plus one, squared, is less than two to the power k plus one. By induction, n squared is less than two to the n, for every n from five on.
Worked Example 4.2.3
A Series Formula: Sum of Squares
The third example is a series formula. For every n, at least one, the sum of i squared, from one to n, equals n times n plus one, times two n plus one, all over six. Chapter three derived arithmetic and geometric sums with a pairing argument, a technique specific to those two series types. Induction proves series formulas by an entirely different route. It works even for a sum like this one, a sum of squares, that pairing doesn't handle neatly. Base case. At n equals one, the left side is one squared, which is one. The right side is one times two times three, over six, which is also one. The hypothesis is the formula at k. And the goal is the sum up to k plus one, equal to k plus one, times k plus two, times two k plus three, over six.
Worked Example 4.2.3
Peel Off the Last Term
Start by peeling off the last term, using the splitting rule from section three point five. The sum to k plus one is the sum to k, plus k plus one, squared. The inductive hypothesis replaces the sum to k with its formula. Now factor out k plus one, and put everything over six. Inside the bracket, that's k times two k plus one, plus six times k plus one. Multiplying out, the bracket becomes two k squared, plus seven k, plus six. And k plus two, times two k plus three, is exactly two k squared plus seven k plus six. So the result matches the target. That completes the step. By induction, the sum of squares formula holds for every n from one on.
4.2.3 Strong Induction
When One Previous Case Isn't Enough
Every step so far derived the k plus one case using only the k case. Some claims can't be organized that way. The most natural argument for k plus one depends on a different earlier case, sometimes an unpredictable one. Strong induction, also called complete induction, widens the hypothesis to make that possible. First, verify as many consecutive base cases as the step actually needs before it can be applied. Second, the strong inductive step. Assume P of m holds for every m from n zero up to k, and show P of k plus one. The only difference from section four point one is that hypothesis. It covers every prior case in range, not only k itself.
Worked Example 4.2.4
Memory from 3 GB and 8 GB Modules
Here's an example. A server rack can only be expanded with add-on memory modules sold in two fixed sizes, three gigabytes and eight gigabytes. The claim is that every total capacity of fourteen gigabytes or more can be assembled as three a, plus eight b, for some nonnegative integers a and b. Base cases. Fourteen is two threes and one eight. Fifteen is five threes. Sixteen is two eights. The strong hypothesis assumes every m, from fourteen up to k, has this form, for some fixed, arbitrary k, at least sixteen. Now take k plus one, and remove one three gigabyte module. That leaves k minus two. Since k is at least sixteen, k minus two is at least fourteen, so it's covered by the hypothesis. Write it as three a plus eight b. Then k plus one is three times a plus one, plus eight b. Again the required form. So by strong induction, every capacity of at least fourteen gigabytes can be built from three and eight gigabyte modules alone.
Figure 4.2.1
How Far Back the Step Reaches
This picture shows the difference in how far back each step reaches. In standard induction, on the top row, each case leans on the one immediately before it. The case for eighteen comes from seventeen. In strong induction, on the bottom row, the step for eighteen depends on fifteen, three places back, not on seventeen. Because the step reaches back three places, three consecutive base cases, fourteen, fifteen, and sixteen, have to be verified directly before the pattern can take over.
Table 4.2.1
A Checklist for a Complete Proof
This checklist maps each part of the template to the way it most often goes wrong. The base case needs explicit verification, at the starting value the step actually needs. The failure is skipping it, or checking a different n. The hypothesis must be about one fixed, arbitrary k. Or for strong induction, every case from the base through k. The failure is phrasing it as true for all n. The step needs a derivation that visibly invokes the hypothesis. The failure is never actually using it, or using it without saying where. And the conclusion needs an explicit closing sentence. The failure is leaving it implicit, or stopping right after the algebra.
4.2.4 Common Mistakes
Proofs That Read Well and Prove Nothing
Two of these failures deserve a closer look, because both produce a proof that reads smoothly and confidently, while establishing nothing. Mistake one is an unjustified base case. Suppose a proof of n squared less than two to the n checked the base case at one, where it happens to be true. Then it attempted the same inductive step as before. That step relies on the fact that two k squared exceeds k plus one squared, which is only true from five on. The proof would report a false theorem at two, three, and four, while looking complete on paper. Mistake two is a circular assumption. Assume six divides seven to the n minus one, for all n. In particular, it divides seven to the power k plus one, minus one. Done. Nothing was derived there. The argument assumed the universal claim as its premise, then restated a special case of it as the conclusion. The correct hypothesis assumes the claim for one fixed k only, and the step must actually derive the next case from it.
Takeaways
Structure Is What Makes It a Proof
To summarize. A complete induction proof states the claim, and checks the base case directly. It assumes P of k for one fixed, arbitrary k. Then it derives P of k plus one, with the hypothesis flagged, and it concludes. The same structure fits divisibility claims, inequalities, and series formulas. Only the algebra in the step changes. Strong induction assumes every case from the base through k, which is necessary whenever the step reaches back further than one case. And a base case checked at the wrong value, or a hypothesis phrased for all n, invalidates a proof just as thoroughly as a missing step. Here's something to think about. Could the memory module step be rewritten to use only P of k, never mentioning k minus two? Try rewriting it using only the case immediately before, and see specifically what breaks.
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
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 Constructing Proofs by Induction
What are the steps of a complete proof by induction?
How do you prove a divisibility statement like 6 \mid 7^n - 1 by induction?
When do you need strong induction instead of ordinary induction?
What mistakes make an induction proof invalid even if it looks complete?
About the Discrete Mathematics course
How many college credits is Discrete Mathematics?
How much does Discrete Mathematics cost and what is included?
Which universities accept UPI Study credits?
How long does Discrete Mathematics take?
How are the exams done?
How do my credits reach my college?
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.
4 credits · NCCRSEnroll →