12.9. Induction Proofs http://www.ck12.org
Inductive Hypothesis (starting equation): 2 + 22 +··· 2 k= 2 k+^1 − 2
Multiply by 2: 2 ( 2 + 22 +···+ 2 k) = 2 ( 2 k+^1 − 2 )
Rewrite: 22 + 23 +···+ 2 k+^1 = 2 k+^1 +^1 − 4
Add 2 to both sides: 2 + 22 + 23 +···+ 2 k+^1 = 2 k+^1 +^1 − 4 + 2
Simplify: 2 + 22 +···+ 2 k+^1 = 2 k+^1 +^1 − 2
This is exactly what you were trying to prove! So, first you showed that the statement worked forn=1. Then,
you showed that the if the statement works for one number than it must work for the next number. This means, the
statement must be true for all numbers greater than or equal to 1.
The idea of induction can be hard to understand at first and it definitely takes practice. One thing that makes induction
tricky is that there is not a clear procedure for the “proof” part. With practice, you will start to see some common
algebra techniques for manipulating equations to prove what you are trying to prove.
Example A
There is something wrong with this proof. Can you explain what the mistake is?
For n≥1 : 1^2 + 22 + 32 +···+n^2 =n(n+^1 )( 62 n+^1 )
Base Case: 1 = 12 =^1 (^1 +^1 )( 62 ·^1 +^1 )=^1 ·^26 ·^3 =^66 = 1
Inductive Hypothesis:Assume the following statement is true:
12 + 22 + 32 +···+k^2 =k(k+^1 )( 62 k+^1 )
Proof:You want to show the statement is true fork+1.
“Since the statement is assumed true for k, which is any number, then it must be true for k+ 1. You can just substitute
k+ 1 in.”
12 + 22 + 32 +···+(k+ 1 )^2 =(k+^1 )((k+^1 )+ 61 )(^2 (k+^1 )+^1 )
Solution:This is the most common fallacy when doing induction proofs. The fact that the statement is assumed to
be true forkdoes not immediately imply that it is true fork+1 and you cannot just substitute ink+1 to produce
what you are trying to show. This is equivalent to assuming true for all numbers and then concluding true for all
numbers which is circular and illogical.
Example B
Write the base case, inductive hypothesis and what you are trying to show for the following statement. Do not
actually prove it.
13 + 23 + 33 +···+n^3 =n^2 (n 4 +^1 )^2
Solution:
Base Case: 13 =^12 (^14 +^1 )^2 (Both sides are equal to 1)
Inductive Hypothesis:Assume the following statement is true:
13 + 23 + 33 +···+k^3 =k^2 (k+ 41 )^2
Next, you would want to prove that the following is true:
13 + 23 + 33 +···+k^3 +(k+ 1 )^3 =(k+^1 )^2 ((k 4 +^1 )+^1 )^2
Example C
Prove the following statement:For n≥ 1 , 13 + 23 + 33 +···n^3 = ( 1 + 2 + 3 +···n)^2.
Solution: