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
  1. Notes
  2. /Induction for Sums and Divisibility: Quick Revision
Mathematics

Induction for Sums and Divisibility: Quick Revision

A brief note on the principle of induction, its base case and step, proofs of sums and products, and divisibility proofs with the add-and-subtract trick. With a worked example, practice, a program and questions to check yourself.

StemPy LabWritten by StemPy Lab
Log in to save

A brief note on Induction for Sums and Divisibility. Read it before a test. Try each question at the end before you open its answer.

The principle

  • Base case: show P(n0)P(n_0)P(n0​), usually P(1)P(1)P(1).
  • Step: assume P(k)P(k)P(k) for some k≥n0k \ge n_0k≥n0​ (the inductive hypothesis) and prove P(k+1)P(k + 1)P(k+1).
  • Conclusion: by induction, P(n)P(n)P(n) holds for every n≥n0n \ge n_0n≥n0​.
  • Checking cases is not a proof: n2−n+41n^2 - n + 41n2−n+41 is prime for n=1n = 1n=1 to 404040 and not for n=41n = 41n=41.

Sums and products

  • Shape of the step: S(k+1)=S(k)+termk+1S(k + 1) = S(k) + \text{term}_{k + 1}S(k+1)=S(k)+termk+1​, then use the hypothesis.
  • Squares: 12+⋯+n2=n(n+1)(2n+1)61^2 + \dots + n^2 = \dfrac{n(n + 1)(2n + 1)}{6}12+⋯+n2=6n(n+1)(2n+1)​.
  • Cubes: 13+⋯+n3=(n(n+1)2)21^3 + \dots + n^3 = \left(\dfrac{n(n + 1)}{2}\right)^213+⋯+n3=(2n(n+1)​)2.
  • Telescoping: 1k(k+1)=1k−1k+1\dfrac{1}{k(k + 1)} = \dfrac{1}{k} - \dfrac{1}{k + 1}k(k+1)1​=k1​−k+11​.
  • No formula given: work out small cases, guess, then prove.

Divisibility

  • Plan: f(k+1)=c f(k)+(a clear multiple of d)f(k + 1) = c\,f(k) + (\text{a clear multiple of } d)f(k+1)=cf(k)+(a clear multiple of d).
  • Trick: multiply f(k)f(k)f(k) by the base of the power and subtract.
  • Largest divisor: the highest common factor of the first values, then a proof.

A worked example

Prove that 3∣4n−13 \mid 4^n - 13∣4n−1 for every n≥1n \ge 1n≥1.

  1. Base. 4−1=34 - 1 = 34−1=3.
  2. Step. 4k+1−1=4(4k−1)+34^{k + 1} - 1 = 4(4^k - 1) + 34k+1−1=4(4k−1)+3.
  3. Conclusion. Both parts are multiples of 333, so by induction 3∣4n−13 \mid 4^n - 13∣4n−1 for every n≥1n \ge 1n≥1.

Practice with new numbers

A program to try

The program tests three results of this note for n=1n = 1n=1 to 505050.

Read it first. Then run it. Do all three lines say True?

1. Add a line that tests whether 555 divides n5−nn^5 - nn5−n for n=1n = 1n=1 to 505050.

Mistakes to avoid

  • No base case. A step alone proves nothing.
  • Assuming P(k+1)P(k + 1)P(k+1). Assume P(k)P(k)P(k) only.
  • Wrong next term. Term k+1k + 1k+1 of 12+22+…1^2 + 2^2 + \dots12+22+… is (k+1)2(k + 1)^2(k+1)2.
  • Dropping a term when you multiply f(k)f(k)f(k) by a number.

Check yourself

  1. What is the base case of 1+4+7+⋯+(3n−2)=n(3n−1)21 + 4 + 7 + \dots + (3n - 2) = \dfrac{n(3n - 1)}{2}1+4+7+⋯+(3n−2)=2n(3n−1)​?
  1. Prove the step for the same formula.
  1. Write 7k+1−17^{k + 1} - 17k+1−1 as 7(7k−1)7(7^k - 1)7(7k−1) plus a number.
  1. Find the largest number that divides 22n−12^{2n} - 122n−1 for every n≥1n \ge 1n≥1.

Sources

  • Arthur Engel, Problem-Solving Strategies, Chapter 8.
  • Richard Hammack, Book of Proof, Chapter 10.
← All Notes
← Vectors and Trigonometric Graphs: Quick RevisionStrong Induction, Inequalities and Recursion: Quick Revision →
More onMathematical Induction

Discussion (0)

Log in to join the discussion.

Loading…

On this page

  1. The principle
  2. Sums and products
  3. Divisibility
  4. A worked example
  5. Practice with new numbers
  6. A program to try
  7. Mistakes to avoid
  8. Check yourself
  9. Sources

Goes with the lesson

  1. Divisibility by inductionInduction for Sums and Divisibility

More notes on this topic

  1. Induction in Algebra, Calculus and Olympiad Problems: Quick Revision
  2. Strong Induction, Inequalities and Recursion: Quick Revision
All notes on this topic →