“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.
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} } } {}
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} } } {}
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 \) } } } {}
n+1n+2n+1n+2 size 12{ { {n+1} over {n+2} } } {}
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 \) } } } {}
n+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 \) } } } {}
(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
(
n
+
1
)
2
(n+1
)
2
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.
Mathematical Induction Video
"DAISY and BRF versions of this collection are available."