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 is true for some : for some .
Step 3: Expand the next case
There is no index law to use here, so expand and look for the expression from the assumption.
Step 4: Regroup to find the assumption
Step 5: Substitute and factor out 3
. 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
Expand the expression for .
Group the terms that make up the expression for , and replace them by .
Factor out from what is left and say why the bracket is an integer.
Watch out for
Expanding as . It is .
Not grouping together, so the assumption never gets used.