Lesson 1 of 7 · 16 min
The idea of proof by induction
See why checking examples is never enough, and how an initial statement, an assumption and an inductive step together prove a statement for every positive integer.
What you will be able to do
- Explain why checking a statement for many values of does not prove it.
- Name and write the four parts of a proof by induction: initial statement, assumption statement, inductive step and conclusion.
- Explain why a proof by induction needs both the initial statement and the inductive step.
Add up the first few odd numbers and something keeps happening:
Every total is a perfect square. Does it work for the first odd numbers? The first million? You can't check them all, because there are infinitely many positive integers. This lesson shows how to prove it anyway.
Look down the column of running totals. What kind of numbers appear?
If the pattern continues, what is , the sum of the first odd numbers?
History
Patterns can fool you
Euler noticed that is prime for : forty prime values in a row. But at it gives . Forty confirming cases proved nothing. A proof has to cover every case at once.
The initial statement knocks over the first domino. The inductive step guarantees that each falling domino knocks over the next.
Think of a row of dominoes, one for each positive integer. To be sure that every domino falls, you need two facts:
- The first domino falls.
- Whenever a domino falls, it knocks over the next one.
The first fact starts things off. The second passes the fall along the row forever. Neither is enough alone: if nobody pushes the first domino, nothing falls, and if there is a gap somewhere, the fall stops there.
Key idea
The principle of mathematical induction
Let be a statement about the positive integer . If
- is true, and
- for every positive integer , if is true then is true,
then is true for every .
Each odd number is an L-shaped layer. Adding the th odd number, , turns an square into an square.
The picture shows why the odd numbers build squares: the next odd number wraps an L-shape around the square you already have. A proof by induction turns exactly that idea, "if it works for one square, it works for the next", into algebra.
The four parts of a proof by induction
Initial statement
Show that is true by evaluating both sides at .
Assumption statement
Assume that is true for some , and write out what that means.
Inductive step
Prove that is then true. Write down the target and use the assumption to reach it.
Conclusion
State that since is true and , by the principle of mathematical induction is true for all .
Step through each part. The table checks the first few values of , but only the four parts together prove the statement for every .
Worked example
Prove
Prove by mathematical induction that
for all .
Step 1: Define
Let be the statement , for .
Naming the statement lets you refer to , and precisely.
Step 2: Initial statement
When the left-hand side has one term, . The right-hand side is . Both sides equal , so is true.
The last term is . When that is , so the sum is just its first term.
Step 3: Assumption statement
Assume is true for some :
Step 4: Write the target
says
The new last term is .
Knowing exactly where you are heading keeps the inductive step on track.
Step 5: Inductive step
So is true whenever is true.
by the index laws.
Step 6: Conclusion
is true, and true implies true. So by the principle of mathematical induction, for all .
Try it yourself first, then check the working one step at a time.
Answer
The statement is true for all : holds, and the inductive step shows .
Method
Define and check by evaluating both sides.
Assume for some .
Write the target , including the new last term.
Replace the first terms using the assumption, then simplify to the target.
Write the conclusion.
Watch out for
Writing the new term as . The last term of the sum to terms is .
Writing or . In fact .
Put the lines of this proof that for all in order.
Here is why the initial statement matters. Consider the claim
Suppose it is true for . Adding the next term, , gives
which is the claim for . The inductive step works. But at the left side is and the right side is . The first domino never falls, and in fact the claim is false for every : the correct total is .
A student shows that "if is true then is true" for a statement , but never checks any particular value of . What can you conclude?
Common mistake
Assuming the thing you are proving
The assumption is about one particular value: "assume is true for some ". Writing "assume is true for all " assumes the whole result, and the proof collapses. Use a new letter, , for the assumption.
Exam tip
What markers look for
QCAA solutions use the syllabus's four parts. Make each one easy to find: define and its domain, show the initial statement, write the assumption in full, show where the inductive step uses it, and finish with the conclusion sentence. A correct inductive step with no conclusion still loses a mark.
Summary
Checking cases, however many, is evidence, not proof.
Induction proves for all from two facts: is true, and true implies true.
The four parts are the initial statement, the assumption statement, the inductive step and the conclusion.
The inductive step must use the assumption.
Without the initial statement, a statement can pass the inductive step and still be false for every value.
Finished the lesson?
Try the 3 quick checks above and the lesson completes itself, or mark it complete now.