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 k. 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
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 n horses, all the horses have the same colour.
Base case. A group of 1 horse has one colour.
Step. Take a group of k+1 horses. Leave out the first horse: the other k have one colour, by the hypothesis. Leave out the last horse: the first k have one colour. The two groups overlap, so all k+1 horses have the same colour.
The step is fine for most k. But look at k=1, the step from 1 horse to 2 horses. Leaving out the first horse gives {horse 2}. Leaving out the last gives {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≥n0, including the smallest.
A step with no base case
Claim.n(n+1)+1 is even for every n≥1.
The step works: (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) is always even, so n(n+1)+1 is always odd. The claim is false for every n. The dominoes are set up well, but nobody pushes the first one.
A pattern that breaks
Put n 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,5 you get 1,2,4,8,16. Surely the next is 32? It is 31.
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+(2n)+(4n), which equals 2n−1 only up to n=5. You met another such pattern in course 1: n2−n+41 is prime for n=1 to 40. A guess needs a proof.
Too few base cases
Claim. Every amount of 1 unit or more can be paid with coins of 3 and 5 units. Proof. True for 3 and 5. If k−2 can be paid, add a 3 to pay k+1.
The step looks back 3 places, so it needs three base cases in a row, and the proof never checks 1, 2 or 4. 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+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=2 gives 0×1=0×2. The step must start from P(k) and end at P(k+1).
A checklist for any induction
Is the base case checked, and is it true?
Does the step use only the hypothesis and known facts?
Does the step work for the smallest k it is used for?
If the step looks back r places, are there r base cases?
Does the step end with 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 2, and it looks for values of n that make n(n+1)+1 even.
Common mistakes
Checking the step only for a large k. The horses fail at k=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). That is assuming the result.
Remember these
A step must work for every k 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.
In the horses proof, the step from 2 horses to 3 horses works. Why?
A student proves "3n+1 is a multiple of 4" with the step 3k+1+1=3(3k+1)−2. What is wrong?
How many regions do 6 points on a circle make?
A proof shows P(k)⇒P(k+1) for every k≥1 and checks P(3). What has it proved?
Why is "assume 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.