The Central Idea
Suppose \(P(n)\) is a statement indexed by integers \(n\ge n_0\).
Mathematical induction proves
\[ P(n_0),P(n_0+1),P(n_0+2),\ldots \]by establishing two things:
- the first case \(P(n_0)\) is true;
- whenever \(P(k)\) is true, \(P(k+1)\) is also true.
Symbolically,
\[ \boxed{ P(n_0) \quad\text{and}\quad \forall k\ge n_0,\; P(k)\Longrightarrow P(k+1) } \]together imply
\[ \boxed{\forall n\ge n_0,\;P(n).} \]The Domino Picture
A common analogy is a row of dominoes.
The base case knocks over the first domino.
The inductive step proves that whenever one domino falls, the next domino must fall.
Together these facts force every domino in the row to fall.
The analogy is useful, but the mathematics is a chain of logical implications.
The Statement \(P(n)\)
Before beginning an induction proof, identify exactly what proposition is being indexed by \(n\).
For example,
\[ P(n): 1+2+\cdots+n=\frac{n(n+1)}{2}. \]The goal is not merely to manipulate a formula. It is to prove that the proposition \(P(n)\) is true for every required integer \(n\).
The Base Case
The base case verifies the first value covered by the theorem.
If the claim begins at \(n=1\), prove \(P(1)\).
If it begins at \(n=5\), prove \(P(5)\).
The base case anchors the chain. Without it, the inductive implication may be valid but never actually start.
The Inductive Hypothesis
In the inductive step, choose an arbitrary integer \(k\) in the required range and assume
\[ P(k). \]This temporary assumption is called the inductive hypothesis.
It does not assume the entire theorem. It assumes one arbitrary case so that we can prove the implication
\[ P(k)\Longrightarrow P(k+1). \]The Inductive Step
The inductive step begins with the inductive hypothesis \(P(k)\) and derives the next case \(P(k+1)\).
The required logical form is
\[ \boxed{P(k)\Longrightarrow P(k+1).} \]The proof must work for an arbitrary \(k\) in the specified range.
Example: Sum of the First \(n\) Positive Integers
Prove that for every integer \(n\ge1\),
\[ 1+2+\cdots+n=\frac{n(n+1)}{2}. \]Let
\[ P(n): 1+2+\cdots+n=\frac{n(n+1)}{2}. \]Base Case for the Summation Formula
For \(n=1\), the left side is
\[ 1. \]The right side is
\[ \frac{1(1+1)}{2}=1. \]Therefore \(P(1)\) is true.
Inductive Hypothesis for the Summation Formula
Assume \(P(k)\) is true for some arbitrary integer \(k\ge1\):
\[ 1+2+\cdots+k=\frac{k(k+1)}{2}. \]We must prove
\[ P(k+1): 1+2+\cdots+k+(k+1) = \frac{(k+1)(k+2)}{2}. \]Inductive Step for the Summation Formula
Begin with the left side of \(P(k+1)\):
\[ 1+2+\cdots+k+(k+1). \]Use the inductive hypothesis on the first \(k\) terms:
\[ =\frac{k(k+1)}{2}+(k+1). \]Factor \(k+1\):
\[ =(k+1)\left(\frac{k}{2}+1\right). \]Simplify:
\[ =\frac{(k+1)(k+2)}{2}. \]This is exactly the formula required for \(P(k+1)\).
Therefore,
\[ P(k)\Longrightarrow P(k+1). \]By mathematical induction,
\[ \boxed{ 1+2+\cdots+n=\frac{n(n+1)}{2} } \]for every integer \(n\ge1\).
Why the Inductive Hypothesis Is Useful
The expression for the \(k+1\) case often contains the entire \(k\) case plus one new piece.
In the previous example,
\[ 1+2+\cdots+k+(k+1) \]contains
\[ 1+2+\cdots+k, \]which the inductive hypothesis already tells us how to rewrite.
Induction works especially well when the next case grows naturally from the previous one.
Example: Sum of the First \(n\) Odd Numbers
Prove that for \(n\ge1\),
\[ 1+3+5+\cdots+(2n-1)=n^2. \]Define
\[ P(n): 1+3+\cdots+(2n-1)=n^2. \]Base Case
For \(n=1\),
\[ 1=1^2. \]So \(P(1)\) is true.
Inductive Step
Assume
\[ 1+3+\cdots+(2k-1)=k^2. \]The next odd number is
\[ 2(k+1)-1=2k+1. \]Therefore,
\[ 1+3+\cdots+(2k-1)+(2k+1) \] \[ =k^2+2k+1 \] \[ =(k+1)^2. \]Thus \(P(k+1)\) is true.
By induction,
\[ \boxed{1+3+\cdots+(2n-1)=n^2} \]for every integer \(n\ge1\).
Induction with Divisibility
Induction can prove divisibility patterns indexed by \(n\).
The inductive step often rewrites the \(k+1\) expression as
\[ \text{an expression known to be divisible by }d \]plus another term that is also divisible by \(d\).
Example: \(3\mid(4^n-1)\)
Prove that for every integer \(n\ge1\),
\[ 3\mid(4^n-1). \]Let
\[ P(n):3\mid(4^n-1). \]Base Case for the Divisibility Example
For \(n=1\),
\[ 4^1-1=3, \]and \(3\mid3\).
Therefore \(P(1)\) is true.
Inductive Step for the Divisibility Example
Assume
\[ 3\mid(4^k-1). \]Then there exists an integer \(m\) such that
\[ 4^k-1=3m. \]Consider
\[ 4^{k+1}-1. \]Rewrite:
\[ 4^{k+1}-1 = 4\cdot4^k-1. \]Add and subtract \(4\):
\[ =4(4^k-1)+3. \]Use the inductive hypothesis:
\[ =4(3m)+3 \] \[ =3(4m+1). \]Since \(4m+1\) is an integer,
\[ 3\mid(4^{k+1}-1). \]Therefore the result holds for all \(n\ge1\).
Induction with Inequalities
Induction can also prove inequalities.
The main challenge is that the inductive hypothesis gives a comparison, not an exact equality.
Each inequality transformation must preserve the required direction.
Example: \(2^n\ge n+1\)
Prove that for every integer \(n\ge0\),
\[ 2^n\ge n+1. \]Define
\[ P(n):2^n\ge n+1. \]Base Case for the Inequality
For \(n=0\),
\[ 2^0=1 \]and
\[ 0+1=1. \]Therefore \(P(0)\) is true.
Inductive Step for the Inequality
Assume
\[ 2^k\ge k+1. \]Multiply by \(2>0\):
\[ 2^{k+1}\ge2(k+1). \]Since \(k\ge0\),
\[ 2(k+1)=2k+2\ge k+2. \]Therefore,
\[ 2^{k+1}\ge k+2. \]This is exactly \(P(k+1)\).
Hence
\[ \boxed{2^n\ge n+1} \]for all integers \(n\ge0\).
The Starting Index Matters
An induction theorem does not have to begin at \(n=0\) or \(n=1\).
Suppose a claim is true for every \(n\ge4\).
Then the base case is
\[ P(4), \]and the inductive step proves
\[ P(k)\Longrightarrow P(k+1) \]for arbitrary \(k\ge4\).
The induction starts exactly where the theorem starts.
Example with a Later Starting Index
Prove that for every integer \(n\ge4\),
\[ 2^n\ge n^2. \]The base case is
\[ 2^4=16=4^2. \]Assume
\[ 2^k\ge k^2 \]for some \(k\ge4\).
Then
\[ 2^{k+1}=2\cdot2^k\ge2k^2. \]Since \(k\ge4\),
\[ 2k^2-(k+1)^2 = k^2-2k-1 >0. \]Thus
\[ 2k^2\ge(k+1)^2. \]Therefore
\[ 2^{k+1}\ge(k+1)^2. \]By induction,
\[ \boxed{2^n\ge n^2\text{ for all }n\ge4.} \]Induction and Recursive Definitions
Induction is naturally connected to recursively defined objects.
A recursive sequence gives later terms in terms of earlier terms, for example
\[ a_{n+1}=a_n+3. \]If a property of \(a_k\) can be used to prove the same property of \(a_{k+1}\), induction follows the same structure as the recursion itself.
Example: Arithmetic Sequence Formula
Suppose
\[ a_1=5 \]and
\[ a_{n+1}=a_n+3. \]Prove
\[ a_n=3n+2. \]For \(n=1\),
\[ a_1=5=3(1)+2. \]Assume
\[ a_k=3k+2. \]Then
\[ a_{k+1}=a_k+3 \] \[ =(3k+2)+3 \] \[ =3k+5 \] \[ =3(k+1)+2. \]Therefore \(a_{k+1}\) has the required form, so
\[ \boxed{a_n=3n+2} \]for all \(n\ge1\).
Induction with Products
Product identities may also be proved inductively.
The \(k+1\) case often adds one new factor:
\[ a_1a_2\cdots a_k a_{k+1}. \]The inductive hypothesis replaces the first \(k\) factors with a known expression, after which the final factor is incorporated.
Example: A Factorial Identity
Prove for \(n\ge1\),
\[ 1\cdot2\cdot3\cdots n=n!. \]This identity is essentially the recursive definition of factorial, but it illustrates the product structure.
For \(n=1\),
\[ 1=1!. \]Assume
\[ 1\cdot2\cdots k=k!. \]Then
\[ 1\cdot2\cdots k(k+1) = k!(k+1) = (k+1)!. \]Thus the identity holds for every \(n\ge1\).
What the Inductive Hypothesis Does Not Mean
Assuming \(P(k)\) in the inductive step does not assume what we are trying to prove in a circular way.
We are proving the conditional statement
\[ P(k)\Longrightarrow P(k+1). \]Conditional proofs are allowed to assume their hypothesis temporarily.
The base case then supplies the first actual instance from which the chain begins.
Why the Base Case Cannot Be Omitted
Suppose someone proves
\[ P(k)\Longrightarrow P(k+1) \]for every \(k\), but never proves any \(P(k)\) is actually true.
Then the implication could be vacuously true while every statement in the sequence is false.
The base case gives the chain its first true statement.
A Classic False Induction Pattern
Consider the false claim:
\[ P(n):n>100 \]for every positive integer \(n\).
If \(k>100\), then certainly
\[ k+1>100. \]So the implication
\[ P(k)\Longrightarrow P(k+1) \]is valid.
But the base case
\[ P(1) \]is false.
Therefore induction cannot begin.
The Inductive Step Must Use an Arbitrary \(k\)
Checking
\[ P(5)\Longrightarrow P(6) \]proves only one link.
Induction requires a proof that
\[ P(k)\Longrightarrow P(k+1) \]for every arbitrary \(k\) in the relevant range.
The symbol \(k\) represents a general stage, not a specially chosen one.
The Goal in the Inductive Step
After assuming \(P(k)\), write down \(P(k+1)\) explicitly.
This helps prevent a common mistake: proving something related to the next case without proving the exact required statement.
For a formula
\[ P(n):S_n=f(n), \]the inductive goal is
\[ S_{k+1}=f(k+1). \]Use the Hypothesis, Do Not Merely Restate It
A complete inductive step must actually use
\[ P(k). \]If the proof of \(P(k+1)\) never depends on the inductive hypothesis, then the argument may simply be a direct proof.
That is not necessarily wrong, but it means induction was unnecessary.
Induction Is Not Repeated Verification
Showing
\[ P(1),P(2),P(3),P(4) \]does not prove \(P(n)\) for all \(n\).
No matter how many individual cases are checked, infinitely many remain.
Induction replaces repeated verification with a general propagation rule.
Common Error: Proving \(P(k)\) Instead of \(P(k+1)\)
In the inductive step, \(P(k)\) is assumed.
Re-deriving \(P(k)\) accomplishes nothing.
The required target is
\[ \boxed{P(k+1).} \]Common Error: Assuming \(P(k+1)\)
If the goal is to prove
\[ P(k)\Longrightarrow P(k+1), \]we may assume \(P(k)\), but we may not assume \(P(k+1)\).
Doing so would assume the very conclusion the inductive step is supposed to establish.
Common Error: Starting at the Wrong Base Case
If a theorem states
\[ P(n)\text{ for all }n\ge3, \]then verifying \(P(1)\) is irrelevant.
The base case must correspond to the first value in the theorem:
\[ \boxed{P(3).} \]Common Error: Changing the Domain Midproof
If the theorem concerns integers \(n\ge1\), then the induction variable should remain in that domain.
A proof should not suddenly rely on \(k\) being real, negative, or having some property not provided by the theorem.
The inductive step must work under exactly the stated conditions.
Common Error: Algebra That Does Not Reach the Target
Suppose the inductive goal is
\[ \frac{(k+1)(k+2)}{2}. \]Ending with
\[ \frac{k^2+3k+2}{2} \]is mathematically equivalent, but the proof should make the connection explicit:
\[ \frac{k^2+3k+2}{2} = \frac{(k+1)(k+2)}{2}. \]Match the final form to the statement being proved.
Common Error: Proving Only the First Few Cases
A student may write
\[ P(1),P(2),P(3) \]are true and conclude that the pattern continues.
This is evidence, not induction.
A valid induction proof needs a general implication from \(P(k)\) to \(P(k+1)\).
Common Error: Forgetting the Final Conclusion
After completing the base case and inductive step, state the result:
Therefore, by mathematical induction, \(P(n)\) holds for every integer \(n\ge n_0\).
This closes the logical structure of the proof.
Common Error: Hidden Dependence on Earlier Cases
Ordinary induction assumes only \(P(k)\) when proving \(P(k+1)\).
If the argument needs
\[ P(k),P(k-1),P(k-2), \]then ordinary induction may not be the cleanest formulation.
The next lesson, Strong Induction, allows the inductive step to assume all earlier cases up through \(k\).
Induction and Recursive Algorithms
The same reasoning pattern appears in computer science.
If an algorithm processes inputs of size \(n\) by reducing them to inputs of size \(n-1\), a correctness proof may:
- verify the smallest input;
- assume correctness for size \(k\);
- prove correctness for size \(k+1\).
This structural parallel is one reason induction is central to discrete mathematics.
Induction and Loop Reasoning
Iterative processes also produce induction-like arguments.
A loop may maintain a property after each iteration.
Proving that the property holds initially and is preserved from one iteration to the next mirrors:
\[ \text{base case} \]plus
\[ \text{inductive step}. \]This connection leads naturally to loop invariants and algorithm correctness.
A Reliable Procedure for Mathematical Induction
- State the proposition \(P(n)\) clearly.
- Identify the first value \(n_0\).
- Verify the base case \(P(n_0)\).
- Let \(k\ge n_0\) be arbitrary.
- Assume \(P(k)\) as the inductive hypothesis.
- Write the exact statement \(P(k+1)\) that must be proved.
- Transform the \(k+1\) case using the inductive hypothesis.
- Justify every algebraic, divisibility, or inequality step.
- Show that the final form is exactly \(P(k+1)\).
- Conclude that \(P(n)\) holds for all \(n\ge n_0\).
Example: Full Induction Workflow
Prove that for every integer \(n\ge1\),
\[ 1+2+4+\cdots+2^{n-1}=2^n-1. \]Step 1: Define the proposition.
\[ P(n): 1+2+4+\cdots+2^{n-1}=2^n-1. \]Step 2: Base case.
For \(n=1\),
\[ 1=2^1-1=1. \]So \(P(1)\) is true.
Step 3: Inductive hypothesis.
Assume
\[ 1+2+4+\cdots+2^{k-1}=2^k-1. \]Step 4: Prove the next case.
The \(k+1\) case is
\[ 1+2+\cdots+2^{k-1}+2^k. \]Use the inductive hypothesis:
\[ =(2^k-1)+2^k \] \[ =2^{k+1}-1. \]This is exactly \(P(k+1)\).
Step 5: Conclude.
Therefore, by mathematical induction,
\[ \boxed{1+2+4+\cdots+2^{n-1}=2^n-1} \]for every integer \(n\ge1\).
Practice 1: Arithmetic Sum
Prove by induction:
\[ 1+2+\cdots+n=\frac{n(n+1)}{2}. \]Practice 2: Odd Numbers
Prove by induction:
\[ 1+3+5+\cdots+(2n-1)=n^2. \]Practice 3: Powers of Two
Prove by induction for \(n\ge1\):
\[ 1+2+4+\cdots+2^{n-1}=2^n-1. \]Practice 4: Divisibility
Prove by induction that for every integer \(n\ge1\),
\[ 5\mid(6^n-1). \]Practice 5: Inequality
Prove by induction that for every integer \(n\ge0\),
\[ 3^n\ge n+1. \]Practice 6: Starting at \(n=4\)
Prove by induction:
\[ 2^n\ge n^2 \]for every integer \(n\ge4\).
Practice 7: Recursive Sequence
Let
\[ a_1=2,\qquad a_{n+1}=a_n+4. \]Prove by induction that
\[ a_n=4n-2. \]Practice 8: Identify the Missing Step
A student verifies \(P(1)\), assumes \(P(k)\), and then immediately writes “therefore \(P(k+1)\).”
What is missing?
Practice 9: Identify the Error
A theorem claims \(P(n)\) for all integers \(n\ge5\), but the student uses \(P(1)\) as the base case.
Explain the error.
Practice 10: Ordinary or Strong Induction?
Suppose proving \(P(k+1)\) requires assuming all of
\[ P(1),P(2),\ldots,P(k). \]Which induction method is the more natural choice?
Practice Answers
Practice 1
Base case:
\[ 1=\frac{1(2)}{2}. \]Assume
\[ 1+2+\cdots+k=\frac{k(k+1)}{2}. \]Then
\[ 1+2+\cdots+k+(k+1) \] \[ =\frac{k(k+1)}{2}+(k+1) \] \[ =\frac{(k+1)(k+2)}{2}. \]Therefore the formula holds for all \(n\ge1\).
Practice 2
Base case:
\[ 1=1^2. \]Assume
\[ 1+3+\cdots+(2k-1)=k^2. \]Add the next odd number \(2k+1\):
\[ k^2+2k+1=(k+1)^2. \]Hence the identity holds for every \(n\ge1\).
Practice 3
Base case:
\[ 1=2^1-1. \]Assume
\[ 1+2+\cdots+2^{k-1}=2^k-1. \]Then
\[ 1+2+\cdots+2^{k-1}+2^k \] \[ =(2^k-1)+2^k \] \[ =2^{k+1}-1. \]Practice 4
Base case:
\[ 6^1-1=5. \]Assume
\[ 6^k-1=5m \]for some integer \(m\). Then
\[ 6^{k+1}-1 = 6(6^k)-1 \] \[ = 6(6^k-1)+5 \] \[ = 6(5m)+5 \] \[ = 5(6m+1). \]Therefore \(5\mid(6^{k+1}-1)\).
Practice 5
For \(n=0\),
\[ 3^0=1=0+1. \]Assume
\[ 3^k\ge k+1. \]Then
\[ 3^{k+1}=3\cdot3^k\ge3(k+1). \]Since \(k\ge0\),
\[ 3(k+1)\ge k+2. \]Therefore
\[ 3^{k+1}\ge k+2. \]Practice 6
Base case:
\[ 2^4=16=4^2. \]Assume \(2^k\ge k^2\) for \(k\ge4\). Then
\[ 2^{k+1}\ge2k^2. \]Also,
\[ 2k^2-(k+1)^2=k^2-2k-1>0 \]for \(k\ge4\). Hence
\[ 2^{k+1}\ge(k+1)^2. \]Practice 7
For \(n=1\),
\[ a_1=2=4(1)-2. \]Assume
\[ a_k=4k-2. \]Then
\[ a_{k+1}=a_k+4 \] \[ =4k-2+4 \] \[ =4k+2 \] \[ =4(k+1)-2. \]Therefore \(a_n=4n-2\) for all \(n\ge1\).
Practice 8
The student has not proved the inductive implication.
They must use the assumption \(P(k)\) to derive the exact statement \(P(k+1)\).
Practice 9
The theorem begins at \(n=5\), so the base case must be
\[ \boxed{P(5).} \]Verifying \(P(1)\) does not establish the first case covered by the theorem.
Practice 10
Strong induction is the more natural formulation because the proof of the next case depends on all earlier cases, not only on \(P(k)\).
What to Remember
Mathematical induction proves an infinite sequence of statements using a starting point and a propagation rule:
\[ \boxed{ P(n_0) \quad\text{and}\quad P(k)\Longrightarrow P(k+1) } \]imply
\[ \boxed{\forall n\ge n_0,\;P(n).} \]- state \(P(n)\) clearly;
- verify the correct base case;
- let \(k\) be arbitrary in the required range;
- assume \(P(k)\) only as the inductive hypothesis;
- prove the exact next statement \(P(k+1)\);
- use the hypothesis rather than merely repeating it;
- match the final algebra to the target form;
- close by invoking mathematical induction.
The central strategic question is: How does the \(k+1\) case contain or depend on the structure already established in the \(k\) case?
Where We Go Next
Ordinary induction assumes one previous case while proving the next. Some recursive arguments need access to several earlier cases at once.
The next lesson, Strong Induction, expands the inductive hypothesis to assume all required cases through \(k\) before proving \(P(k+1)\).