Principle of Mathematical Induction

 
    Let Pn be a statement involving the positive integer n. If

      

    1. P1 is true, and 
      2. 

    2. the truth of Pk implies the truth of Pk + 1, for every positive k,
    
then Pn must be true for all positive integers n.

Mathematical induction consists of two distinct parts. First, you must show that the formula is true for n = 1. The second part has two steps. The first step is to assume that the formula is valid for some integer k. The second step is to use this assumption to prove that the formula is valid for the next integer, k + 1. Combining the results of parts (1) and (2), you can conclude by mathematical induction that the formula is valid for all positive integer values of n.

Remarks:

Proof:

Show the statement works for
n = 1.

 

 

Assume it works for some arbitrary integer k, and show that it works for k + 1.

Write out the initial statement as an assumption.

Write out the statement adding the next term to the left hand side and substituting k + 1 for k in the right hand side. The left hand side then becomes Sk + ak + 1.

Utilize the assumption: substitute the right hand side of the assumption for Sk.

Now simplify both sides to see if the statement is true for k + 1.

 

 

by Jack Tompkins