Learning Resources

Proof by Induction

• Step 1: You must show that the statement you are trying to prove is indeed true for the first integer value of 1. Simply, substitute 1 in for n and show it yields a true statement.
• Step 2: Assume the statement is true for n = k. Substitute k into the statement  for the value of n. It may be beneficial here to rewrite the expression obtained so as to isolate the part that contains the variable k. For example, if after substituting k for n, you were left with 3^k - 1 = 2m, it might be a good idea to rewrite this as  3^k = 2m + 1. This will prove useful in step 3 of the process.
• Step 3: Prove the statement true for n = k + 1. This is the crux of the process, since you are trying to prove that the premise from step 2 implies the truth of the statement for the next integer value, n = k + 1. You are to substitute the value (k + 1) in for n. Since you will use the assumption made in step 2, you must try to rewrite the expression involving (k + 1) in terms of the one involving k. For example, if after substituting (k + 1) for n the result was 3^{k + 1} - 1, you would use exponent laws to rewrite this as 3^k x 3¹ - 1. Now you have an expression involving k for which you can substitute 2m + 1, based on the assumption you made in step 2.
• Step 4: You are to summarize what has happened in the first 3 steps of the process. It may be worded as follows, "Based on the principal of mathematical induction, it is true that .......(rewrite the statement to be proven) ..... for all natural numbers, n.