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
Strong Induction, Inequalities and Recursion
  1. 1Inequalities by induction
  2. 2Strong induction and the well-ordering principle
  3. 3Sequences defined by recursion
  1. Mathematics
  2. /Strong Induction, Inequalities and Recursion
  3. /Strong induction and the well-ordering principle

Course 26.2·Lesson 2 of 3

Strong induction and the well-ordering principle

In strong induction you may assume every statement P(1),…,P(k)P(1), \dots, P(k)P(1),…,P(k) to prove P(k+1)P(k + 1)P(k+1)

Lesson 2 of 3Show all lessonsHide
Strong Induction, Inequalities and Recursion
  1. 1Inequalities by induction
  2. 2Strong induction and the well-ordering principle
  3. 3Sequences defined by recursion

Try the code and the simulations beside the lesson.

What you will be able to do

  • write a proof by strong induction with the right number of base cases;
  • use the well-ordering principle with a smallest counterexample;
  • choose between ordinary and strong induction.

When one step back is not enough

Every whole number n≥2n \ge 2n≥2 is a product of primes. Try to prove it by ordinary induction. Assume kkk is a product of primes. Does that tell us anything about k+1k + 1k+1? No. The factors of k+1k + 1k+1 have nothing to do with kkk. We need the smaller factors of k+1k + 1k+1, which could be any numbers below it.

Strong induction

Let P(n)P(n)P(n) be a statement for each n≥n0n \ge n_0n≥n0​. Suppose that:

  1. P(n0)P(n_0)P(n0​) is true;
  2. for every k≥n0k \ge n_0k≥n0​, if P(n0),P(n0+1),…,P(k)P(n_0), P(n_0 + 1), \dots, P(k)P(n0​),P(n0​+1),…,P(k) are all true, then P(k+1)P(k + 1)P(k+1) is true.

Then P(n)P(n)P(n) is true for every n≥n0n \ge n_0n≥n0​. The difference from ordinary induction is in the hypothesis: we may use every earlier statement, not only the last one. It is also called complete induction.

Prime factors. Let P(n)P(n)P(n) say that nnn is a product of primes, for n≥2n \ge 2n≥2. P(2)P(2)P(2) is true, since 222 is prime. Assume P(2),…,P(k)P(2), \dots, P(k)P(2),…,P(k). If k+1k + 1k+1 is prime, we are done. If not, k+1=abk + 1 = abk+1=ab with 2≤a,b≤k2 \le a, b \le k2≤a,b≤k. By the hypothesis, aaa and bbb are products of primes, so k+1k + 1k+1 is one too.

Stamps and base cases

Stamps come in 333 units and 555 units. Which amounts can be paid exactly? The amounts 111, 222, 444 and 777 cannot. We claim that every amount n≥8n \ge 8n≥8 can.

  1. Base cases. 8=3+58 = 3 + 58=3+5, 9=3+3+39 = 3 + 3 + 39=3+3+3, 10=5+510 = 5 + 510=5+5.
  2. Step. Let k+1≥11k + 1 \ge 11k+1≥11, and assume every amount from 888 to kkk can be paid. Then (k+1)−3≥8(k + 1) - 3 \ge 8(k+1)−3≥8, so k−2k - 2k−2 can be paid. Add one stamp of 333.
  3. Conclusion. By strong induction, every amount n≥8n \ge 8n≥8 can be paid.

Why three base cases? The step goes back 333 places. With only the base case 888, the step from 888 would reach 111111, 141414, 171717 and so on, and never 999 or 101010. A step that goes back rrr places needs rrr base cases in a row.

A row of numbered boxes for the amounts 1 to 14. The boxes 1, 2, 4 and 7 are red with a cross, because those amounts cannot be paid with stamps of 3 and 5. Every other box is green with its stamps written under it, for example 8 = 3 + 5, 9 = 3 + 3 + 3 and 10 = 5 + 5. A bracket over 8, 9 and 10 is labelled base cases, and arrows from 8 to 11, 9 to 12 and 10 to 13 are labelled add a 3.

For any two values aaa and bbb with no common factor, the largest amount that cannot be paid is ab−a−bab - a - bab−a−b. With 333 and 555 that is 15−8=715 - 8 = 715−8=7, as we found.

The well-ordering principle

Every non-empty set of positive integers has a least element.

It sounds obvious. Yet it fails for other sets: the positive fractions have no least element, and neither do all the integers. It is the reason induction works, and it gives a second style of proof.

Proof by a smallest counterexample. Suppose a statement is false for some positive integers. Among those there is a least one, mmm. Now show that a smaller counterexample exists, or that mmm cannot be a counterexample. Either way we have a contradiction, so there is no counterexample at all.

Example. Every n≥2n \ge 2n≥2 has a prime divisor. Let DDD be the set of divisors of nnn that are bigger than 111. It contains nnn, so it is not empty, and it has a least element ppp. If ppp were not prime, it would have a divisor ddd with 1<d<p1 < d < p1<d<p, and ddd would also divide nnn. Then ddd is in DDD and smaller than ppp, which is impossible. So ppp is prime.

Ordinary induction, strong induction and the well-ordering principle can each be proved from the others. Use the one that makes the argument shortest.

Practise with new numbers

Try it in Python

The program finds the amounts that cannot be paid with stamps of 333 and 555. Then it splits 360360360 into primes in the way the strong induction proof does.

Read it first. Then run it. Which amounts cannot be paid? Is 777 the largest?

1. Change the stamps to 444 and 777. Predict the largest amount that cannot be paid, then run it.

2. Change 360360360 to a prime such as 979797. What does prime_factors return, and why?

Common mistakes

  • Too few base cases. If the step uses P(k−2)P(k - 2)P(k−2), you need three base cases in a row.
  • A step that reaches below the base. The stamp step uses k−2k - 2k−2, which must be at least 888.
  • Thinking strong induction is a different truth. It proves the same things. It only lets the hypothesis say more.
  • Forgetting that the least element must exist. The well-ordering principle needs a non-empty set of positive integers.

Remember these

  • Strong induction: assume P(n0),…,P(k)P(n_0), \dots, P(k)P(n0​),…,P(k), prove P(k+1)P(k + 1)P(k+1).
  • A step that goes back rrr places needs rrr base cases.
  • Two values aaa, bbb with no common factor: the largest amount that cannot be paid is ab−a−bab - a - bab−a−b.
  • Well-ordering: every non-empty set of positive integers has a least element.

Check yourself

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

  1. Stamps come in 444 and 555 units. List the base cases for a proof that every amount from 121212 on can be paid.
  1. Why can ordinary induction not prove that every n≥2n \ge 2n≥2 is a product of primes in a simple way?
  1. Does the set of positive fractions have a least element?
  1. With stamps of 333 and 555, a student uses only the base case 888 and the step n→n+3n \to n + 3n→n+3. Which amounts has she proved?
  1. Use ab−a−bab - a - bab−a−b to find the largest amount that cannot be paid with stamps of 555 and 777.

References

  • Richard Hammack, Book of Proof, third edition, Chapter 10, sections on strong induction and proof by smallest counterexample.
  • Arthur Engel, Problem-Solving Strategies, Chapter 8, The Induction Principle.

Enroll free in Strong Induction, Inequalities and Recursion

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 games arcade sells tokens worth 4 points and 7 points…Hard · High School (11–12) · by StemPy Lab
The Fibonacci numbers are 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … (here we list each value once…Advanced · High School (11–12) · by StemPy Lab
A pile of n stones sits on a table. A player splits any pile with more than one stone into two…Advanced · High School (11–12) · by StemPy Lab
Next: lesson 3Sequences defined by recursion
← Strong Induction, Inequalities and Recursion
← Inequalities by inductionSequences defined by recursion →

Discussion (0)

Log in to join the discussion.

Loading…

. It handles results that look back more than one step, such as prime factors and stamp amounts. A step that looks back
rrr
places needs
rrr
base cases. The well-ordering principle, that every non-empty set of positive integers has a least element, is the same idea, used through a smallest counterexample.
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.