HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
Induction for Sums and Divisibility
  1. 1The principle of mathematical induction
  2. 2Sums and identities by induction
  3. 3Divisibility by induction
  1. Mathematics
  2. /Induction for Sums and Divisibility
  3. /Divisibility by induction

Course 26.1·Lesson 3 of 3

Divisibility by induction

To prove that ddd divides an expression f(n)f(n)f(n) for every nnn

Lesson 3 of 3Show all lessonsHide
Induction for Sums and Divisibility
  1. 1The principle of mathematical induction
  2. 2Sums and identities by induction
  3. 3Divisibility by induction

Try the code and the simulations beside the lesson.

What you will be able to do

  • prove that a number divides an expression in nnn for every nnn;
  • use the add-and-subtract trick in the inductive step;
  • find the largest number that always divides an expression.

What "divides" means

We write d∣md \mid md∣m and say "ddd divides mmm" when m=d×qm = d \times qm=d×q for a whole number qqq. Two facts carry every proof in this lesson.

  • If d∣ad \mid ad∣a and d∣bd \mid bd∣b, then d∣a+bd \mid a + bd∣a+b and d∣a−bd \mid a - bd∣a−b.
  • If d∣ad \mid ad∣a, then d∣c×ad \mid c \times ad∣c×a for every whole number ccc.

The plan

To prove d∣f(n)d \mid f(n)d∣f(n) for every n≥1n \ge 1n≥1:

  1. check that d∣f(1)d \mid f(1)d∣f(1);
  2. assume d∣f(k)d \mid f(k)d∣f(k);
  3. write f(k+1)=c×f(k)+(something that d divides)f(k + 1) = c \times f(k) + (\text{something that } d \text{ divides})f(k+1)=c×f(k)+(something that d divides).

Step 3 is the whole art. You build it by adding and subtracting a term.

A first example

Claim. 6∣7n−16 \mid 7^n - 16∣7n−1 for every n≥1n \ge 1n≥1.

  1. Base case. 7−1=67 - 1 = 67−1=6, and 6∣66 \mid 66∣6.
  2. Hypothesis. Assume 6∣7k−16 \mid 7^k - 16∣7k−1.
  3. Step. Write 7k+1−1=7×7k−7+7−1=7(7k−1)+67^{k + 1} - 1 = 7 \times 7^k - 7 + 7 - 1 = 7(7^k - 1) + 67k+1−1=7×7k−7+7−1=7(7k−1)+6.
  4. The first part is 777 times a multiple of 666. The second part is 666. So 6∣7k+1−16 \mid 7^{k + 1} - 16∣7k+1−1.

The same idea shows that a−1∣an−1a - 1 \mid a^n - 1a−1∣an−1 for every base a≥2a \ge 2a≥2, because ak+1−1=a(ak−1)+(a−1)a^{k + 1} - 1 = a(a^k - 1) + (a - 1)ak+1−1=a(ak−1)+(a−1).

A polynomial example

Claim. 6∣n3−n6 \mid n^3 - n6∣n3−n for every n≥1n \ge 1n≥1.

  1. Base case. 1−1=01 - 1 = 01−1=0, and 6∣06 \mid 06∣0.
  2. Step. Expand: (k+1)3−(k+1)=k3+3k2+3k+1−k−1=(k3−k)+3k(k+1)(k + 1)^3 - (k + 1) = k^3 + 3k^2 + 3k + 1 - k - 1 = (k^3 - k) + 3k(k + 1)(k+1)3−(k+1)=k3+3k2+3k+1−k−1=(k3−k)+3k(k+1).
  3. The first bracket is a multiple of 666 by the hypothesis. In the second, k(k+1)k(k + 1)k(k+1) is a product of two consecutive numbers, so it is even. Then 3k(k+1)3k(k + 1)3k(k+1) is a multiple of 666.

So 6∣(k+1)3−(k+1)6 \mid (k + 1)^3 - (k + 1)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−19 \mid 4^n + 15n - 19∣4n+15n−1 for every n≥1n \ge 1n≥1.

  1. Base case. 4+15−1=18=9×24 + 15 - 1 = 18 = 9 \times 24+15−1=18=9×2.
  2. Step. Let f(k)=4k+15k−1f(k) = 4^k + 15k - 1f(k)=4k+15k−1. We want f(k+1)f(k + 1)f(k+1) in terms of f(k)f(k)f(k). Multiply f(k)f(k)f(k) by 444 and compare:
f(k+1)−4f(k)=(4k+1+15k+14)−(4k+1+60k−4)=18−45k.\displaystyle f(k + 1) - 4f(k) = (4^{k + 1} + 15k + 14) - (4^{k + 1} + 60k - 4) = 18 - 45k.f(k+1)−4f(k)=(4k+1+15k+14)−(4k+1+60k−4)=18−45k.
  1. So f(k+1)=4f(k)−9(5k−2)f(k + 1) = 4f(k) - 9(5k - 2)f(k+1)=4f(k)−9(5k−2). Both parts are multiples of 999.

The trick: multiply f(k)f(k)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)f(n)f(n) for every nnn" is a common question. Two steps answer it.

  1. The answer must divide f(1)f(1)f(1), f(2)f(2)f(2), and so on. So it divides their highest common factor. This gives an upper bound.
  2. Prove by induction that this bound really divides every f(n)f(n)f(n).

For 4n+15n−14^n + 15n - 14n+15n−1 the first values are 181818, 454545 and 108108108. Their highest common factor is 999, and the proof above shows that 999 always works. So the answer is 999.

You met another method in the chapter on the binomial theorem: expand 7n=(6+1)n7^n = (6 + 1)^n7n=(6+1)n, and every term but the last has a factor 666. 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−14^n + 15n - 14n+15n−1 with its remainder on dividing by 999, finds the largest common divisor of the list, and prints the difference used in the step.

Read it first. Then run it. Is every remainder 000? Is every number in the last part a multiple of 999?

1. Change the expression to 5 ** n + 4 * n - 1 in both places. What is the largest common divisor now?

2. Change 4 * a in the last loop to 5 * a, to match the new base. What do you notice about the differences?

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)f(k + 1) - 4f(k)f(k+1)−4f(k), multiply every term of f(k)f(k)f(k) by 444, including 15k15k15k and −1-1−1.
  • Forgetting the second fact. The step for n3−nn^3 - nn3−n also needs "k(k+1)k(k + 1)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)f(k + 1) = c \times f(k) + (\text{a clear multiple of } d)f(k+1)=c×f(k)+(a clear multiple of d).
  • Multiply f(k)f(k)f(k) by the base of the power, and look at what is left.
  • a−1a - 1a−1 divides an−1a^n - 1an−1; 666 divides n3−nn^3 - nn3−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.

  1. Prove the step for 4∣5n−14 \mid 5^n - 14∣5n−1.
  1. Find the largest number that divides 5n+4n−15^n + 4n - 15n+4n−1 for every n≥1n \ge 1n≥1.
  1. In the step for 6∣n3−n6 \mid n^3 - n6∣n3−n, why is 3k(k+1)3k(k + 1)3k(k+1) a multiple of 666?
  1. Prove the step for 3∣22n−13 \mid 2^{2n} - 13∣22n−1.
  1. A student says that 999 divides 10n−110^n - 110n−1 for n=1,2,3n = 1, 2, 3n=1,2,3, so it divides it for every nnn. 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.
No payment. You can leave at any time.

Problems (3)

A clock face has 8 marks, numbered 0 to 7…Hard · High School (11–12) · by StemPy Lab
A number puzzle says: for every whole number n ≥ 0, the number 11^(n + 2) + 12^(2n + 1) is a…Advanced · High School (11–12) · by StemPy Lab
Let f(n) = n⁵ - n for whole numbers n ≥ 1…Advanced · High School (11–12) · by StemPy Lab
That was the last lessonBack to the course: take the test
← Induction for Sums and Divisibility
← Sums and identities by inductionNext →

Discussion (0)

Log in to join the discussion.

Loading…

, check
f(1)f(1)f(1)
, then write
f(k+1)f(k + 1)f(k+1)
as a multiple of
f(k)f(k)f(k)
plus a part that
ddd
clearly divides. Adding and subtracting a well-chosen term finds that form. Examples are
6∣7n−16 \mid 7^n - 16∣7n−1
,
6∣n3−n6 \mid n^3 - n6∣n3−n
and
9∣4n+15n−19 \mid 4^n + 15n - 19∣4n+15n−1
.
about 25 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.

Python Labs (1)

Divisibility, value by valuePython Lab · by StemPy Lab

Question Sets (1)

Induction for Sums and Divisibility: Check Your Understanding10 questions · by StemPy Lab

Notes (1)

Induction for Sums and Divisibility: Quick RevisionNote · by StemPy Lab