Discrete Mathematics for Computer Science

Mathematical Induction 47

It is not obvious that this formula is true for all n. It is true for n = 0, 1, 2, 3, and 4, but as

yet, we have no reason to believe it is true for, say, n = 12, or 347, or any of the integers

for which we have not shown it to be true.

What is needed is a method to prove that the conjectured formula is correct for all

n e N. The standard method of proof for a result claimed to hold for every natural num-

ber is called mathematical induction. Such proofs use an axiom of arithmetic called the

Principle of Mathematical Induction. This is not like Template 1.2 (Set Inclusion), since

we are not proving the same thing for every element of N. For example, for the sum of the

first n integers, suppose we want to prove the sum is 6 for n = 3 but 15 for n = 5. Before

stating the general principle, we present an example showing how the principle is used to

prove that our conjectured formula for adding the natural numbers from 0 to n is true for

all natural numbers n.

Theorem 1. For any natural number n,

n .(n + 1)

2

Proof. Step 1: (Base step) Prove the result for n = 0, the smallest natural number.

The sum on the left-hand side of the equals sign is just the sum of all the natural numbers

starting at 0 and going up to 0-that is, it is just 0. The number on the right-hand side is

0. (0 + 1)/2, which is also 0. Therefore, the two sides are equal, and the result is true for
   n =0.
   Step 1: (Inductive step) Let n be any natural number for which the result is true. Prove
   the result is also true for n + 1. The assumption that the result is true for n is called the
   inductive hypothesis or inductive assumption. Assuming the result is true for n means
   that

n.(n + 1)

2

Use this assumed-correct result to prove the required result for n + 1-that is, to prove that

(n + 1). (n + 2)

2

To prove this, we start by regrouping the terms on the left-hand side:

0+ l + 2+...+n+(n+ l)=(O+ I + 2 +...+n)+(n+ 1)

By the inductive hypothesis, the result is true for n, so we can substitute n(n + 1)/2 for the

terms in the first pair of parentheses on the right-hand side. We get

(0 + I+ 2-. -n) -- (n + 1) (n + 1) + (n + 1) (using the inductive hypothesis)
2

(n ± 1) ±2 (n + 1) (simplifying the algebra)

2

(n + 1). (n + 2)

2

This means the formula is true for n + 1.