Lesson 1: The idea of proof by induction
Prove
SkillsStructure of an induction proofProving sum formulas by induction
Worked example
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 .
Answer
The statement is true for all : holds, and the inductive step shows .
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
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 .