*13 -
7 Mathematical
Induction*
**The idea of
math induction,
is a concept that can be used to prove statements true for all positive
integers ***n. *This can not be done directly because we are
dealing
with an infinite set of numbers. Because statements about
sequences
and sums are related to the set of positive integers, this type of
proof
is used most often when dealing with them. The process takes three
steps
as outlined below:
**1)
Prove that it works
for the first element in the sequence or series.**
**That is:
prove it works
for n = 1**
**2) Assume that the
sequence or series is true for some finite
number of terms. That is,
assume it works for n = k**
**3)
Prove that it works
for the next element in the sequence/series.**
**That is,
prove it works
for n = k + 1**
**Sounds complicated, and
it can be. Here's an analogy you might consider to why this proof
works. You are babysitting your little baby brother. He is
over by the steps and he has never berfore climbed the steps. You
watch him crawl up the first step! (That's
the first step of the proof. Prove for n = 1.)
He now has the ability to move from
one step to the next. The phone
rings and you go to the kitchen to answer it. When you come back,
your little brother is now on the 6th step! (Way
to babysit!)(This of course is step two, assuming
it works for some finite number of elements) Now
you didn't see him actually climb the stairs, but the only assumption
you
can realistically make is he climbed the stairs one at a time!
Now
you see him climb one more stair. (Voila!)
(This is of course step three,
proving it works for n = k + 1)**
**The analogy is
of course
a stretch, but as good as we are going to get. We don't have an
infinite
staircase, but the beauty here is, it doesn't matter how many steps you
missed seeing him crawl. It could have just as easily been 2, 9,
23, etc. It doesn't matter. That's where the infinite part
comes in. No matter how many you assume to be true, you can
always
prove one more!**

__Sample
Proof:__
*Prove
that:
1 + 2 + 3 + 4 + . . . + n = n(n + 1)/2*
*Step 1)
Prove it works
for n = 1*
*Use the
first element
in the series and replace n = 1 on the right side!*
*1 = 1(1
+ 1)/2*
*1 = 1 *
*Step
2) Assume
it works for n = k (some finite #)*
*1 + 2 + 3 + . . . + k
= k(k + 1)/2
is
true. That's it for step 2.*
*Step
3) Prove it
works for n = k + 1*
*1 + 2 + 3 + . . . + k
+ (k + 1)
= (k + 1)(k + 2)/2*
*Notice
everything in
white is what you assumed to be true in step 2. Make a
substitution
from step 2.*
*k(k +
1)/2 + (k + 1)
= (k + 1)(k + 2)/2*
*Now show
the left hand
side = right side by using basic algebra!*
*k(k + 1)/2 +2(k + 1)/2
(Common
denominator)*
*(k*^{2} + k +
2k + 2)/2 (adding numerators)
*(k*^{2} + 3k +
2)/2 (combining like terms)
*(k + 1)(k + 2)/2 (factoring)*
*It equals the right side! *

*Congratulations!
You have made it to the end of the chapter. All that remains is a
sample test on the next page and the answers on the page after
that! *