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. /The principle of mathematical induction

Course 26.1·Lesson 1 of 3

The principle of mathematical induction

Induction proves a statement P(n)P(n)P(n) for every whole number nnn from a starting value. You check the base case, then you show that whenever P(k)P(k)P(k)

Lesson 1 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

  • state the principle of mathematical induction and say why it works;
  • write an induction proof with a base case, an inductive step and a conclusion;
  • explain why checking many cases is not a proof.

A row of dominoes

Stand a long row of dominoes on a table. When do all of them fall? Two things are enough.

  1. The first domino falls.
  2. Each domino, when it falls, knocks over the next one.

You do not need to watch every domino. The first one falls, so the second falls, so the third falls, and so on along the whole row.

A row of eight dominoes standing on a line, numbered 1 to 8. Domino 1 is tipped over and touches domino 2, which is starting to tip. A label under domino 1 says base case: the first one falls. A curved arrow from domino k to domino k + 1 is labelled step: each one knocks over the next.

Statements that depend on n

Many results in mathematics are statements about a whole number nnn. Here is one:

P(n):1+3+5+⋯+(2n−1)=n2.\displaystyle P(n):\quad 1 + 3 + 5 + \dots + (2n - 1) = n^2.P(n):1+3+5+⋯+(2n−1)=n2.

For each nnn we get one statement. P(1)P(1)P(1) says 1=11 = 11=1. P(2)P(2)P(2) says 1+3=41 + 3 = 41+3=4. P(3)P(3)P(3) says 1+3+5=91 + 3 + 5 = 91+3+5=9. We want all of them at once, for every n≥1n \ge 1n≥1. There are infinitely many, so checking them one by one can never finish.

The principle of mathematical induction

Let P(n)P(n)P(n) be a statement for each whole number n≥1n \ge 1n≥1. Suppose that:

  1. the base case holds: P(1)P(1)P(1) is true;
  2. the inductive step holds: for every k≥1k \ge 1k≥1, if P(k)P(k)P(k) is true, then P(k+1)P(k + 1)P(k+1) is true.

Then P(n)P(n)P(n) is true for every whole number n≥1n \ge 1n≥1.

The assumption "P(k)P(k)P(k) is true" inside the step is called the inductive hypothesis. We do not know yet that it is true. We only show that if it is true, then the next statement follows.

Why does this work? Suppose some P(n)P(n)P(n) were false. Among the false ones there is a smallest, say P(m)P(m)P(m). It is not P(1)P(1)P(1), because the base case holds. So P(m−1)P(m - 1)P(m−1) is true, and the step makes P(m)P(m)P(m) true. That is a contradiction. Course 2 names the fact used here: the well-ordering principle.

A first proof

Claim. For every n≥1n \ge 1n≥1, 1+3+5+⋯+(2n−1)=n21 + 3 + 5 + \dots + (2n - 1) = n^21+3+5+⋯+(2n−1)=n2.

  1. Base case. For n=1n = 1n=1 the left side is 111 and the right side is 12=11^2 = 112=1. So P(1)P(1)P(1) is true.
  2. Inductive hypothesis. Assume P(k)P(k)P(k) for some k≥1k \ge 1k≥1: 1+3+⋯+(2k−1)=k21 + 3 + \dots + (2k - 1) = k^21+3+⋯+(2k−1)=k2.
  3. Inductive step. The next odd number is 2(k+1)−1=2k+12(k + 1) - 1 = 2k + 12(k+1)−1=2k+1. Add it to both sides:
1+3+⋯+(2k−1)+(2k+1)=k2+2k+1=(k+1)2.\displaystyle 1 + 3 + \dots + (2k - 1) + (2k + 1) = k^2 + 2k + 1 = (k + 1)^2.1+3+⋯+(2k−1)+(2k+1)=k2+2k+1=(k+1)2.

This is exactly P(k+1)P(k + 1)P(k+1).

  1. Conclusion. P(1)P(1)P(1) is true, and P(k)P(k)P(k) implies P(k+1)P(k + 1)P(k+1) for every k≥1k \ge 1k≥1. By induction, P(n)P(n)P(n) is true for every n≥1n \ge 1n≥1.

The picture shows the same step. Each new odd number is an L-shaped layer that turns a k×kk \times kk×k square into a (k+1)×(k+1)(k + 1) \times (k + 1)(k+1)×(k+1) square.

A 5 by 5 square of small squares coloured in five L-shaped layers. The corner square is 1, the next L-shaped layer has 3 squares, then 5, then 7, then 9. Labels show 1 + 3 + 5 + 7 + 9 = 25 = 5 squared, and that adding the layer 2k + 1 turns a k by k square into a k + 1 by k + 1 square.

A second proof

Claim. For every n≥1n \ge 1n≥1, 1+2+3+⋯+n=n(n+1)21 + 2 + 3 + \dots + n = \dfrac{n(n + 1)}{2}1+2+3+⋯+n=2n(n+1)​.

  1. Base case. For n=1n = 1n=1: 1=1×221 = \dfrac{1 \times 2}{2}1=21×2​. True.
  2. Hypothesis. Assume 1+2+⋯+k=k(k+1)21 + 2 + \dots + k = \dfrac{k(k + 1)}{2}1+2+⋯+k=2k(k+1)​.
  3. Step. Add k+1k + 1k+1 to both sides. The right side becomes
k(k+1)2+(k+1)=(k+1)(k+2)2,\displaystyle \dfrac{k(k + 1)}{2} + (k + 1) = \dfrac{(k + 1)(k + 2)}{2},2k(k+1)​+(k+1)=2(k+1)(k+2)​,

which is the formula with n=k+1n = k + 1n=k+1.

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

A good habit: write down the target P(k+1)P(k + 1)P(k+1) before you start the step. Then you know where the algebra must end.

A staircase of blue squares with columns of height 1, 2, 3, 4 and 5, and a copy of the same staircase in orange turned upside down and fitted on top. Together they make a rectangle 5 squares wide and 6 squares tall, so twice the sum 1 + 2 + 3 + 4 + 5 is 5 times 6.

Starting somewhere else

The base case need not be n=1n = 1n=1. If P(n0)P(n_0)P(n0​) is true, and P(k)P(k)P(k) implies P(k+1)P(k + 1)P(k+1) for every k≥n0k \ge n_0k≥n0​, then P(n)P(n)P(n) is true for every n≥n0n \ge n_0n≥n0​. Course 2 uses this for inequalities that only start to hold at n=5n = 5n=5 or later.

How the proof is written in different books

  • Indian textbooks name the statement P(n)P(n)P(n) and write the step as "assume P(k)P(k)P(k), prove P(k+1)P(k + 1)P(k+1)".
  • A-Level Further Mathematics and IB Higher Level mark schemes give credit for each part: the base case, the assumption for n=kn = kn=k, the step to n=k+1n = k + 1n=k+1, and a concluding sentence. Always write the conclusion in full.
  • Some books count the natural numbers from 000, others from 111. Say clearly where your base case is.

Practise with new numbers

Try it in Python

The program checks the odd-number formula for n=1n = 1n=1 to 101010. Then it tests a famous pattern: n2−n+41n^2 - n + 41n2−n+41 is prime for a long run of nnn.

Read it first. Then run it. Look at the last two lines.

1. Change the first loop to test 1+2+⋯+n1 + 2 + \dots + n1+2+⋯+n against n * (n + 1) // 2. Do all ten rows say True?

2. The pattern breaks at n=41n = 41n=41. Can you see why without a computer? Put n=41n = 41n=41 into n2−n+41n^2 - n + 41n2−n+41.

Common mistakes

  • Skipping the base case. A step can work while every statement is false. Course 3 has examples.
  • Assuming what you want to prove. In the step you assume P(k)P(k)P(k), never P(k+1)P(k + 1)P(k+1).
  • Testing is not proving. The pattern n2−n+41n^2 - n + 41n2−n+41 gives primes for n=1n = 1n=1 to 404040 and fails at n=41n = 41n=41.
  • No conclusion. End with a sentence that names both steps and says "by induction".

Remember these

  • Base case P(1)P(1)P(1), then the step: P(k)P(k)P(k) true implies P(k+1)P(k + 1)P(k+1) true, for every k≥1k \ge 1k≥1.
  • The assumption P(k)P(k)P(k) is the inductive hypothesis.
  • Write the target P(k+1)P(k + 1)P(k+1) first.
  • A base case at n0n_0n0​ gives the result for every n≥n0n \ge n_0n≥n0​.

Check yourself

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

  1. What is the base case of the claim 2+4+6+⋯+2n=n(n+1)2 + 4 + 6 + \dots + 2n = n(n + 1)2+4+6+⋯+2n=n(n+1), and is it true?
  1. In the step of the same claim, what do you add to both sides of P(k)P(k)P(k)?
  1. A statement P(n)P(n)P(n) is true for n=5n = 5n=5, and P(k)P(k)P(k) implies P(k+1)P(k + 1)P(k+1) for every k≥5k \ge 5k≥5. For which nnn do we know that P(n)P(n)P(n) is true?
  1. A computer checks a formula for every nnn from 111 to 100010001000. Is that a proof for every nnn?
  1. Write P(k+1)P(k + 1)P(k+1) for P(n)P(n)P(n): 1+2+4+⋯+2n−1=2n−11 + 2 + 4 + \dots + 2^{n - 1} = 2^n - 11+2+4+⋯+2n−1=2n−1. Then prove the step.

References

  • Richard Hammack, Book of Proof, third edition, Chapter 10, Mathematical Induction.
  • NCERT, Mathematics Textbook for Class XI (2006 edition), Chapter 4, Principle of 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 (3)

A tiler lays a triangle-shaped panel on a wall, one row at a time…Hard · High School (11–12) · by StemPy Lab
A surveyor measures the corner angles of plots of land shaped as convex polygons…Hard · High School (11–12) · by StemPy Lab
A shop builds a display of cans in layers…Advanced · High School (11–12) · by StemPy Lab
Next: lesson 2Sums and identities by induction
← Induction for Sums and Divisibility
← PreviousSums and identities by induction →

Discussion (0)

Log in to join the discussion.

Loading…

is true,
P(k+1)P(k + 1)P(k+1)
is true. The two steps together reach every
nnn
, like a row of dominoes. Checking many cases is not a proof, as the pattern
n2−n+41n^2 - n + 41n2−n+41
shows.
about 30 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)

Test a formula, then find where a pattern breaksPython Lab · by StemPy Lab