More proof techniques: by induction

I posted below on a simple proof technique (proof by contradiction) which is useful in both math / science as well as everyday arguments. Mathematical induction is only useful in math / science but worth knowing if you don't, regardless of your field. For the mathematically inclined, I prove in the post just below why induction works. This post is just to show how it works.

The basic logic is that of dominoes: in a row of dominoes, any randomly chosen domino will knock down the one just after it, and the first domino is knocked down to get things going. What you're using induction for is to prove that some property P is true for all the natural numbers: i.e. 1, 2, 3, ... , n. Say, the property that the sum of the first n nat. numbers is given by a particular formula. There are two steps in an inductive proof: the Basis, and the Inductive step. The Basis is like the first domino -- it says that there's at least one number for which P is true. The Inductive step mimics the "domino effect" -- it says that, if you assume P is true for the number n, then it follows that P is also true for the next number n+1. This is crucial: the Inductive step is an If-Then statement: if you assume bla, then you can conclude bla bla. The conclusion statement is optional, but probably worth reiterating when you're first getting used to the technique. It just re-states your claim: because the domino effect is at work, and because the first domino is knocked down, all of them are -- i.e. the property P is true for all nat. numbers n.

Example: the handshake problem. We want to find out how many possible distinct handshakes there can be in room full of n people, and then prove this formula by induction. OK, imagine yourself as any randomly chosen person in that room -- how many people's hands can you shake? Well, you can shake everybody's but your own, which means there are n-1 handshakes a random person can make. Now, if there are n such people, then there should be n(n-1) handshakes, right? Almost -- but if A shakes B's hand, that's the same as B shaking A's hand, so we've accidentally counted each handshake twice. No problem, we'll just cut our number in half: (n(n-1))/2. This is usually the hardest part of an inductive proof -- just figuring out what the damn thing is you want to prove.

For the proof, we begin with a "let" statement. Let the property P(n) be defined (on the set of natural numbers) as the property that in a room of n people, there are (n(n-1))/2 distinct handshakes. We first establish the Basis. Here we'll pick n=2 since there need to be at least 2 people for a handshake to be defined. In a room full of 2 people, there is only 1 possible handshake. Substituting n=2 into our formula gives us (2(2-1))/2 = 1. The Basis checks out, so P(2) is true.

For the Inductive step, we assume that P(n) is true, and we want to show that this assumption implies that P(n+1) is true. So we assume that in a room of n people, the formula above gives the number of handshakes. Consider what would happen if another person entered the room. By our inductive hypothesis, there were already (n(n-1))/2 handshakes before he entered, and by the time he's shaken the hand of the n people who were already there, he'll have contributed an additional n handshakes to the total. By simple algebra, (n(n-1))/2 + n = ((n+1)n)/2. But we can re-write that as ((n+1)(n+1-1))/2 -- which means that P(n+1) is also true. That is, assuming P(n) is true, P(n+1) follows. This completes the Inductive step: it assures us that the domino effect happens. So in conclusion, P is true for all nat. numbers n -- the formula above gives the number of possible distinct handshakes in a room of n people.

Exercise 1: how many possible distinct diagonals can be drawn between the vertices of a polygon that has n sides? A polygon is just like the shapes you saw in high school geometry (triangle, rectangle, pentagon, etc.). Prove this formula is true by induction. Note: the Basis will be n=3 since you need at least 3 sides for a polygon. Hint for finding the formula: it's not a coincidence that this exercise follows the handshake example.

Exercise 2: prove by induction that the sum of the first n nat. numbers is given by the formula (n(n+1))/2.

Exercise 3: find a formula for the sum of the first n CUBES -- that is, 1^3 + 2^3 + ... + n^3. Prove this formula by induction.