Mathematical Induction

  
       If you can prove that something is true for a particular value,
       say 1, and if you can also show that if this same thing is true for
       an arbitrary value, say k, then it is also true for the next value, k+1,
       then you have proven that is is true for all values beginning with 1.

       1)  The base case:  You must prove, usually via a demonstration, that
           what you are trying to prove is true for one specific value. Usually
           the value you choose will be determined by what you are proving
           and will be the smallest value.  For instance, if you are proving
           some property of the positive integers then you would choose 1 for
           the base case as it is the smallest positive integer.  

       2)  The Inductive Hypothesis:  Assume that what you are proving is,
           in fact, true for some arbitrary value, say n.  It is perfectly
           valid to make such an assumption as you have already demonstrated
           the the claim is true for some value in the base case.  

       3)  Now, having established the base case and made our inductive
           hypothesis we need to show that if the claim is true for some
           value, say n, then it is also true for the next case, n + 1.
           This is usually done by considering the n + 1 case and  showing
	   that it can be established from the hypothesis made in step 2
           above.


       Example:

       Claim:  For all values of n > 3, n! > 2^n. 

       Proof: By induction on n

       1) Base case: The statement is claiming a certain relationship
                     between the factorial funcion and the power function
                     for all values greater than three.  Since four is the 
                     next integer it will be the smallest instance of this
                     claim and hence the base case for the proof.

                     Since the statement is claiming a relationship between
                     the factorial and power functions, we must consider
                     both functions when n = 4.

                     Factorial: 4! = 24 
                     Power:    2^4 = 16. 

		     Clearly 24 > 16, so the claim is true for the base
                     case.

       2) Inductive step: Assume that k! > 2^k is true for some arbitrary
                     value of k > 3. 

       3) Consider the next problem instance, k + 1.

          From the definition of the factorial function we know that

          a)      (k + 1)! = (k + 1) * k!

          From the inductive hypothesis we know that

          b)            k! > 2^k

          And if k! is larger than 2^k then clearly (k + 1) * k! is
          larger than (k + 1) * 2^k. So:

          c)  (k + 1) * k! > (k + 1) * 2^k

          And from a) we know that

          d)      (k + 1)! > (k + 1) * 2^k

          Since k is greater than 3 from the inductive step we know that

          e) (k + 1) * 2^k > 2 * 2^k

          Combining d) and e) we finally have:

          f) (k + 1) * k! > (k + 1) * 2^k > 2 * 2^k

          and

          g) (k + 1) * k! > 2 * 2^k

          and since 2 * 2^k = 2^(k + 1) then

          h) (k + 1) * k! > 2^(k + 1)

          and finally

          i)     (k + 1)! > 2^(k + 1)

          So, we have proven that the above claim is true for the base 
          case when n = 4.  And we have proven that if the claim is true
          for some arbitrary value, say k, then it is also true for k + 1.
          Well, since we know it's true for 4, then it is also true for 5.
          And, if it is true for 5, then it is also true for 6. And so on,
          and so on.

Links to other pages on proof by induction:

• Dr. David Sumner's induction tutorial.

• Idris H. Hsi's tutorial.

• Elizabeth Stapel's Purplemath module on induction.