Multiple Proofs 11

And now a proof by induction. Mathematical induction is a method of proving that

something is true for all natural numbers by showing that it starts out true at n = 0 and that,

furthermore, truth is preserved from each number to the next. We shall cover this method

in detail in chapter 4, but for now let us simply use the method.

Proof #3 (by induction). The claim that n

2

− n is even is true when n = 0, since 0 is even.

So it starts out true. To see that the fact is propagated from each number to the next,

suppose that n

2

− n is even and consider the next instance, (n + 1)

2

− (n + 1). By using

some elementary algebra, this is equal to n

2

+ 2n + 1 −n −1 = n

2

+ n, which can be written

as (n

2

− n) + 2n. Thus, in moving from n

2

− n to (n + 1)

2

− n

2

we have added 2n,aneven

number. And so if the statement is true at a number n, then it remains true at n + 1, and so

the truth of the statement is propagated from each number to the next. So by mathematical

induction, it is true for all numbers.

Next, we prove the theorem using geometry.

Proof #4 (by geometrical figure). Consider an n×n square, consisting of n

2

small squares.

If we remove the diagonal, which has n squares on it, there are exactly n

2

− n squares

remaining.

Notice that the figure is completely symmetric, and every small square on one side of the

diagonal can be paired with a corresponding square on the other side of the diagonal. So

n

2

− n is even.

We now prove the theorem using ideas from combinatorics.

Proof #5 (by combinatorics). The reader may happen to know that the number of ways to

choose 2 things from a set of n − 1 things is n(n − 1)/2, and we shall prove such facts in

chapter 5. Since this number is an integer, it follows that the numerator n(n − 1) must be a

multiple of 2, and so we conclude that n

2

− n is even.

And next we prove the theorem using modular arithmetic.