Induction proves a statement P(n) for every whole number n from a starting value. You check the base case, then you show that whenever P(k)
Lesson 1 of 3Show all lessonsHide
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.
The first domino falls.
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 n. Here is one:
P(n):1+3+5+⋯+(2n−1)=n2.
For each n we get one statement. P(1) says 1=1. P(2) says 1+3=4. P(3) says 1+3+5=9. We want all of them at once, for every n≥1. There are infinitely many, so checking them one by one can never finish.
The principle of mathematical induction
Let P(n) be a statement for each whole number n≥1. Suppose that:
the base case holds: P(1) is true;
the inductive step holds: for every k≥1, if P(k) is true, then P(k+1) is true.
Then P(n) is true for every whole number n≥1.
The assumption "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) were false. Among the false ones there is a smallest, say P(m). It is not P(1), because the base case holds. So P(m−1) is true, and the step makes 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≥1, 1+3+5+⋯+(2n−1)=n2.
Base case. For n=1 the left side is 1 and the right side is 12=1. So P(1) is true.
Inductive hypothesis. Assume P(k) for some k≥1: 1+3+⋯+(2k−1)=k2.
Inductive step. The next odd number is 2(k+1)−1=2k+1. Add it to both sides:
1+3+⋯+(2k−1)+(2k+1)=k2+2k+1=(k+1)2.
This is exactly P(k+1).
Conclusion.P(1) is true, and P(k) implies P(k+1) for every k≥1. By induction, P(n) is true for every n≥1.
The picture shows the same step. Each new odd number is an L-shaped layer that turns a k×k square into a (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≥1, 1+2+3+⋯+n=2n(n+1).
Base case. For n=1: 1=21×2. True.
Hypothesis. Assume 1+2+⋯+k=2k(k+1).
Step. Add k+1 to both sides. The right side becomes
2k(k+1)+(k+1)=2(k+1)(k+2),
which is the formula with n=k+1.
Conclusion. By induction the formula holds for every n≥1.
A good habit: write down the target 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=1. If P(n0) is true, and P(k) implies P(k+1) for every k≥n0, then P(n) is true for every n≥n0. Course 2 uses this for inequalities that only start to hold at n=5 or later.
How the proof is written in different books
Indian textbooks name the statement P(n) and write the step as "assume P(k), prove 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=k, the step to n=k+1, and a concluding sentence. Always write the conclusion in full.
Some books count the natural numbers from 0, others from 1. Say clearly where your base case is.
Practise with new numbers
Try it in Python
The program checks the odd-number formula for n=1 to 10. Then it tests a famous pattern: n2−n+41 is prime for a long run of n.
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), never P(k+1).
Testing is not proving. The pattern n2−n+41 gives primes for n=1 to 40 and fails at n=41.
No conclusion. End with a sentence that names both steps and says "by induction".
Remember these
Base case P(1), then the step: P(k) true implies P(k+1) true, for every k≥1.
The assumption P(k) is the inductive hypothesis.
Write the target P(k+1) first.
A base case at n0 gives the result for every n≥n0.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
What is the base case of the claim 2+4+6+⋯+2n=n(n+1), and is it true?
In the step of the same claim, what do you add to both sides of P(k)?
A statement P(n) is true for n=5, and P(k) implies P(k+1) for every k≥5. For which n do we know that P(n) is true?
A computer checks a formula for every n from 1 to 1000. Is that a proof for every n?
Write P(k+1) for P(n): 1+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.