Refresher - Proof

A proof is a clear explanation, accepted by the mathematical community, of why something is true. Ancient Babylonian and Egyptian mathematics had no proofs, just examples and methods. The way we use proofs today began with the Greeks and Euclid.

Mathematical Induction is a technique for proving assertions for every natural number, once a pattern is identified. By proving statements of a small sample, we can generalize for a whole set. Think of Mathematical Induction as a proof method that utilizes a process that is like walking up a staircase. You must first get on the first step. Then you must show that you can always proceed from one step to the next. So, if you can get on the first step, you can proceed to the second. If you are on the second step, you can proceed to the third. If you are on the third step, you can proceed to the fourth, and so on, indefinitely, for all the steps. In other words, for all n, if we can get to the first, the nth step, we can get to the second (n+1) step. This tells us that we can climb all the steps.

Basic Steps in a proof by Mathematical Induction

Prove that your statement is true for the first case, usually n = 1
Assume the statement works for n = k, (the statement is true for some finite number of terms)
Prove the statement works for n = k + 1 (the statement works for the next element in the sequence/series)

EXAMPLE
Use the principle of mathematical induction to prove the following statement:

$1 + 4 + 7 + ... (3 n - 2) = \frac{n (3 n - 1)}{2}$

1. Initial step: show the statement is true for n = 1
$\begin{array}{l} (3 n - 2) = \frac{n (3 n - 1)}{2} \\ 3 (1) - 2 = 1 \\ \frac{1 [3 (1) - 1]}{2} = \frac{1 (2)}{2} = 1 \end{array}$
$\begin{array}{l} \end{array}$ $\begin{array}{l} \end{array}$

Since both sides equal 1, the statement is true for n = 1.

2. Induction step: Assume the statement is true for n = k and prove it is also true for n = k + 1

$1 + 4 + 7 + ... (3 k - 2) = \frac{k (3 k - 1)}{2}$

(Substitute k for n)

We want to show that

$1 + 4 + 7 + ... (3 k - 2) + [3 (k + 1) - 2] = \frac{(k + 1) [3 (k + 1) - 1]}{2}$

$1 + 4 + 7 + ... (3 k - 2) + [3 (k + 1) - 2] = \frac{k (3 k - 1)}{2} + [3 (k + 1) - 2]$

(Add [3(k+1) -2] to both sides)

$= \frac{k (3 k - 1)}{2} + 3 k + 1$

Simplify

$= \frac{k (3 k - 1)}{2} + \frac{2 (3 k + 1)}{2}$ Multiply the second term by $\frac{2}{2}$

$= \frac{3 k^{2} - k + 6 k + 2}{2}$ Distribute property

$= \frac{3 k^{2} + 5 k + 2}{2}$ Simplfy

$= \frac{(k + 1) (3 k + 2)}{2}$ Factor

$= \frac{(k + 1) [3 (k + 1) - 1]}{2}$ Distribute property

The statement is true for n = k+1. Since both the initial step and the inductive steps have been completed by induction, the statement is true for all natural numbers, n.

Click here Links to an external site. for more practice problems with variations on the standard method of proof by induction.