## Mathematical Induction

Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. It is done by

- proving the first statement in the infinite sequence of statements is true, and then
- proving that if any one statement in the infinite sequence of statements is true, then so is the following one

Example:

Suppose we wish to prove the statement that

"The sum of the
first n
odd positive integers equals n^{2}."

First few cases
of this statement may be shown to be true:

1 = 1

1 + 3 = 4 = 2

1 + 3 + 5 = 9 = 3

.

.

.

Because the n

1 + 3 + 5 + (2n - 1) = n

1 = 1

^{2 }(n = 1, trivial case with only a single term)1 + 3 = 4 = 2

^{2 }(n = 2)1 + 3 + 5 = 9 = 3

^{2}(n = 3).

.

.

Because the n

^{th}odd positive integer is 2n - 1, the n^{th}case may be written as:1 + 3 + 5 + (2n - 1) = n

^{2}The next odd
positive integer following (2n
-1) would be (2n
- 1) +2)) or (2n
+ 1)

Thus, adding 2n + 1 to each side of the above statement for the n

1 + 3 + 5 + (2n - 1) + (2n + 1) = n

As right hand side equals (n + 1)

Thus, adding 2n + 1 to each side of the above statement for the n

^{th}case, it follows:1 + 3 + 5 + (2n - 1) + (2n + 1) = n

^{2}+ (2n + 1)As right hand side equals (n + 1)

^{2,}it follow that:1 + 3 + 5 + (2n - 1) + (2n + 1) = (n + 1)

^{2 }Which represents the (n + 1)

^{st}case

∴

Every case of the statement "the sum of the first n odd positive integers equals n

^{2}" is true if the first case (i.e., n =1) is true.