Mathematical Induction

Proof by Induction

Mathematical induction is an alternative way of proving mathematical theorems. Instead of using analysis and tractability, mathematical induction relies on verifying base truths and showing that the theorem holds for other parameters based on these base truths. Mathematical Induction usually starts by showing that the theorem is valid for a low number such as 1. After showing that, it is assumed that the theorem holds for any number x and it is up to the student to show that if it holds for x, it will hold for x+1. Since the theorem was already shown to work on x=1 and that it will hold for x+1, it will essentially work on all other numbers.

In our example, we must first show that the sum of the first n even numbers is equal to (n)(n+1) when n = 1. This is a trivial matter as we can show that for n = 1, the sum of the first 1 even numbers is 2. Looking at the formula, (1)(1+2) = 2, the theorem holds for the base truth. We can even verify this for the first seven even integers.

We now assume that the theorem is valid for any n. We can express this mathematically as:

.  (Equation 1)

We must now show that the case for n = n+1 holds true if Equation 1 is true.

We bring out the final term in the summation.
We subtract (2n+2) from each side

Q.E.D.
We see that the case for n+1 does hold true if we assume that our theorem is true.