13.4 Proof by induction

Proof by induction

Going over last night’s homework, make sure they got the right formulas. For an arithmetic series, $S_n=\frac{n}{2}(t_1+t_n)$ . For a geometric, $S_n=\frac{t_1{r}^n-t_1}{r-1}$ , in some form or another.

Anyway, on to today’s topic.

Today, we’re going to learn a new way of proving things. This method, called“proof by induction,”is a very powerful and general technique that turns up in many different areas of mathematics: we are going to be applying it to series, but the real point is to learn the technique itself.

So...to begin with, we are going to prove something we already know to be true:

$1+2+3+4...n=\frac{n}{2}(n+1)$

Of course we know how to prove that using the arithmetic series trick, but we’re going to prove it a different way.

Let’s start by seeing if that formula works when $n=1$ : in other words, for a 1-term series. In that case, what is the left side of the equation? (Even this seemingly innocuous question can baffle good students sometimes. Give them a minute. Point to the equation. Remind them that the equal sign divides any equation into a left side, and a right side. So, what is the left side of this equation, when there is only one term?) Yes, it is just...1.

How about the right side? Well, that’s... $\frac{1}{2}(1+1)=1$ . So at least, for this particular case, it works.

To build up to the next step, ask this hypothetical question. Suppose we had not yet proven that this equation always works. But suppose that I had proven that it works when $n=200$ . Just say, I had sat down with my calculator and added up all the numbers from 1 to 200, which took a very long time, but in the end, I did indeed get what the formula predicts (which is, of course, $100\times 201=20,100)$ . And now I ask you to confirm that the formula works when $n=201$ .

Well, you can do the right side easily enough: $\frac{\text{201}}{2}\left(202\right)=20,301$ . But what about the left side? Do you have to add up all those numbers on your calculator? No, you don’t, if you’re clever. (See if they can figure this next part out—this is the key.) I already told you what the first 200 numbers add up to. So you can simply add 201 to my total. $20,100+201=20,301$ .

The point here is not just“it works.”The point is that you can confirm that it works, without adding up all 200 numbers again , because I already did that part—all you have to add is the last number.

Now...suppose I had already proven that it works for $n=325$ . How would we show that it works for $n=326$ ? Good—we would add 326 to the old answer (for $n=325$ ), and see if we got what the formula predicted we should get for $n=326$ . Let’s try it...

Now...suppose I had already proven that it works for $n=1000$ . How would we show that it works for $n=1001$ ? Good—we would add 1001 to the old answer (for $n=1000$ ), and see if we got what the formula predicted we should get for $n=1001$ . Let’s try it... Repeat this exercise until they are sick of it, but boy, do they get it. Then hit them with the big one: what is the general form of this question ? See if they can figure out that it is:

Suppose I had already proven that it works for some $n$ . How would we show that it works for $n+1$ ?

Give them time here...see if they can find the answer...

We would add $(n+1)$ to the old answer (for $n)$ , and see if we got what the formula predicted we should get for $(n+1)$ .

What does that look like? Well, for the old $n$ , the formula predicted we would get $\frac{n}{2}(n+1)$ . So if we add $(n+1)$ to that, we get $\frac{n}{2}(n+1)+(n+1)$ . And what should we get? Well, for $(n+1)$ , the formula predicts we should get $\frac{n+1}{2}(n+1+1)$ .

Do the algebra to show that they are equal. Then, step back and say...so, what have we done? Well, first we proved that the formula works for $n=1$ . Then we proved—not for one specific case, but quite generally—that if it works for any number, it must also work for the next number . If it works for $n=1$ , then it must work for $n=2$ . If it works for $n=2$ , then it must work for $n=3$ ....and so on. It must always work.

At this point, I think it’s helpful to work through one more example. I recommend going through $\Sigma \frac{1}{n(n+1)}$ , just as it is done in the Conceptual Explanations. This time, you’re using a little less explanation and focusing more on the process, so it makes a better model for their homework.

Homework:

At this point, you’re ready for the test. Unlike most of my“Sample Tests,”this one is probably too short , but it serves to illustrate the sorts of problems you will want to ask, and to remind the students of what we’ve covered.