Lesson 4: Proving divisibility by induction
Prove is divisible by
SkillProving divisibility by induction
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 for some and some . Rearranged, .
Solve the assumption for one of the two powers. Either choice works; here is replaced.
Step 3: Write the next case using the old powers
and .
Step 4: Substitute the assumption
Step 5: Factor out 5
. Since and are integers, is an integer, so is true whenever is true.
Step 6: Conclusion
is true and , so by the principle of mathematical induction is divisible by for all .
Answer
Proved: , a multiple of .
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
Rewrite each power for as a number times the power for .
Replace one power using the assumption.
Collect the other power: its coefficient should be a multiple of the divisor.
Factor out the divisor and say why the bracket is an integer.
Watch out for
Writing as . The multiplies all of , so the power rises by .
Trying to substitute for both powers at once. Replace one and the other combines into a multiple of the divisor.