12.9. Induction Proofs http://www.ck12.org
Vocabulary
Thebase caseis the anchor step. It is the first domino to fall, creating a cascade and thus proving the statement true
for every number greater than the base case.
Theinductive hypothesisis the step where you assume the statement is true fork.
The inductive stepis the proof. It is when you show the statement is true fork+1 using only the inductive
hypothesis and algebra.
Guided Practice
- Write the base case, inductive hypothesis, and what you are trying to show for the following statement. Do not
actually prove it.
For n≥ 1 ,n^3 + 2 nis divisible by 3 for any positive integern - Complete the proof for the previous problem.
- Prove the following statement using induction:
For n≥ 1 , 1 + 2 + 3 + 4 +···+n=n(n 2 +^1 )
Answers:
1.Base Case: 13 + 2 · 1 =3 which is divisible by 3.
Inductive Step:Assume the following is true fork:
k^3 + 2 kdivisible by 3.
Next, you will want to show the following is true fork+1:
(k+ 1 )^3 + 2 (k+ 1 )is divisible by 3. - The goal is to show that(k+ 1 )^3 + 2 (k+ 1 )is divisible by 3 if you already knowk^3 + 2 kis divisible by 3. Expand
(k+ 1 )^3 + 2 (k+ 1 )to see what you get:
(k+ 1 )^3 + 2 (k+ 1 ) =k^3 + 3 k^2 + 3 k+ 1 + 2 k+ 2
= (k^3 + 2 k)+ 3 (k^2 +k+ 1 )k^3 + 2 kis divisible by 3 by assumption (the inductive step) and 3(k^2 +k+ 1 )is clearly a multiple of 3 so is divisible
by 3. The sum of two numbers that are divisible by is also divisible by 3.
∴
3.Base Case: 1 =^1 (^12 +^1 )= 1 ·^22 = 1
Inductive Hypothesis: 1 + 2 + 3 + 4 +···+k=k(k+ 21 )
Proof:Start with what you know and work to showing it true fork+1.
Inductive Hypothesis: 1+ 2 + 3 + 4 +···+k=k(k 2 +^1 )
Addk+1 to both sides: 1+ 2 + 3 + 4 +···+k+(k+ 1 ) =k(k 2 +^1 )+(k+ 1 )
Find a common denominator for the right side: 1+ 2 + 3 + 4 +···+k+(k+ 1 ) =k^2 + 2 k+^2 k 2 +^2
Simplify the right side: 1+ 2 + 3 + 4 +···+k+(k+ 1 ) =k^2 +^32 k+^2
Factor the numerator of the right side: 1+ 2 + 3 + 4 +···+k+(k+ 1 ) =(k+^1 )( 2 k+^2 )