Review – Mathematical Induction

Mathematical induction is a method of proving certain formulas. It requires proving the formula for the values of n and n + 1. Here is an example:

Use mathematical induction to prove the formula for every positive integer n.

2 + 4 + 6 + 8 + . . . + 2n = n(n + 1)

First, we must prove this formula true for n = 1:

2(1) = (1)((1) + 1)
2 = 1(2)
2 = 2

Next, we must assume that the formula is true for n, and attempt to prove it for n + 1:

2 + 4 + 6 + 8 + . . . + 2(n + 1) = (n + 1)((n + 1) + 1)
2 + 4 + 6 + 8 + . . . + 2n + 2 = (n + 1)(n + 2)

We can substitute the 2 + 4 + 6 + 8 + . . . with n(n + 1), since we assume that the formula is true for n:

2n + 2n + 2 = (n + 1)(n + 2)
n(n + 1) + 2n + 2 = (n + 1)(n + 2)
n² + n + 2n + 2 = n² + n + 2n + 2
n² + 3n + 2 = n² + 3n + 2

Since the left-hand side now is equal to the right-hand side, we have proven this formula true for every positive integer n.

Mathematical induction can also be used in formulas using summation (sigma) notation.