Lesson 4 of 7 · 18 min
Proving divisibility by induction
Prove that an expression is divisible by a given integer for every positive integer n, by writing the assumption as an equation with an integer multiple and substituting it.
What you will be able to do
- Write "divisible by " as an equation: for some .
- Rewrite so the assumption can be substituted, then factor out .
- Prove divisibility results involving one power, a polynomial, or two different powers.
Work out for the first few values of and divide each by :
Five cases are evidence, not proof. To prove that is divisible by for every positive integer , you need induction, and the key is to turn "divisible by " into something you can calculate with.
Definition
Divisible
An integer is divisible by a non-zero integer when for some integer .
So " is divisible by " means for some , which rearranges to . Note that is divisible by every .
In the inductive step, use the index laws to bring in the power from the assumption: . Then substitute and factor out . Step through the same method on another statement first.
The table shows for the first few values of : , each a multiple of .
Worked example
Prove is divisible by
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 .
Try it yourself first, then check the working one step at a time.
Answer
Proved: with , so the result holds for all .
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.
Substitute for the power
From the assumption, :
Split off the old expression
Add and subtract to make appear:
In a proof that is divisible by , the assumption is for some . Express in terms of .
When the expression is a polynomial in , there is no index law to use. Expand the expression for instead, and look for the expression from the assumption inside it.
Worked example
Prove is divisible by
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 .
Try it yourself first, then check the working one step at a time.
Answer
Proved: , a multiple of .
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.
To prove that is divisible by , you need in terms of . Expand and simplify .
With two different powers, such as , write each power for as a number times the power for . Then substitute for one of them using the assumption; the other power should combine into a multiple of the divisor.
Worked example
Prove is divisible by
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 .
Try it yourself first, then check the working one step at a time.
Answer
Proved: , a multiple of .
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.
Which expression equals ?
Common mistake
Common errors in divisibility proofs
- Using as the multiplier. "" is false for . The multiplier is an unknown integer, .
- Index law slips. , not .
- Stopping too early. is not the end. Factor out and say why the bracket is an integer.
Exam tip
Say why the bracket is an integer
State the domain of in the assumption ("for some "). After factoring, say why the other factor is an integer: "since and are integers, is an integer". That sentence is what turns the algebra into a divisibility argument.
Summary
Write the assumption as an equation: , .
With powers, use , substitute the assumption, then factor out .
With polynomials, expand the expression for and group the expression from the assumption.
With two different powers, substitute for one; the other should combine into a multiple of .
Finish by saying why the remaining factor is an integer, then write the conclusion.
Finished the lesson?
Try the 3 quick checks above and the lesson completes itself, or mark it complete now.