I proved each of the following via mathematical induction.
+ 1
+ + 1
n· (n+1)
= 1 - 1
  for n 1 .

3n < n! for n > 6  .

| n3 -n for n 0  .
The format for these proofs is standard. Here is a proof of the third:
The base case is n = 0.
We check whether 6 | 03 -0, i.e., whether 6 | 0 and see that the answer is yes.
Now assume that for some k, 6 | k3 -k.
We need to prove that 6 | (k+1)3 -(k+1).
But (k+1)3 -(k+1) = (k3 - k)+3(k2+k). Since 6 | k3 -k, we need only show that 6 | 3(k2+k). This follows provided 2 | k2+k. But k2+k = k(k+1) and either k of k+1 must be even so we are done.

As an illustration of what can happen if one is careless in applying the assumption, consider the following ``proof'' that all positive numbers are equal.

We will prove that if max(a,b) = n then a = b. If n = 1 both a and b must be 1, hence a = b. Assume that for some k, we have max(a,b) = k     a = b. If max(a,b) = k+1 then max(a-1,b-1) = k from which it follows that a-1 = b-1 so that a = b.

The problem is (as it turns out) that there is no guarantee that a-1 and b-1 are positive integers.

Next time I will consider induction where rather than assuming that the property holds for k (and trying to prove it holds for k+1) we will assume that the property holds for all numbers less than or equal to k but otherwise proceed as above.

File translated from TEX by TTH, version 2.60.
On 30 Oct 2000, 19:43.