Skip to content Skip to navigation

OpenStax_CNX

You are here: Home » Content » Sequences and Series Guide -- Proof by Induction

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • Featured Content display tagshide tags

    This module is included inLens: Connexions Featured Content
    By: ConnexionsAs a part of collection: "Advanced Algebra II: Teacher's Guide"

    Comments:

    "This is the "teacher's guide" book in Kenny Felder's "Advanced Algebra II" series. This text was created with a focus on 'doing' and 'understanding' algebra concepts rather than simply hearing […]"

    Click the "Featured Content" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

Also in these lenses

  • Busbee's Math Materials display tagshide tags

    This module is included inLens: Busbee's Math Materials Lens
    By: Kenneth Leroy BusbeeAs a part of collection: "Advanced Algebra II: Teacher's Guide"

    Click the "Busbee's Math Materials" link to see all content selected in this lens.

    Click the tag icon tag icon to display tags associated with this content.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Sequences and Series Guide -- Proof by Induction

Module by: Kenny M. Felder. E-mail the author

Summary: A teacher's guide to lecturing on proofs by induction.

Proof by Induction

Going over last night’s homework, make sure they got the right formulas. For an arithmetic series, S n = n2( t 1 + t n ) S n =n2 size 12{ { {n} over {2} } } {}( t 1 + t n ). For a geometric, S n = t1rnt1r1 S n =t1rnt1r1 size 12{ { {t rSub { size 8{1} } r rSup { size 8{n} } - t rSub { size 8{1} } } over {r - 1} } } {}, in some form or another.

Example 1

Students sometimes ask if that formula will still work for an arithmetic series with an odd number of terms. Obviously, you can’t still pair them up in the way we have been doing. The answer is, it does still work. One proof—which I usually don’t mention unless the right questions are asked—is that, for an arithmetic series, the average of all the terms is right in the middle of the first and last terms. (It can take a minute to convince yourself that this is not always true for any series, but it is for any arithmetic series.) So the average is t1+tn2t1+tn2 size 12{ left ( { {t rSub { size 8{1} } +t rSub { size 8{n} } } over {2} } right )} {}, and there are n n terms. This leads us to the total sum being n t1+tn2nt1+tn2 size 12{ left ( { {t rSub { size 8{1} } +t rSub { size 8{n} } } over {2} } right )} {}, which is the old formula written in a new way. This lacks some of the elegance of the original proof, but it has the advantage that it doesn’t matter if n n is even or odd.

Anyway, on to today’s topic.

Note:

Important note. The following lecture can be done in 5-10 minutes—I’ve done it many times—and if you do it that way, it doesn’t work. This can be one of the most confusing topics in the whole unit. It must be taken very slowly and carefully!

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 = n2( n + 1 ) 1+2+3+4...n=n2 size 12{ { {n} over {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 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... 1 2 ( 1 + 1 ) = 1 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 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 × 201 = 20 , 100 ) 100×201=20,100). And now I ask you to confirm that the formula works when n = 201 n=201.

Well, you can do the right side easily enough: 2012( 202 ) = 20 , 301 2012 size 12{ { {"201"} over {2} } } {}(202)=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 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 n=325. How would we show that it works for n = 326 n=326? Good—we would add 326 to the old answer (for n = 325 n=325), and see if we got what the formula predicted we should get for n = 326 n=326. Let’s try it...

Now...suppose I had already proven that it works for n = 1000 n=1000. How would we show that it works for n = 1001 n=1001? Good—we would add 1001 to the old answer (for n = 1000 n=1000), and see if we got what the formula predicted we should get for n = 1001 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 n. How would we show that it works for n + 1 n+1?

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

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

What does that look like? Well, for the old n n, the formula predicted we would get n2( n + 1 ) n2 size 12{ { {n} over {2} } } {}(n+1). So if we add ( n + 1 ) (n+1) to that, we get n2( n + 1 ) + ( n + 1 ) n2 size 12{ { {n} over {2} } } {}(n+1)+(n+1). And what should we get? Well, for ( n + 1 ) (n+1), the formula predicts we should get n+12( n + 1 + 1 ) n+12 size 12{ { {n+1} over {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 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 n=1, then it must work for n = 2 n=2. If it works for n = 2 n=2, then it must work for n = 3 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 Σ 1n(n+1)Σ1n(n+1) size 12{ { {1} over {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:

“Homework—Proof by Induction”

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.

Content actions

Download module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks