Table of Contents   |   Proof Methods   |   Glossary

Formulating a Proof by Induction

The Basic Proof by Induction

A Proof by Induction has 5 basic parts.

     1. State The Proposition

State the proposition about n that you are trying to prove for all n.  This includes defining the range of integers that n covers.  Often this proposition will take the form f(n) = g(n).  
Show that the following statement P(n) is true for all n >= 1

     2. Verify the Base Case

Check the base case.  Usually this involves checking that a statement is true at n=0 and n=1.  What you are trying to do is prove that the smallest case is true.  If the smallest case is false, then the whole proposition will be false.
Evaluate P(n) at n=1 and verify that it is true.

      3. Formulate the Inductive Hypothesis

Formulate the Inductive Hypothesis and state that you are assuming the hypothesis to be true for some specific integer k.  It actually doesn't matter what letter you use but to avoid confusion, you should select a letter that isn't n.

Also, there are some variations on this.  Sometimes, it's easier to start with k in your hypothesis and go to k in your inductive step. Other times, you might prefer to start with k and prove k + 1.  We will generally start with k and prove k+1 in our examples unless otherwise stated.

Assume the following hypothesis is true for all  0 <= i <= k.

      4. Prove the Inductive Step

Prove your Inductive Step.  Here you will prove that the Inductive Hypothesis is true for the next case.  Step 4 really has 4 substeps.  
  1. State the proposition of the inductive step.
  2. Recheck the base case of the inductive step.
  3. Restate the proposition f(k+1) in terms of a function of f(k) and k+1.  (It's not always obvious how this is to be done.  Remember to use the inductive hypothesis when you restate the problem.)
  4. Substitute the inductive hypothesis and show that the proposition is still true at the k+1st step.

First, state the propostion P(k+1) which you are trying to derive.  This proposition may take the form f(k+1) = g(k+1).

Prove, given the above hypothesis, that:P(k + 1) is true.

Next, recheck the base case to make sure the proposition is true.

So the base case is true.

What you will then do is reduce f(k+1) to a function of f(k) and k+1.

We know that the left hand summation can be broken up .  (See Summation Identities)

Then, you'll substitute g(k) for f(k) (remember that the Inductive Hypothesis is assuming that f(k) = g(k) ),  

We can now use the Inductive Hypothesis

After substitution,

                 

Finally, derive g(k+1).

        

        

        

(Note: that the inductive step has to be valid for any pair of consecutive integers in the range that you've defined but usually it's enough just to prove it for k and k+1.  See the Henry Ford Theorem for an example of why.) 

     5. State the Conclusion of the Proof

Conclude that since the base case is true and the inductive step is true. P(n) is true for all n.  This is just to preserve the formal presentation of the proof.  

The proposition P(n) is true for all n

Another Example

Here's an example of induction involving a visual problem.  (Grossman, 1990, pg. 339)

(1)  We will prove the following proposition P(n) true for all n>=1:

Given a 2n by 2n checkerboard with any one square deleted, it is possible to cover this board with L-shaped pieces.

For example, a 4 x 4 checkerboard could be covered like this.

                   

(2)  Check the base case at n = 1.  At n = 1, you get a 2 x 2 checkerboard, with one square greyed out.

                    

(3) Assume the following hypothesis is true for some integer k.

It is possible to cover any 2i by 2i board, with any 1 square missing, with L-shaped pieces.

(4) Prove that it is possible to cover a 2k+1 by 2k+1 board.

A 2k+1 by 2k+1 checkerboard missing one square can be represented as the following,

                   

This part is tricky.  We can subdivide the problem by dividing the board into 4 quadrants and adding an L-shaped block to the middle.

                   

Each quadrant has 2k by 2k squares.  By adding the L-shaped piece, we've effectively reduced the problem now to 4 subproblems of size 2k x 2k.  If we can show that each 2k by 2k quadrant can be covered by L-shaped pieces, then we've shown that the whole 2k+1 by 2k+1 board can also be covered.

By the inductive hypothesis, we know that a 2i by 2i checkerboard that is missing one square is coverable by L-shaped pieces. 

(5) Therefore the whole 2k+1 by 2k+1 checkerboard can also be covered, ending the proof.  

Back to:

Top of Page