Lesson 4: Proving divisibility by induction
Why the digit test for 9 works
SkillProving divisibility by induction
Worked example
(a) Prove by mathematical induction that is divisible by for all .
(b) A three-digit number with digits , and equals . Use part (a) to show that it is divisible by exactly when is divisible by .
Step 1: (a) Initial statement
Let be the statement " is divisible by ". When : , so is true.
Step 2: (a) Assumption statement
Assume for some and some , so .
Step 3: (a) Inductive step
Since , is divisible by , so is true whenever is true.
Step 4: (a) Conclusion
By the principle of mathematical induction, is divisible by for all .
Step 5: (b) Separate the digit sum
Writing each power of as splits the number into a part that part (a) controls and the digit sum.
Step 6: (b) Use part (a)
By part (a), and are multiples of , so and
The first part is always a multiple of . So the number is a multiple of exactly when is.
Answer
(a) Proved for all . (b) The number and its digit sum differ by , a multiple of , so one is divisible by exactly when the other is.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
Prove the divisibility result by induction.
Split each power of into .
Use the result to show the difference is a multiple of the divisor.
Watch out for
In (b), checking a few numbers is not a proof. You need the algebraic split, which works for every choice of digits.