<< Chapter < Page Chapter >> Page >
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 = 1 n 1 i ( i + 1 ) size 12{ Sum cSub { size 8{i=1} } cSup { size 8{n} } { { {1} over {i \( i+1 \) } } } } {} . In other words, 1 1 × 2 size 12{ { {1} over {1 times 2} } } {} + 1 2 × 3 size 12{ { {1} over {2 times 3} } } {} + 1 3 × 4 size 12{ { {1} over {3 times 4} } } {} +...+ 1 n ( 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: 1 1 × 2 size 12{ { {1} over {1 times 2} } } {} = 1 2 size 12{ { {1} over {2} } } {}
  • 2 terms: 1 1 × 2 size 12{ { {1} over {1 times 2} } } {} + 1 2 × 3 size 12{ { {1} over {2 times 3} } } {} = 1 2 size 12{ { {1} over {2} } } {} + 1 6 size 12{ { {1} over {6} } } {} = 2 3 size 12{ { {2} over {3} } } {}
  • 3 terms: 1 1 × 2 size 12{ { {1} over {1 times 2} } } {} + 1 2 × 3 size 12{ { {1} over {2 times 3} } } {} + 1 3 × 4 size 12{ { {1} over {3 times 4} } } {} = 2 3 size 12{ { {2} over {3} } } {} + 1 12 size 12{ { {1} over {"12"} } } {} = 3 4 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: 1 1 × 2 size 12{ { {1} over {1 times 2} } } {} + 1 2 × 3 size 12{ { {1} over {2 times 3} } } {} + 1 3 × 4 size 12{ { {1} over {3 times 4} } } {} + 1 4 × 5 size 12{ { {1} over {4 times 5} } } {} = 3 4 size 12{ { {3} over {4} } } {} + 1 20 size 12{ { {1} over {"20"} } } {} = 4 5 size 12{ { {4} over {5} } } {}

It seems to work. The next term will probably be 5 6 , and then 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:

1 1 × 2 size 12{ { {1} over {1 times 2} } } {} + 1 2 × 3 size 12{ { {1} over {2 times 3} } } {} + 1 3 × 4 size 12{ { {1} over {3 times 4} } } {} +...+ 1 n ( n + 1 ) size 12{ { {1} over {n \( n+1 \) } } } {} = n n + 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 = 2 , n = 3 , and n = 4 . Based on this pattern, we expect that if we added up 1 1 × 2 size 12{ { {1} over {1 times 2} } } {} + 1 2 × 3 size 12{ { {1} over {2 times 3} } } {} + 1 3 × 4 size 12{ { {1} over {3 times 4} } } {} +...+ 1 100 × 101 size 12{ { {1} over {"100" times "101"} } } {} , we would get 100 101 size 12{ { {"100"} over {"101"} } } {} .

But we have not yet proven anything . Maybe the pattern breaks down for 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 . The second step is to show that, whenever this pattern holds for some particular n , it will also hold for the next n . If it holds for n = 5 , then it must hold for n = 6 . If it works for n = 99 , then it must also work for n = 100 . Once we have proven that, in general, then we will have shown that it works for all n values.

Proof by induction

Inductive proof of:

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

First step:

Show that it works for n = 1

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

Second step:

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

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

1 1 × 2 size 12{ { {1} over {1 times 2} } } {} + 1 2 × 3 size 12{ { {1} over {2 times 3} } } {} + 1 3 × 4 size 12{ { {1} over {3 times 4} } } {} +...+ 1 n ( 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 size 12{ { {n+1} over {n+1+1} } } {}

So we want to see if:

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

Now comes the key step.

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

n n + 1 size 12{ { {n} over {n+1} } } {} + 1 ( n + 1 ) ( n + 2 ) size 12{ { {1} over { \( n+1 \) \( n+2 \) } } } {} n + 1 n + 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 ) size 12{ { {n \( n+2 \) } over { \( n+1 \) \( n+2 \) } } } {} + 1 ( n + 1 ) ( n + 2 ) size 12{ { {1} over { \( 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 A checked box ( n + 1 ) 2 A checked box

Got questions? Get instant answers now!

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 . But in the middle of that proof, we assumed that it works for the previous term, 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.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Advanced algebra ii: conceptual explanations. OpenStax CNX. May 04, 2010 Download for free at http://cnx.org/content/col10624/1.15
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Advanced algebra ii: conceptual explanations' conversation and receive update notifications?

Ask