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)
(k2 + k + 2k + 2)/2  (adding numerators)
(k2 + 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!