Induction

Finally, we are introduced to Induction in this class. I don't really understand why we were not introduced to introduction when we were first doing proofs, given that it is so useful. Actually, induction seems so simple and straightforward that its power is sometimes underestimated at first. At least I was one of them. However, upon closer examination, I realized that induction actually proves some of our assumptions in our previous proofs. For example, one of our first proofs was "for all natural numbers n, if n is odd, then n^2 is odd." We proved that by first assuming that n is a natural number and n is odd. How do we know that if n is odd then n^2 is odd is true for all natural numbers? Do we plug every natural number in and check the result? We could do that until the end of time, and still be unable to get a conclusion. Therefore, we need a more powerful tool of logic to help us out.

Induction is really an axiom, and like all axioms, it is self evident. Lets break it down.

• let P(n) be a predicate
• if P(0) is true and for all natural numbers n, (P(n)=>P(n+1)) is true
• then for all natural numbers n, P(n) is true!

So if P(0) is true, and P(0) => P(1) is true, then P(1)=> P(2) is true, and P(2) => P(3) is true... and so on...

Now lets prove the following proposition:

It's interesting to note, that I didn't really introduce anything new here... We were already given the equation sum of i = n(n+1)/2, and we simply proved that it's true. However, induction did not give us that equation nor did it give us the reasoning behind it. Is that satisfying?