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 n2."
First few cases
of this statement may be shown to be true:
1 = 12 (n = 1, trivial case with only a single term)
1 + 3 = 4 = 22 (n = 2)
1 + 3 + 5 = 9 = 32 (n = 3)
.
.
.
Because the nth odd positive integer is 2n - 1, the nth case may be written as:
1 + 3 + 5 + (2n - 1) = n2
1 = 12 (n = 1, trivial case with only a single term)
1 + 3 = 4 = 22 (n = 2)
1 + 3 + 5 = 9 = 32 (n = 3)
.
.
.
Because the nth odd positive integer is 2n - 1, the nth case may be written as:
1 + 3 + 5 + (2n - 1) = n2
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 nth case, it follows:
1 + 3 + 5 + (2n - 1) + (2n + 1) = n2 + (2n + 1)
As right hand side equals (n + 1)2, it follow that:
Thus, adding 2n + 1 to each side of the above statement for the nth case, it follows:
1 + 3 + 5 + (2n - 1) + (2n + 1) = n2 + (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 n2" is true if the first case (i.e., n =1) is true.