The first bracket is a multiple of 6 by the hypothesis. In the second, k(k+1) is a product of two consecutive numbers, so it is even. Then 3k(k+1) is a multiple of 6.
So 6∣(k+1)3−(k+1). Notice that the step used a second, simpler fact. Many divisibility proofs need one.
When the extra part has n in it
Claim.9∣4n+15n−1 for every n≥1.
Base case.4+15−1=18=9×2.
Step. Let f(k)=4k+15k−1. We want f(k+1) in terms of f(k). Multiply f(k) by 4 and compare:
f(k+1)−4f(k)=(4k+1+15k+14)−(4k+1+60k−4)=18−45k.
So f(k+1)=4f(k)−9(5k−2). Both parts are multiples of 9.
The trick: multiply f(k) by the base of the power, so the powers cancel, and look at what is left.
The largest divisor
"Find the largest number that divides f(n) for every n" is a common question. Two steps answer it.
The answer must divide f(1), f(2), and so on. So it divides their highest common factor. This gives an upper bound.
Prove by induction that this bound really divides every f(n).
For 4n+15n−1 the first values are 18, 45 and 108. Their highest common factor is 9, and the proof above shows that 9 always works. So the answer is 9.
You met another method in the chapter on the binomial theorem: expand 7n=(6+1)n, and every term but the last has a factor 6. Both methods are accepted. Induction works even when no binomial is in sight.
Practise with new numbers
Try it in Python
The program lists 4n+15n−1 with its remainder on dividing by 9, finds the largest common divisor of the list, and prints the difference used in the step.
Common mistakes
Proving only a few cases. A list of remainders is evidence. The step is the proof.
Losing a term. In f(k+1)−4f(k), multiply every term of f(k) by 4, including 15k and −1.
Forgetting the second fact. The step for n3−n also needs "k(k+1) is even".
Stopping at an upper bound. The highest common factor of a few values is a candidate. It still needs a proof.
Remember these
Base case, then f(k+1)=c×f(k)+(a clear multiple of d).
Multiply f(k) by the base of the power, and look at what is left.
a−1 divides an−1; 6 divides n3−n.
The largest divisor: take the highest common factor of the first values, then prove it by induction.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Prove the step for 4∣5n−1.
Find the largest number that divides 5n+4n−1 for every n≥1.
In the step for 6∣n3−n, why is 3k(k+1) a multiple of 6?
Prove the step for 3∣22n−1.
A student says that 9 divides 10n−1 for n=1,2,3, so it divides it for every n. What should the student add?
References
Arthur Engel, Problem-Solving Strategies, Chapter 8, The Induction Principle.
NCERT, Mathematics Textbook for Class XI (2006 edition), Chapter 4, the examples on divisibility.
Enroll free in Induction for Sums and Divisibility
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.