CPSC 170
Mathematical Induction

Mathematical induction can often be used to prove some property P of all integers greater than or equal to some base case b. The strategy in induction is to prove that P is true for the base case b, and then prove that if P is true for some arbitrary case k (k >= b), then P must also be true for k+1. This is sometimes described as climbing a ladder: proving the base case is like getting onto the ladder, and proving P(k+1) given P(k) is like going from one rung to the next. If you can do both of those things, you can climb the ladder as high as you want!

This kind of argument is supported by the First Principle of Mathematical Induction, which says the following: 

IF
  1. P(b) true (for some integer b)
  2. P(k) true -> P(k+1) true (k >= b)
THEN
  P(n) true for all n >= b

For example, the property P(n) might be that 1 + 2 + ... + n = n(n+1)/2, and we might want to show that it's true for all n >= 1. Proof by induction requires two steps:

  1. Base case

    Prove that the property is true for the base case b, that is, P(b). For this example the base case is 1, so we simply check P(1), 

      1 = 1*(1+1)/2
    which is true.

  2. Inductive step

    Show that IF the property is true for some arbitrary value k, then it must be true for k+1 as well. Note that what we are proving here is the implication P(k) -> P(k+1)(if P(k) then P(k+1)). We aren't concerned with whether or not P(k) is actually true; we just show that if it is true, then P(k+1) must be true as well. P(k) is called the inductive hypothesis. For this example: 

    P(k):   1+2+ ... + k       = k(k+1)/2      (inductive hypothesis -- assume true)
P(k+1): 1+2+ ... + k + k+1 = (k+1)(k+2)/2  (need to show this given P(k))
    How to prove P(k+1) given P(k)? Fortunately, the left side of P(k) is often very similar to the left side of P(k+1); in this case they differ only by k+1. Since we know that P(k) is true, we can add k+1 to both sides of that equation and still have a true statement: 
           1+2+ ... + k + k+1 = k(k+1)/2 + k+1
    The left side now looks like the left side of P(k+1). The right side looks different, but maybe they're just in different forms. We can transform the right side as follows: 
         k(k+1)/2 + k+1

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

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

=>   (k2 + k + 2k + 2)/2

=>   (k2 + 3k + 2)/2

=>   (k+1)(k+2)/2
    Thus we have shown P(k+1) given P(k), so the proof by induction is complete.

Another example

Prove that a fence of this type |--|--|--| with n posts, n>=1, has n-1 sections.

Base case (n=1): A fence with a single post (|) has 0 sections.

Inductive step: If a fence with k posts has k-1 sections, then a fence with k+1 posts has k sections.

Proof: A fence with k+1 posts has a fence with k posts embedded in it. 

   |-|-|-| ... |-|-|
  \______________/
       k posts
By the inductive hypothesis, a fence with k posts has k-1 sections. But a fence with k+1 posts has just one additional section (see diagram), so it has k-1+1 = k sections. This completes the proof by induction.

Yet another example

Use mathematical induction to show that 2n > n for all n>=1.
  1. Base case (n=1):

    21 > 1, so the base case holds.

  2. Inductive step: If 2k > k then 2k+1 > k+1.

    Starting with the inductive hypothesis (the k case), we notice that the left side looks like the left side of the k+1 case but is smaller by a factor of 2. So multiply both sides of the inductive hypothesis by 2, which maintains the inequality: 

          2k > k  

=>    2k * 2 > k * 2

=>    2k+1 > k * 2
    But we're trying to show that 2k+1 > k + 1, and we can't turn k*2 into k+1. However, note that for all k>1, k*2 is bigger than k+1, so anything that is bigger than k*2 must be bigger than k+1 as well. We have already shown that 2k+1 > k * 2, so we can conclude that 2k * 2 > k + 1.

The Second Principle of Mathematical Induction

There is another form of mathematical induction, called the Second Principle of Mathematical Induction, that is often useful. It says the following: 

IF
  1. P(b) true (for some integer b)
  2. P(r), b<=r<=k, true -> P(k+1) (k >= b)
THEN
  P(n) is true for all n >= b

The Second Principle is different in the second rule, which assumes not only that P is true for k, but that P is true for all values from b to k. This sounds like a stronger condition, but it turns out that the First and Second principles are actually equivalent. Depending on the problem, it just may be more convenient to use one form over another.

More Fences

Use the Second Principle of Mathematical Induction to prove that a fence with n posts has n-1 sections. (This is a problem that is easily proved using either the first or second principle.)

Base case: A fence with a single post (|) has 0 sections.

Inductive step: If a fence with r posts, 1<=r<=k, has r-1 sections, then a fence with k+1 posts has k sections.

Proof: A fence with k+1 posts can be divided into two parts, each of which has at least one post (since k>=1). If we say that the left part has x posts, then the right part must have the rest of the posts, that is, (k+1)-x posts. 

       |-|...|-|...|-|       (k+1) posts total
      \______/ \_____/
       x posts  (k+1)-x posts
Since each part has at least one and not more than k posts, the inductive hypothesis applies to each part. So by the inductive hypothesis, the left part has x-1 sections and the right part has k+1-x-1 sections. The whole fence, which has k+1 posts, has the sections in the left plus the sections in the right plus the section that joins them together: 
   x-1  +  k+1-x-1  +  1 = k sections.
    |         |        |      |
  left      right    join    total
This completes the proof.

Another example

Prove that any amount of postage greater than or equal to 8 cents can be built using only 3-cent and 5-cent stamps.

Base cases (n=8, n=9, n=10): 8=3+5; 9=3+3+3; 10=5+5.

Inductive step (second principle): If any amount of postage r, 8<=r<=k, can be built using only 3-cent and 5-cent stamps, then postage k+1 can be built using only 3-cent and 5-cent stamps.

Proof: Cases k=8, k=9, and k=10 were proved in the base case, so here we can assume that k+1 >= 11. By the inductive hypothesis, we know that the postage for k-2 can be formed using 3-cent and 5-cent stamps since (k+1)>=11 => (k-2)>=8. Now take the postage for k-2 and add a 3-cent stamp; this gives the postage for k+1, completing the proof.