Mathematical Induction

Introduction

Mathematical and scientific discovery often arises from the recognition of a pattern.
There are two main aspects of inquiry in mathematics and science whereby new results can be discovered
1. deduction, and
2. induction.
Deduction
- accepting certain statements as premises and axioms, we can deduce other statements on the basis of valid inferences.
Induction
- the process of discovering general laws by observation and experimentation.
- arriving at a conjecture for a general rule by inductive reasoning.
- proof technique for verifying conjectures about positive integers.

The Principle of Mathematical Induction

Let P(n) be a statement which, for each integer n, may either be true or false.
To prove P(n) is true for all integers n >= 1, it suffices to prove
1. P(1) is true.
2. For all k >= 1, P(k) implies P(k+1).

General Case

For all n that belong to N, P(n) is true for all n >= n₀ if
1. P(n₀) is true.
2. For all k >= n₀, P(k) implies P(k+1).
n₀ is called the basis of induction and it may be any integer.

Three Steps to a Proof using Induction

Basis of Induction
- Show that P(n₀) is true.
Inductive Hypothesis
- Assume P(k) is true for k >= n₀.
Inductive Step
- Show that P(k+1) is true on the basis of the inductive hypothesis.

Example 1

Goal: To determine a formula for the sum of the first n positive integers.
Let S(n) = 1 + 2 + 3 + ... + n.

Examine a few values for S(n)

     n        1  2  3   4   5   6   7
     --------------------------------
     S(n)     1  3  6  10  15  21  28

Observe the following pattern

     2 S(1) =  2  =  1 X 2
     2 S(2) =  6  =  2 X 3 
     2 S(3) = 12  =  3 X 4
     2 S(4) = 20  =  4 X 5
     2 S(5) = 30  =  5 X 6
     2 S(6) = 42  =  6 X 7

Conjecture that 2S(n) = n(n+1) or S(n) = n(n+1)/2.
Prove by mathematical induction
- Statement: Let P(n) be the statement -- the sum S(n) of the first n positive integers is equal to n(n+1)/2.
1. Basis of Induction
  - Since S(1) = 1 = 1(1+1)/2, the formula is true for n = 1.
2. Inductive Hypothesis
  - Assume that P(n) is true for n = k, that is S(k) = 1 + 2 + ... + k = k(k+1)/2.
3. Inductive Step
  - Now show that the formula is true for n = k + 1.
  - Observe that S(k+1) = 1 + 2 + ... + k + (k+1) = S(k) + (k+1).
  - Since S(k) = k(k+1)/2 by the inductive hypothesis, then
```
     S(k+1) = S(k) + (k+1) 
            = (k/2)(k+1) + (k+1)
            = (k+1)(k/2 + 1)
            = ( (k+1)(k+2) ) / 2
```
    and the formula holds for k + 1. QED

Example 2

Goal: To determine a formula for the sum of the first n cubes.

            3    3    3          3
Let S(n) = 1  + 2  + 3  + ... + n .

Examine a few values for S(n)

     n        1  2   3    4
     -----------------------
     S(n)     1  9  36  100

Observe the following pattern

      3                              2
     1                   =   1  =   1

      3    3                         2
     1  + 2              =   9  =   3

      3    3    3                    2
     1  + 2  + 3         =  36  =   6

      3    3    3    3               2
     1  + 2  + 3  + 4    = 100  =  10
 
                                 2
Conjecture that S(n) = (n(n+1)/2)

Prove by mathematical induction

Statement:

Let P(n) be the statement -- the sum S(n) of the first n cubes
                      2
is equal to (n(n+1)/2) .

Basis of Induction

              3             2
Since S(1) = 1  = (1(1+1)/2) , the formula is true for n = 1.

Inductive Hypothesis

Assume that P(n) is true for n = k, that is 
        3    3          3             2
S(k) = 1  + 2  + ... + k  = (k(k+1)/2) .

Inductive Step

Now show that the formula is true for n = k + 1. 

Observe that 
          3    3          3        3               3
S(k+1) = 1  + 2  + ... + k  + (k+1)  = S(k) + (k+1) .
		
Using the inductive hypothesis, 
 3    3          3        3             2        3
1  + 2  + ... + k  + (k+1)  = (k(k+1)/2)  + (k+1)

                                   2        2
                            = (k+1)  ( (k/2) + k + 1 )

                                   2    2
                            = (k+1)  ( k / 4 + k + 1 )

                                   2     2
                            = (k+1)  ( (k  + 4k + 4) / 4 )

                                   2          2
                            = (k+1)  ((k+2)/2)

                                              2
                            = ((k+1)(k+2) / 2)
and the formula holds for k + 1.

QED

Example 3

Goal: To prove by mathematical induction that
```
 (n+2)    (2n+1)
6      + 7
```
is divisible by 43 for each positive integer n.

Prove by mathematical induction

Statement:

                             (n+2)    (2n+1)
Let P(n) be the statement ( 6      + 7       ) = 43x.

Basis of Induction

         (1+2)    (2+1)      3    3
Since ( 6      + 7      ) = 6  + 7  = 559 = 43 X 13, 
the formula is true for n = 1.

Inductive Hypothesis

                                             (k+2)    (2k+1)
Assume that P(n) is true for n = k, that is 6      + 7       = 43x 
for some integer x.

Inductive Step

Now show that the formula is true for n = k + 1. 

Observe that 
          (k+1+2)    (2(k+1)+1)
P(k+1) = 6        + 7

          (k+3)    (2k+3)
       = 6      + 7

              (k+2)    2    (2k+1)
       = 6 X 6      + 7  X 7

              (k+2)             (2k+1)
       = 6 X 6      + (6+43) X 7

              (k+2)        (2k+1)         (2k+1)
       = 6 X 6      + 6 X 7       + 43 X 7

                (k+2)    (2k+1)           (2k+1)
       = 6 X ( 6      + 7       ) + 43 X 7

                              (2k+1)
       = 6 X ( P(k) ) + 43 X 7

Since each component of this sum is divisible by 43 so is the entire sum and the formula holds for k + 1. QED

Example 4

Goal: Suppose that U.S. Postal Service prints only 5 and 9 cent stamps. Prove that it is possible to make up any postage of n cents using only 5 and 9 cent stamps for n >= 35.
Prove by mathematical induction
1. Basis of Induction
  - Since n₀ = 35 = 7 X 5 + 0 X 9 then it is true for n₀.
2. Inductive Hypothesis
  - Assume that n cent postage can be made up with only 5 and 9 cent stamps where n >= 35.
3. Inductive Step
  - Consider postage of n + 1 cents. There are two possibilities
    1. the n cent postage is made up of only 5 cent stamps, or
    2. there is at least one 9 cent stamp involved.
  - Case 1
    - The number of 5 cent stamps is at least seven (since n >= 35). Thus, we can replace the seven 5 cent stamps with four 9 cent stamps and make up n + 1 cent postage.
  - Case 2
    - Since there is at least one 9 cent stamp, we can replace it with two 5 cent stamps to achieve n + 1 cent postage.
  - Therefore, we can make up n + 1 cent postage in terms of only 5 and 9 cent stamps. QED

Summary

Mathematical induction involves a combination of the general problem solving methods of
1. the special case
  - proving the theorem true for n = 1 or n₀
2. the subgoal method -- dividing the goal into 2 parts
  1. proving it is true for n₀
  2. showing that if it is true for k, then it is true for k + 1