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. /Sums and identities by induction

Course 26.1·Lesson 2 of 3

Sums and identities by induction

Induction proves formulas for sums and products. Write P(k+1)P(k + 1)P(k+1) as P(k)P(k)P(k)

Lesson 2 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 formulas for sums of squares and cubes by induction;
  • prove telescoping sums and products of fractions;
  • guess a formula from small cases and then prove it.

The shape of every sum proof

Let S(n)S(n)S(n) be the sum of the first nnn terms of a list, and suppose we want S(n)=F(n)S(n) = F(n)S(n)=F(n) for a formula FFF. The step always runs the same way.

  1. S(k+1)=S(k)+(term number k+1)S(k + 1) = S(k) + (\text{term number } k + 1)S(k+1)=S(k)+(term number k+1).
  2. Replace S(k)S(k)S(k) by F(k)F(k)F(k). This is where the hypothesis is used.
  3. Show that F(k)+(term k+1)=F(k+1)F(k) + (\text{term } k + 1) = F(k + 1)F(k)+(term k+1)=F(k+1). This is pure algebra.

So the step is a single identity. Factorise early. The common factor is usually (k+1)(k + 1)(k+1).

The sum of squares

Claim. 12+22+⋯+n2=n(n+1)(2n+1)61^2 + 2^2 + \dots + n^2 = \dfrac{n(n + 1)(2n + 1)}{6}12+22+⋯+n2=6n(n+1)(2n+1)​ for every n≥1n \ge 1n≥1.

  1. Base case. For n=1n = 1n=1: 1×2×36=1=12\dfrac{1 \times 2 \times 3}{6} = 1 = 1^261×2×3​=1=12.
  2. Step. Assume the formula for n=kn = kn=k. Then
12+⋯+k2+(k+1)2=k(k+1)(2k+1)6+(k+1)2.\displaystyle 1^2 + \dots + k^2 + (k + 1)^2 = \dfrac{k(k + 1)(2k + 1)}{6} + (k + 1)^2.12+⋯+k2+(k+1)2=6k(k+1)(2k+1)​+(k+1)2.
  1. Take out k+16\dfrac{k + 1}{6}6k+1​: the bracket left is k(2k+1)+6(k+1)=2k2+7k+6=(k+2)(2k+3)k(2k + 1) + 6(k + 1) = 2k^2 + 7k + 6 = (k + 2)(2k + 3)k(2k+1)+6(k+1)=2k2+7k+6=(k+2)(2k+3).
  2. So the sum is (k+1)(k+2)(2k+3)6\dfrac{(k + 1)(k + 2)(2k + 3)}{6}6(k+1)(k+2)(2k+3)​. This is the formula with n=k+1n = k + 1n=k+1, since 2(k+1)+1=2k+32(k + 1) + 1 = 2k + 32(k+1)+1=2k+3.

By induction the formula holds for every n≥1n \ge 1n≥1.

The sum of cubes

The sum of the first nnn cubes is the square of the sum of the first nnn numbers:

13+23+⋯+n3=(n(n+1)2)2.\displaystyle 1^3 + 2^3 + \dots + n^3 = \left(\dfrac{n(n + 1)}{2}\right)^2.13+23+⋯+n3=(2n(n+1)​)2.

In the step, take out (k+1)24\dfrac{(k + 1)^2}{4}4(k+1)2​. What is left is k2+4(k+1)=(k+2)2k^2 + 4(k + 1) = (k + 2)^2k2+4(k+1)=(k+2)2. Try it yourself in Check yourself.

Telescoping sums

Now take fractions:

11×2+12×3+⋯+1n(n+1)=nn+1.\displaystyle \dfrac{1}{1 \times 2} + \dfrac{1}{2 \times 3} + \dots + \dfrac{1}{n(n + 1)} = \dfrac{n}{n + 1}.1×21​+2×31​+⋯+n(n+1)1​=n+1n​.

The step needs kk+1+1(k+1)(k+2)=k+1k+2\dfrac{k}{k + 1} + \dfrac{1}{(k + 1)(k + 2)} = \dfrac{k + 1}{k + 2}k+1k​+(k+1)(k+2)1​=k+2k+1​. Over the common denominator (k+1)(k+2)(k + 1)(k + 2)(k+1)(k+2) the top is k(k+2)+1=(k+1)2k(k + 2) + 1 = (k + 1)^2k(k+2)+1=(k+1)2. Cancel one (k+1)(k + 1)(k+1), and we are done.

There is also a direct proof: 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​, so the terms cancel in pairs. Both proofs are fine. Induction is the safe choice when you cannot see the cancelling.

Products

A product works like a sum, with multiplying in place of adding:

(1+11)(1+12)⋯(1+1n)\displaystyle \left(1 + \dfrac{1}{1}\right)\left(1 + \dfrac{1}{2}\right)\cdots\left(1 + \dfrac{1}{n}\right)(1+11​)(1+21​)⋯(1+n1​)
=n+1.\displaystyle = n + 1.=n+1.

The step multiplies k+1k + 1k+1 by the next factor 1+1k+1=k+2k+11 + \dfrac{1}{k + 1} = \dfrac{k + 2}{k + 1}1+k+11​=k+1k+2​. The result is k+2k + 2k+2.

Guess, then prove

Sometimes no formula is given. Then:

  1. work out the first few values;
  2. look for a pattern and write a guess;
  3. prove the guess by induction.

Example. Find 1×1!+2×2!+⋯+n×n!1 \times 1! + 2 \times 2! + \dots + n \times n!1×1!+2×2!+⋯+n×n!. The values for n=1,2,3,4n = 1, 2, 3, 4n=1,2,3,4 are 111, 555, 232323, 119119119. Each is one less than a factorial: 2!−12! - 12!−1, 3!−13! - 13!−1, 4!−14! - 14!−1, 5!−15! - 15!−1. So we guess (n+1)!−1(n + 1)! - 1(n+1)!−1. The step adds (k+1)(k+1)!(k + 1)(k + 1)!(k+1)(k+1)! to (k+1)!−1(k + 1)! - 1(k+1)!−1, which gives (k+2)(k+1)!−1=(k+2)!−1(k + 2)(k + 1)! - 1 = (k + 2)! - 1(k+2)(k+1)!−1=(k+2)!−1.

Practise with new numbers

Try it in Python

The program prints the telescoping sum as exact fractions, so the pattern is easy to see. Then it tests the guess and the sum of squares on many values.

Read it first. Then run it. What pattern do the fractions in the first part follow?

1. Change the term to Fraction(1, (2 * n - 1) * (2 * n + 1)). Print the sums and guess a new formula.

2. In part 3, replace the squares by cubes and the formula by (n * (n + 1) // 2) ** 2. Does it still print True?

Common mistakes

  • Adding the wrong term. Term number k+1k + 1k+1 of 12+22+…1^2 + 2^2 + \dots12+22+… is (k+1)2(k + 1)^2(k+1)2, not k2+1k^2 + 1k2+1.
  • Expanding everything. Large expansions hide the target. Take out the common factor first.
  • Forgetting the base case of a guess. A guessed formula must pass the base case too.
  • Stopping at the algebra. The last line must say that the result is P(k+1)P(k + 1)P(k+1).

Remember these

  • 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)​ and 13+⋯+n3=(n(n+1)2)21^3 + \dots + n^3 = \left(\dfrac{n(n + 1)}{2}\right)^213+⋯+n3=(2n(n+1)​)2.
  • The step: S(k+1)=S(k)+next termS(k + 1) = S(k) + \text{next term}S(k+1)=S(k)+next term, then use the hypothesis.
  • 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: compute, guess, prove.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

  1. Finish the step for the sum of cubes: show that (k(k+1)2)2+(k+1)3=((k+1)(k+2)2)2\left(\dfrac{k(k + 1)}{2}\right)^2 + (k + 1)^3 = \left(\dfrac{(k + 1)(k + 2)}{2}\right)^2(2k(k+1)​)2+(k+1)3=(2(k+1)(k+2)​)2.
  1. What is term number k+1k + 1k+1 of the sum 1×3+2×4+3×5+…1 \times 3 + 2 \times 4 + 3 \times 5 + \dots1×3+2×4+3×5+…?
  1. Guess a formula for 12+14+⋯+12n\dfrac{1}{2} + \dfrac{1}{4} + \dots + \dfrac{1}{2^n}21​+41​+⋯+2n1​ and prove the step.
  1. Let Pn=(1−12)⋯(1−1n+1)P_n = \left(1 - \dfrac{1}{2}\right)\cdots\left(1 - \dfrac{1}{n + 1}\right)Pn​=(1−21​)⋯(1−n+11​). Prove the step for
Pn=1n+1.\displaystyle P_n = \dfrac{1}{n + 1}.Pn​=n+11​.
  1. A student writes the step of the sum of squares as "S(k+1)=S(k)+k2+1S(k + 1) = S(k) + k^2 + 1S(k+1)=S(k)+k2+1". What is wrong?

References

  • Arthur Engel, Problem-Solving Strategies, Chapter 8, The Induction Principle.
  • Richard Hammack, Book of Proof, third edition, Chapter 10, Mathematical Induction.

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 (4)

A student builds towers of small cubes. Tower r is a solid cube with edge r cubes, so it uses r³…Hard · High School (11–12) · by StemPy Lab
An engineer adds up the fractions S(n) = 1/(1 × 3) + 1/(3 × 5) + 1/(5 × 7) + … + 1/((2n - 1)(2n +…Advanced · High School (11–12) · by StemPy Lab
A machine passes a signal through a chain of stages…Hard · High School (11–12) · by StemPy Lab
Next: lesson 3Divisibility by induction
← Induction for Sums and Divisibility
← The principle of mathematical inductionDivisibility by induction →

Discussion (0)

Log in to join the discussion.

Loading…

plus one more term, use the hypothesis, and make the algebra reach the target. The sums of squares and cubes, telescoping sums of fractions and products that cancel are standard. When no formula is given, work out small cases, guess the pattern and then prove it.
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.

A puzzle book asks for the value of T(n) = 1 × 1! …Advanced · High School (11–12) · by StemPy Lab