Lesson 4: Proving divisibility by induction
Prove is divisible by
SkillsProving divisibility by inductionStructure of an induction proof
Worked example
Prove by mathematical induction that is divisible by for all .
Step 1: Initial statement
Let be the statement " is divisible by ", . When : . So is true.
Step 2: Assumption statement
Assume is true for some : for some . Rearranged, .
"Divisible by " means "equal to times an integer". Writing it as an equation gives you something to substitute.
Step 3: Bring in the power from the assumption
The index law brings in , which the assumption tells you about.
Step 4: Substitute the assumption
Step 5: Factor out 6
. Since is an integer, is an integer. So is divisible by , and is true whenever is true.
Step 6: Conclusion
is true, and true implies true. By the principle of mathematical induction, is divisible by for all .
Answer
Proved: with , so the result holds for all .
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
Write the assumption as an equation, with .
Use index laws to write in terms of the power in .
Substitute the assumption.
Factor out and say why the other factor is an integer.
Watch out for
Writing the assumption as . The multiplier is an unknown integer , not .
Stopping at without factoring out and saying that the bracket is an integer.