Math101 · Independent Ontario learning library
Math101learn.math101.caMathematical Induction
A complete guide to weak induction, its logical structure, variants, and common proof gaps.
Precise definition
The principle of mathematical induction states: if $P(n_0)$ is true and, for every integer $k\ge n_0$, $P(k)\Rightarrow P(k+1)$, then $P(n)$ is true for all integers $n\ge n_0$. The base case anchors the chain; the inductive step proves every link.
Notation and mathematical language
In the inductive step, $P(k)$ is the inductive hypothesis, assumed for an arbitrary $k\ge n_0$ only to prove $P(k+1)$. Strong induction may assume $P(n_0),\ldots,P(k)$ to prove the next case. It is equivalent in power to ordinary induction but often fits recurrences and factorization arguments better.
Conceptual picture
Imagine an infinite row of dominoes beginning at $n_0$. The base case knocks down the first; the inductive implication ensures that whenever an arbitrary domino falls, the next falls. Checking many early dominoes without proving the link does not reach the infinite tail.
Conditions and key results
The statement must be indexed over integers with a clear starting value. Algebra in the inductive step must use the hypothesis rather than merely re-prove $P(k)$. If a recurrence depends on two earlier terms, supply enough base cases and use strong induction or an appropriately strengthened hypothesis.
A reliable strategy
- Write the exact predicate $P(n)$ and the integer range it claims.
- Verify the initial case $P(n_0)$ directly.
- Assume $P(k)$ for an arbitrary $k\ge n_0$, clearly labelling the inductive hypothesis.
- Derive $P(k+1)$, then invoke induction to state the universal conclusion.
Fully worked example
Interpretation and application
Induction verifies loop invariants, recursive algorithms, divisibility patterns, inequalities, and formulas for finite structures. It establishes exact claims, not empirical trends. A computer check of the first million cases can support debugging but cannot replace the inductive link.
Common mistakes
Verification and reasonableness
- Check the formula at the base and next case to catch indexing errors.
- Mark the exact line where the inductive hypothesis is used.
- After the algebra, compare the result with the literal form of $P(k+1)$, including limits and subscripts.
Practice
- What base case is needed for a claim for all $n\ge0$?
- Using $1+\cdots+k=k(k+1)/2$, find $1+\cdots+(k+1)$.
- When is strong induction convenient?
Answers and brief solutions
- $P(0)$.
- $k(k+1)/2+(k+1)=(k+1)(k+2)/2$.
- When the next case naturally depends on several or any earlier cases, such as recursive sequences or prime factorization.
Further deduction
Sometimes the original claim is too weak to make the inductive step work. The remedy is to strengthen the predicate while retaining the desired statement as a consequence. For example, proving a recursive algorithm correct may require a hypothesis about both its returned value and a preserved data invariant. Stronger induction is not circular if the stronger base case and step are established. This planning move explains why a failed induction attempt can reveal missing structure rather than a false theorem.
Related topics
Try it yourself
Hints are part of learning. Open one whenever it makes the next step feel possible.
If $1+\cdots+k=k(k+1)/2$, what is $1+\cdots+k+(k+1)$ after simplification?
- $k(k+1)/2+(k+1)=(k+1)(k/2+1)$.
- This equals $(k+1)(k+2)/2$.
End of lesson
Nice work making it this far.
Understanding grows through return visits. Save this lesson, try the practice, or continue when you are ready.
