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:

Prove: Sn = 3 + 7 + 11 + … + (4n -1) = n(2n +1)

Show the statement works for
n = 1.

 S1 = 4(1) - 1 = 1(2(1) + 1)
3 = 3
So the statement is true 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 Sk + 1 by adding the next term to the left hand side (LHS) and substituting k + 1 for k in the RHS of the assumption. The LHS then becomes Sk + ak + 1.

Utilize the assumption: substitute the RHS of the assumption for Sk.

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

 

 

 

 Let Sk = 3 + 7 + 11 + … + (4k -1) = k(2k +1),

then Sk + 1 =
3 + 7 + 11 + … + (4k -1) + 4((k + 1) -1) = (k + 1)(2(k + 1) +1)

Sk + 4((k + 1) -1) = (k + 1)(2(k + 1) +1)

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

2k2 + k + 4k + 4 -1 = (k + 1)(2k + 3)

2k2 +5k + 3 = 2k2 + 3k + 2k + 3

2k2 +5k + 3 = 2k2 + 3k + 2k + 3.
So the statement is true for all k by the Principle of Mathematical Induction.

by Jack Tompkins