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 in Algebra, Calculus and Olympiad Problems
  1. 1Induction with binomials, matrices and derivatives
  2. 2Flawed inductions: finding the error
  3. 3Induction in olympiad problems
  1. Mathematics
  2. /Induction in Algebra, Calculus and Olympiad Problems
  3. /Flawed inductions: finding the error

Course 26.3·Lesson 2 of 3

Flawed inductions: finding the error

A flawed induction looks like a proof but is not one. The usual errors are a missing base case and a step that fails for one small value of kkk. Others are too few base cases, assuming what is to be proved, and trusting a pattern without a proof. Finding the exact line that fails is a skill the exams test.

about 25 min1 simulation
Lesson 2 of 3Show all lessonsHide
Induction in Algebra, Calculus and Olympiad Problems
  1. 1Induction with binomials, matrices and derivatives
  2. 2Flawed inductions: finding the error
  3. 3Induction in olympiad problems

Try the code and the simulations beside the lesson.

What you will be able to do

  • find the error in a false proof by induction;
  • explain why a step that works is not enough;
  • see why a pattern from small cases can mislead.

All horses are the same colour

Here is a famous false proof. Read it and find the error before you read on.

Claim. In every group of nnn horses, all the horses have the same colour.

  1. Base case. A group of 111 horse has one colour.
  2. Step. Take a group of k+1k + 1k+1 horses. Leave out the first horse: the other kkk have one colour, by the hypothesis. Leave out the last horse: the first kkk have one colour. The two groups overlap, so all k+1k + 1k+1 horses have the same colour.

The step is fine for most kkk. But look at k=1k = 1k=1, the step from 111 horse to 222 horses. Leaving out the first horse gives {horse 2}\{\text{horse } 2\}{horse 2}. Leaving out the last gives {horse 1}\{\text{horse } 1\}{horse 1}. These two groups do not overlap. Nothing links the two colours. One broken domino, between the first and the second, and the whole chain stops.

Two panels. On the left, three horses numbered 1, 2 and 3. A blue loop goes round horses 2 and 3, labelled leave out horse 1, and an orange loop goes round horses 1 and 2, labelled leave out horse 3. The loops overlap on horse 2, labelled shared. On the right, two horses numbered 1 and 2. The blue loop holds only horse 2 and the orange loop holds only horse 1, and a label says no horse is shared, so the step from 1 to 2 breaks.

The lesson: a step must work for every k≥n0k \ge n_0k≥n0​, including the smallest.

A step with no base case

Claim. n(n+1)+1n(n + 1) + 1n(n+1)+1 is even for every n≥1n \ge 1n≥1.

The step works: (k+1)(k+2)+1=k(k+1)+1+2(k+1)(k + 1)(k + 2) + 1 = k(k + 1) + 1 + 2(k + 1)(k+1)(k+2)+1=k(k+1)+1+2(k+1). If the first part is even, so is the sum. But there is no true base case. In fact n(n+1)n(n + 1)n(n+1) is always even, so n(n+1)+1n(n + 1) + 1n(n+1)+1 is always odd. The claim is false for every nnn. The dominoes are set up well, but nobody pushes the first one.

A pattern that breaks

Put nnn points on a circle and join every pair by a chord, with no three chords through one point inside. Count the regions inside the circle. For n=1,2,3,4,5n = 1, 2, 3, 4, 5n=1,2,3,4,5 you get 1,2,4,8,161, 2, 4, 8, 161,2,4,8,16. Surely the next is 323232? It is 313131.

Six circles in a row with 1, 2, 3, 4, 5 and 6 points on them, every pair of points joined by a chord. Under each circle the number of regions inside it is written: 1, 2, 4, 8, 16 and 31. The last number is circled in red, because the doubling pattern would give 32.

The true count is 1+(n2)+(n4)1 + \dbinom{n}{2} + \dbinom{n}{4}1+(2n​)+(4n​), which equals 2n−12^{n - 1}2n−1 only up to n=5n = 5n=5. You met another such pattern in course 1: n2−n+41n^2 - n + 41n2−n+41 is prime for n=1n = 1n=1 to 404040. A guess needs a proof.

Too few base cases

Claim. Every amount of 111 unit or more can be paid with coins of 333 and 555 units. Proof. True for 333 and 555. If k−2k - 2k−2 can be paid, add a 333 to pay k+1k + 1k+1.

The step looks back 333 places, so it needs three base cases in a row, and the proof never checks 111, 222 or 444. Those amounts cannot be paid at all. Strong induction needs as many base cases as the step reaches back.

Assuming the result

A student writes: "Assume the formula holds for n=k+1n = k + 1n=k+1. Then ..." and works backwards to something true. That proves nothing. From a false start you can sometimes reach a true end, for example 1=21 = 21=2 gives 0×1=0×20 \times 1 = 0 \times 20×1=0×2. The step must start from P(k)P(k)P(k) and end at P(k+1)P(k + 1)P(k+1).

A checklist for any induction

  1. Is the base case checked, and is it true?
  2. Does the step use only the hypothesis and known facts?
  3. Does the step work for the smallest kkk it is used for?
  4. If the step looks back rrr places, are there rrr base cases?
  5. Does the step end with P(k+1)P(k + 1)P(k+1), rather than start from it?

Practise with new numbers

Try it in Python

The program prints the circle regions next to the powers of 222, and it looks for values of nnn that make n(n+1)+1n(n + 1) + 1n(n+1)+1 even.

Read it first. Then run it. Where do the two columns first differ? Does the list at the end have anything in it?

1. Add a third column with 1 + n * (n - 1) // 2, the count without the crossings. When does it differ from the regions?

2. Change the claim to n * (n + 1) % 2 == 0. Which values of nnn make it true now?

Common mistakes

  • Checking the step only for a large kkk. The horses fail at k=1k = 1k=1.
  • Trusting a working step. Without a true base case it proves nothing.
  • Believing a pattern. Check, then prove.
  • Working backwards from P(k+1)P(k + 1)P(k+1). That is assuming the result.

Remember these

  • A step must work for every kkk from the base case on.
  • A true base case is needed, and enough of them for strong induction.
  • Small cases suggest a guess. Only a proof settles it.
  • Run the five-point checklist on every proof you write.

Check yourself

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

  1. In the horses proof, the step from 222 horses to 333 horses works. Why?
  1. A student proves "3n+13^n + 13n+1 is a multiple of 444" with the step 3k+1+1=3(3k+1)−23^{k + 1} + 1 = 3(3^k + 1) - 23k+1+1=3(3k+1)−2. What is wrong?
  1. How many regions do 666 points on a circle make?
  1. A proof shows P(k)⇒P(k+1)P(k) \Rightarrow P(k + 1)P(k)⇒P(k+1) for every k≥1k \ge 1k≥1 and checks P(3)P(3)P(3). What has it proved?
  1. Why is "assume P(k+1)P(k + 1)P(k+1) and reach a true statement" not a proof?

References

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

Enroll free in Induction in Algebra, Calculus and Olympiad Problems

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 student claims that, for every whole number n ≥ 1, 1 + 2 + 3 + … + n = ((2n + 1)²)/8.…Hard · High School (11–12) · by StemPy Lab
Read this false proof carefully. Claim. For every n ≥ 2: if n lines in the plane are such that no…Advanced · High School (11–12) · by StemPy Lab
A student puts n points on a circle and joins every pair by a straight chord, choosing the points…Hard · High School (11–12) · by StemPy Lab
Next: lesson 3Induction in olympiad problems
← Induction in Algebra, Calculus and Olympiad Problems
← Induction with binomials, matrices and derivativesInduction in olympiad problems →

Discussion (0)

Log in to join the discussion.

Loading…

1 practice question
1 Python program
5 questions to check yourself

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