Mathematical Induction

A proof obviously needs to be finitely long, so that it can be written down and checked. But sometimes you can imagine that a proof is infinitely many steps long, with step 1, step 2, step 3, and so on, with a step for every positive integer. To do that, you show a general way to do an arbitrary step. Think of the proof as an algorithm. The input is the step number, n, and the output is the proof of step n.

An advantage of doing that is that you imagine the steps being done in order. When doing step 3, you have already done steps 1 and 2, and you are free to assume that they are in the fact bank. When you are doing step n, steps 1 through n−1 are all in the fact bank.

Example

Theorem. For every positive integer n, 1 + 2 + ... + n = n(n+1)/2.

Proof. The proof is by induction. Step 1 proves the equation for n = 1, step 2 proves it for n = 2, etc.

Step n = 1. Substituting n = 1 into the equation in the theorem shows that our goal is to show 1 = (1)(1+1)/2, which is clearly true.

Step n = k, where k > 1. Rather than explicitly doing steps 2, 3, etc., we show now how an arbitrary step k can be done. Since this works for any k > 1, it suffices to carry out all of the (infinitely many) remaining steps.

Our goal is the prove the theorem for the special case of n = k. That is we need to prove

Goal of this step. 1 + 2 + ... + k = k(k+1)/2.

Remember that we are doing the steps in order, starting with step 1, then step 2, etc. At step 100, we have already done step 99 and, in general, when we reach step k, we have already done step k−1. That means our equation with n replace by k−1 is already in the fact bank.

(1) 1 + 2 + ... + (k−1) = (k−1)((k−1)+1)/2.

(2) 1 + 2 + ... + (k−1) = (k−1)(k)/2.

1 + 2 + ... + (k−1) + k	=	(k−1)(k)/2 + k	(by fact (2))
	=	(k2 − k)/2 + k	(by algebra)
	=	(k2 − k + 2k)/2	(by algebra)
	=	(k2 + k)/2	(by algebra)
	=	k(k+1)/2	(by algebra)

(3) 1 + 2 + ... + k = k(k+1)/2.

♦