Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » Advanced Algebra II: Conceptual Explanations » Proof by Induction

Navigation

Table of Contents

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.
  • Bookshare

    This collection is included inLens: Bookshare's Lens
    By: Bookshare - A Benetech Initiative

    Comments:

    "DAISY and BRF versions of this collection are available."

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

  • Featured Content display tagshide tags

    This collection is included inLens: Connexions Featured Content
    By: Connexions

    Comments:

    "This is the "concepts" 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 about […]"

    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 collection is included inLens: Busbee's Math Materials Lens
    By: Kenneth Leroy Busbee

    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.
 

Proof by Induction

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

Summary: An updated version of the Proof by Induction module.

“Induction” is a method of proving something. Once again, let’s start with an example.

Consider the sum i=1n1i(i+1)i=1n1i(i+1) size 12{ Sum cSub { size 8{i=1} } cSup { size 8{n} } { { {1} over {i \( i+1 \) } } } } {}. In other words, 11×2+12×3+13×4+...+1n(n+1)11×2 size 12{ { {1} over {1 times 2} } } {}+12×3 size 12{ { {1} over {2 times 3} } } {}+13×4 size 12{ { {1} over {3 times 4} } } {}+...+1n(n+1) size 12{ { {1} over {n \( n+1 \) } } } {}. This is neither arithmetic nor geometric, so none of our established tricks will work on it. How can we find the sum of such a series?

Students are often surprised to hear that mathematicians typically begin such problems by looking for a pattern. What does this series do for the first few terms?

  • 1 term: 11×2=1211×2 size 12{ { {1} over {1 times 2} } } {}=12 size 12{ { {1} over {2} } } {}
  • 2 terms: 11×2+12×3= 12+16=2311×2 size 12{ { {1} over {1 times 2} } } {}+12×3 size 12{ { {1} over {2 times 3} } } {}=12 size 12{ { {1} over {2} } } {}+16 size 12{ { {1} over {6} } } {}=23 size 12{ { {2} over {3} } } {}
  • 3 terms: 11×2+12×3+13×4=23+112= 3411×2 size 12{ { {1} over {1 times 2} } } {}+12×3 size 12{ { {1} over {2 times 3} } } {}+13×4 size 12{ { {1} over {3 times 4} } } {}=23 size 12{ { {2} over {3} } } {}+112 size 12{ { {1} over {"12"} } } {}=34 size 12{ { {3} over {4} } } {}

At this point, you might already suspect the pattern. ½, ⅔, ¾...could it be that the next term will be 4/5? Let’s find out.

  • 4 terms: 11×2+12×3+13×4+14×5=34+120=4511×2 size 12{ { {1} over {1 times 2} } } {}+12×3 size 12{ { {1} over {2 times 3} } } {}+13×4 size 12{ { {1} over {3 times 4} } } {}+14×5 size 12{ { {1} over {4 times 5} } } {}=34 size 12{ { {3} over {4} } } {}+120 size 12{ { {1} over {"20"} } } {}=45 size 12{ { {4} over {5} } } {}

It seems to work. The next term will probably be 56 5 6 , and then 67 6 7 , and so on. Stop for a moment and make sure you see the pattern. Then, see if you can express that pattern using mathematical notation instead of words. (Try this yourself before you keep reading!)

The pattern can be expressed like this:

11×2+12×3+13×4+...+1n(n+1)=nn+111×2 size 12{ { {1} over {1 times 2} } } {}+12×3 size 12{ { {1} over {2 times 3} } } {}+13×4 size 12{ { {1} over {3 times 4} } } {}+...+1n(n+1) size 12{ { {1} over {n \( n+1 \) } } } {}=nn+1 size 12{ { {n} over {n+1} } } {}

Stop for a moment and make sure you know where we are. What we have done is figured out a pattern to the answers, and shown that the pattern works for n = 1 n=1, n = 2 n=2, n = 3 n=3, and n = 4 n=4. Based on this pattern, we expect that if we added up 11×2+ 12×3+ 13×4+...+ 1100×10111×2 size 12{ { {1} over {1 times 2} } } {}+12×3 size 12{ { {1} over {2 times 3} } } {}+13×4 size 12{ { {1} over {3 times 4} } } {}+...+1100×101 size 12{ { {1} over {"100" times "101"} } } {}, we would get 100101100101 size 12{ { {"100"} over {"101"} } } {}.

But we have not yet proven anything. Maybe the pattern breaks down for n = 5 n=5. Or maybe it works for all the n-values from 1 to 1000, and then suddenly stops working. We cannot possibly test all the values in the world, one by one.

This is where the proof by induction comes in. It gives us a way to prove that such a pattern will continue to hold forever.

An inductive proof, in general, consists of two steps. The first step is to show that the pattern holds when n = 1 n=1. The second step is to show that, whenever this pattern holds for some particular n n, it will also hold for the next n n. If it holds for n = 5 n=5, then it must hold for n = 6 n=6. If it works for n = 99 n=99, then it must also work for n = 100 n=100. Once we have proven that, in general, then we will have shown that it works for all n n values.

Example 1: Proof by Induction

Inductive Proof of:

11×2+12×3+13×4+...+1n(n+1)=nn+111×2 size 12{ { {1} over {1 times 2} } } {}+12×3 size 12{ { {1} over {2 times 3} } } {}+13×4 size 12{ { {1} over {3 times 4} } } {}+...+1n(n+1) size 12{ { {1} over {n \( n+1 \) } } } {}=nn+1 size 12{ { {n} over {n+1} } } {}

First Step:

Show that it works for n = 1 n=1

1 term: 11×2=1211×2 size 12{ { {1} over {1 times 2} } } {}=12 size 12{ { {1} over {2} } } {}A checked box

Second Step:

Show that it works for n + 1 n+1, assuming it works for some n n

For n + 1 n+1, the left side of the equation looks like:

11×2+12×3+13×4+...+1n(n+1)+1(n+1)(n+1+1)11×2 size 12{ { {1} over {1 times 2} } } {}+12×3 size 12{ { {1} over {2 times 3} } } {}+13×4 size 12{ { {1} over {3 times 4} } } {}+...+1n(n+1) size 12{ { {1} over {n \( n+1 \) } } } {}+1(n+1)(n+1+1) size 12{ { {1} over { \( n+1 \) \( n+1+1 \) } } } {}

and the right side of the equation looks like:

n + 1 n + 1 + 1 n + 1 n + 1 + 1 size 12{ { {n+1} over {n+1+1} } } {}
(1)

So we want to see if:

11×2+12×3+13×4+...+1n(n+1)+1(n+1)(n+2)11×2 size 12{ { {1} over {1 times 2} } } {}+12×3 size 12{ { {1} over {2 times 3} } } {}+13×4 size 12{ { {1} over {3 times 4} } } {}+...+1n(n+1) size 12{ { {1} over {n \( n+1 \) } } } {}+1(n+1)(n+2) size 12{ { {1} over { \( n+1 \) \( n+2 \) } } } {}graphics2.pngn+1n+2n+1n+2 size 12{ { {n+1} over {n+2} } } {}

Now comes the key step.

If this pattern held for nn, then the first nn terms of the left side—that is, all but the last (new) term—must add up to nn+1nn+1 size 12{ { {n} over {n+1} } } {}. So we do that substitution:

nn+1+1(n+1)(n+2)nn+1 size 12{ { {n} over {n+1} } } {}+1(n+1)(n+2) size 12{ { {1} over { \( n+1 \) \( n+2 \) } } } {}graphics3.pngn+1n+2n+1n+2 size 12{ { {n+1} over {n+2} } } {}

All that remains, now, is the algebra to show that equation is true. Get a common denominator:

n(n+2)(n+1)(n+2)+1(n+1)(n+2)n(n+2)(n+1)(n+2) size 12{ { {n \( n+2 \) } over { \( n+1 \) \( n+2 \) } } } {}+1(n+1)(n+2) size 12{ { {1} over { \( n+1 \) \( n+2 \) } } } {}graphics4.png(n+1)2(n+1)(n+2)(n+1)2(n+1)(n+2) size 12{ { { \( n+1 \) rSup { size 8{2} } } over { \( n+1 \) \( n+2 \) } } } {}

n 2 + 2 n + 1 n 2 +2n+1 A checked box ( n + 1 ) 2 (n+1 ) 2 A checked box

The algebra here all comes from our unit on rational expressions: you may want to take a moment to make sure you can follow it. But don’t let the algebra distract you from the main point, which is what we proved in the second step. We proved that the formula works for n + 1 n+1. But in the middle of that proof, we assumed that it works for the previous term, n n. In doing so, we proved that if it works for 1, it must also work for 2; if it works for 2, it must also work for 3; and so on. This amounts, then, to a proof that the pattern holds forever.

Collection Navigation

Content actions

Download:

Collection 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 ...

Module as:

PDF | More downloads ...

Add:

Collection 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

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