Proof by Induction (Lesson 7.4 Day 1)
Unit 7 - Day 8
Understand what constitutes as mathematical proof
Explain the importance of the base case, induction hypothesis, and induction step in writing a proof by induction
Quick Lesson Plan
Students start with an interesting “would you rather” question that will provide the framework for the rest of the lesson. Give students time to discuss in their group and then have students share out. You can do this mini-debrief before having groups move on to question 2. Make sure some students can articulate why Option B is better if you want to guarantee many, many sunny days. Some groups said since they can’t predict the weather or guarantee that first sunny day it’s better to just run 5 miles, but this is unsustainable in the long run! The best case scenario would of course be to have both options--run on the first day to guarantee the first sunny day, and then have Option B to guarantee sunny weather every day after that. In fact, that’s exactly how a proof by induction works!
In this lesson students work to prove a formula for the sum of the first n integers. To check that a formula works, students find the sum in two different ways, once “by hand” and once by using the formula. If these two methods are the same, we have some evidence that the formula is correct. In question 5b, we want students to use their answer for S to find S . Since they already know the previous sum, the only thing left to add is the very last term, a . This becomes a critical component of a proof by induction, since it is how we incorporate the induction hypothesis.
You may wish to debrief the rest of the front page before moving on to the back, where we now use the infamous “kth term” to build our proof.
The goal of today’s lesson is to build the conceptual framework around a proof by induction. Tomorrow will provide many more opportunities to actually write these proofs. Today’s activity and debrief should reveal these three big ideas:
Proving a formula works for 1, 2, or even 100 terms is not enough to prove that it works for all terms.
We can always show that the sum formula works for a specific value of n by actually finding the sum the long way (brute force) and showing that it matches the formula. This is why we are able to make the induction hypothesis.
Just as tomorrow’s sunny day became today, and then ensures another sunny day the following day, the “next term” becomes the current term, thus ensuring that the formula also works for the next term after that and so on.
At the end of the debrief, return to the idea that a proof by induction is actually a combination of Option A and Option B. By completing the base case we are ensuring that first sunny day instead of having to wait around for something that may never come. The induction step allows us to say that if it is sunny today then it will be sunny tomorrow, thus instigating a never ending chain reaction
Most of our proofs focus on proving sum formulas, so the Important Ideas are geared around proving a formula for S(n). The steps follow analogously for other types of proof by induction (like proving an expression is divisible by a certain number).
In our class we did the first Check Your Understanding problem as a whole class so students get an idea of the entire process. We saved the second question for the next day.
Note: We use the phrases “w/ formula” and “w/o formula” to distinguish the two methods for arriving at the sum (which they then prove are equivalent). You could just as easily call these “w/ formula” and “recursively” or “w/ formula” and “using previous sum”.
Many students struggle with the idea of the induction hypothesis. Why are we able to assume this when we’ve been adamant about proving everything else? The perspective we take in this lesson is that we know we can verify a formula works for any specific value of n (even if it takes a while by brute force). Now we need to show the formula works for all values of n that follow. After having proven the induction step, we know that “the next term” is guaranteed. The previous term could have been the base case, but it doesn’t have to be. We want to consider the possibility that our sunny day today was not because yesterday was the first ever sunny day, but because even a sunny day much further along in the chain can guarantee our sunny day today. This is because the sunny day is what gets the ball rolling and what keeps the ball rolling. The very first sunny day sets everything in motion, but the following sunny days keep things in motion. Just like with dominoes: the first domino starts everything but it technically does not get the 57th domino to fall over. It is the 56th domino that makes the 57th domino fall over. So any sunny day guarantees a sunny day on the next day. This is the rationale behind assuming the formula works up to the kth term.