The Central Idea
Ordinary induction proves
\[ P(k)\Longrightarrow P(k+1). \]Strong induction instead allows the inductive step to assume
\[ P(n_0),P(n_0+1),\ldots,P(k) \]simultaneously.
The strong inductive step has the form
\[ \boxed{ \bigl(P(n_0)\land P(n_0+1)\land\cdots\land P(k)\bigr) \Longrightarrow P(k+1). } \]If the required initial case or cases are established, this proves
\[ \boxed{\forall n\ge n_0,\;P(n).} \]Why Strong Induction Is Useful
Some problems do not naturally depend only on the immediately preceding case.
To prove \(P(k+1)\), we might need:
- \(P(k-1)\);
- \(P(k-2)\);
- several earlier cases together;
- a case \(P(m)\) where \(m\) depends on how \(k+1\) is decomposed.
Strong induction provides access to the entire established history.
Ordinary and Strong Induction Prove the Same Kind of Statements
Strong induction is not logically stronger than ordinary mathematical induction.
Both methods can ultimately establish statements of the form
\[ \forall n\ge n_0,\;P(n). \]The difference is in the form of the inductive hypothesis.
Strong induction is often more convenient when the next case depends on more than one earlier case.
The Strong Inductive Hypothesis
Suppose we want to prove \(P(n)\) for all \(n\ge n_0\).
In the inductive step, let \(k\ge n_0\) be arbitrary and assume:
\[ P(n_0),P(n_0+1),\ldots,P(k) \]are all true.
This collection of assumptions is the strong inductive hypothesis.
We then prove \(P(k+1)\).
The Basic Procedure
- State the proposition \(P(n)\).
- Identify the first required value \(n_0\).
- Prove the necessary base case or base cases.
- Let \(k\) be arbitrary in the required range.
- Assume every case from \(P(n_0)\) through \(P(k)\).
- Use whichever earlier case or cases are needed.
- Prove \(P(k+1)\).
- Conclude the result by strong induction.
A First Example: Every Integer Greater Than 1 Has a Prime Factor
Prove:
\[ \text{Every integer }n>1\text{ has a prime factor.} \]Define
\[ P(n): n\text{ has a prime factor}. \]Base Case
The first integer greater than \(1\) is \(2\).
Since \(2\) is prime, it is itself a prime factor of \(2\).
Therefore \(P(2)\) is true.
Strong Inductive Step
Assume that every integer
\[ 2,3,\ldots,k \]has a prime factor.
Consider \(k+1\).
If \(k+1\) is prime, then it is its own prime factor.
If \(k+1\) is composite, then
\[ k+1=ab \]for integers \(a,b\) satisfying
\[ 2\le a\le k. \]By the strong inductive hypothesis, \(a\) has a prime factor \(p\).
Since
\[ p\mid a \]and
\[ a\mid(k+1), \]we have
\[ p\mid(k+1). \]Therefore \(k+1\) has a prime factor.
By strong induction,
\[ \boxed{\text{every integer greater than }1\text{ has a prime factor}.} \]Why Strong Induction Fits the Prime-Factor Argument
If \(k+1\) is composite, the factor \(a\) need not equal \(k\).
It could be any smaller integer satisfying
\[ 2\le a\le k. \]Ordinary induction would give us only \(P(k)\).
Strong induction gives access to \(P(a)\) regardless of which smaller factor appears.
Prime Factorization
A deeper version of the previous argument proves that every integer \(n>1\) can be written as a product of primes.
Define
\[ P(n): n\text{ can be expressed as a product of one or more primes}. \]Example: Every Integer Greater Than 1 Is a Product of Primes
Base case:
\[ 2 \]is prime, so \(P(2)\) holds.
Assume \(P(2),P(3),\ldots,P(k)\).
Consider \(k+1\).
If \(k+1\) is prime, it is already a product consisting of one prime.
If \(k+1\) is composite, then
\[ k+1=ab \]with
\[ 2\le a,b\le k. \]By the strong inductive hypothesis, both \(a\) and \(b\) can be written as products of primes.
Multiplying those prime factorizations gives a prime factorization of \(k+1\).
Therefore,
\[ \boxed{\text{every integer greater than }1\text{ is a product of primes}.} \]More Than One Base Case May Be Needed
Some recurrence relations depend on several previous terms.
If proving \(P(k+1)\) requires both
\[ P(k) \]and
\[ P(k-1), \]then the proof may need two base cases before the recurring pattern can begin.
Example: A Two-Step Recurrence
Suppose a sequence is defined by
\[ a_1=1,\qquad a_2=3, \]and
\[ a_n=a_{n-1}+2a_{n-2} \]for \(n\ge3\).
To prove a property of every \(a_n\), the inductive step may require both the \(n-1\) and \(n-2\) cases.
Therefore the proof must establish enough initial cases to support the recurrence.
Base Cases Must Cover the Recurrence
If the inductive step for \(P(k+1)\) depends on
\[ P(k) \quad\text{and}\quad P(k-1), \]then proving only \(P(1)\) may not be sufficient.
Usually we establish
\[ P(1) \quad\text{and}\quad P(2) \]before beginning the general step.
Example: Fibonacci Numbers Are Positive
Let
\[ F_1=1,\qquad F_2=1, \]and
\[ F_n=F_{n-1}+F_{n-2} \]for \(n\ge3\).
We will prove
\[ F_n>0 \]for all \(n\ge1\).
Base Cases for the Fibonacci Example
We have
\[ F_1=1>0 \]and
\[ F_2=1>0. \]Thus \(P(1)\) and \(P(2)\) are true.
Inductive Step for the Fibonacci Example
Assume
\[ F_j>0 \]for every integer \(j\) with
\[ 1\le j\le k. \]For \(k\ge2\),
\[ F_{k+1}=F_k+F_{k-1}. \]By the strong inductive hypothesis,
\[ F_k>0 \]and
\[ F_{k-1}>0. \]Therefore,
\[ F_{k+1}>0. \]Hence all Fibonacci numbers in this sequence are positive.
Strong Induction with Representation Problems
Strong induction is particularly useful when a number is represented by reducing it to a smaller number and then adding a fixed piece.
Typical problems ask whether every sufficiently large integer can be represented using:
- specified coin denominations;
- specified summands;
- tiles or blocks of fixed sizes;
- combinations of allowed moves.
Example: Representation by 4s and 5s
We claim that every integer \(n\ge12\) can be written in the form
\[ n=4a+5b \]for some nonnegative integers \(a,b\).
Let \(P(n)\) be that statement.
Base Cases for the Representation Example
We verify four consecutive values:
\[ 12=4+4+4, \] \[ 13=4+4+5, \] \[ 14=4+5+5, \] \[ 15=5+5+5. \]Thus \(P(12),P(13),P(14),P(15)\) are true.
Inductive Step for the Representation Example
Assume every integer from \(12\) through \(k\) can be written as
\[ 4a+5b \]with \(a,b\ge0\), where \(k\ge15\).
Consider
\[ k+1. \]Since \(k\ge15\),
\[ k-3\ge12. \]By the strong inductive hypothesis,
\[ k-3=4a+5b \]for some nonnegative integers \(a,b\).
Add \(4\):
\[ k+1=(k-3)+4. \]Therefore,
\[ k+1=4(a+1)+5b. \]Hence \(P(k+1)\) holds.
By strong induction,
\[ \boxed{n=4a+5b\text{ for every integer }n\ge12} \]with suitable nonnegative integers \(a,b\).
Why Several Consecutive Base Cases Were Needed
The inductive step reduces \(k+1\) by \(4\):
\[ k+1\longrightarrow k-3. \]To make this mechanism work immediately, enough consecutive starting values must already be established.
In general, if an inductive step moves backward by as many as \(r\) places, several initial cases may be needed to bridge the beginning of the proof.
Example: Every Integer \(n\ge8\) Is a Sum of 3s and 5s
We claim that every integer \(n\ge8\) has the form
\[ n=3a+5b \]for nonnegative integers \(a,b\).
Verify:
\[ 8=3+5, \] \[ 9=3+3+3, \] \[ 10=5+5. \]Assume every integer from \(8\) through \(k\) has the required form, where \(k\ge10\).
Then
\[ k-2\ge8. \]By the hypothesis,
\[ k-2=3a+5b. \]Add \(3\):
\[ k+1=3(a+1)+5b. \]Therefore the representation exists for every \(n\ge8\).
Strong Induction with Factorization
Factorization arguments often reduce a composite integer to smaller factors.
Those factors may have many possible sizes.
Strong induction is therefore natural because it makes the theorem available for every smaller factor, not only for the immediately preceding integer.
Example: Composite Numbers Have Prime Divisors at Most Their Square Root
If \(n>1\) is composite, then
\[ n=ab \]with
\[ 1would imply
\[ ab>n, \]contradicting \(ab=n\).
The smaller factor has a prime divisor, and that prime divisor is also at most \(\sqrt n\).
This type of reasoning combines factor structure with results about smaller integers.
Strong Induction and Recursive Algorithms
Recursive algorithms may solve an input of size \(n\) by calling themselves on one or more smaller inputs whose sizes are not always \(n-1\).
A correctness proof may therefore assume correctness for every smaller input:
\[ 1,2,\ldots,k \]and prove correctness for input size \(k+1\).
This is exactly the structure of strong induction.
Example: Recursive Factorization Algorithm
Imagine an algorithm that factors an integer \(n>1\).
If \(n\) is prime, it returns \(n\).
If \(n\) is composite, it finds
\[ n=ab \]with
\[ 1To prove correctness for \(n\), we need correctness for arbitrary smaller values \(a\) and \(b\), not merely for \(n-1\).
Strong induction matches that dependency perfectly.
Strong Induction and Shortest Constructions
Some proofs analyze a minimal or shortest construction.
Removing one component may leave an object of any smaller size.
If the proof then needs a theorem about that smaller object, strong induction makes all earlier sizes available.
Strong Induction Can Still Use Only One Earlier Case
The strong inductive hypothesis provides
\[ P(n_0),\ldots,P(k), \]but a particular proof may use only one of them.
That is allowed.
Strong induction gives permission to use all earlier cases; it does not require every one of them to appear explicitly.
Ordinary Induction Can Simulate Strong Induction
To see why strong induction is not fundamentally stronger, define
\[ Q(n): P(n_0)\land P(n_0+1)\land\cdots\land P(n). \]Ordinary induction can prove \(Q(n)\).
But proving \(Q(n)\) means proving that all cases through \(n\) hold.
Thus ordinary induction can package the accumulated history into a single statement.
Strong Induction Can Simulate Ordinary Induction
If a proof of \(P(k+1)\) needs only \(P(k)\), then the strong inductive hypothesis still contains \(P(k)\).
Therefore any ordinary induction proof can also be presented as a strong induction proof.
The practical choice depends on which formulation makes the dependency structure clearer.
Choosing between Ordinary and Strong Induction
Use ordinary induction when the next case naturally grows from the immediately preceding case:
\[ P(k)\Longrightarrow P(k+1). \]Strong induction is often cleaner when the next case may depend on:
- an arbitrary smaller case;
- two or more earlier cases;
- a factorization into smaller components;
- a recurrence using multiple previous terms;
- a decomposition whose size varies from case to case.
Common Error: Using an Unproved Earlier Case
The strong inductive hypothesis covers only cases in its stated range.
If the hypothesis assumes
\[ P(2),P(3),\ldots,P(k), \]then the proof may not invoke \(P(1)\) unless it has been established separately.
Every referenced case must actually belong to the established range.
Common Error: Forgetting Multiple Base Cases
Suppose the inductive step needs
\[ P(k) \quad\text{and}\quad P(k-1). \]At the beginning of the proof, both of those positions must eventually be available.
A single base case may leave the first inductive step without enough prior information.
Common Error: Assuming \(P(k+1)\)
Strong induction expands the hypothesis backward, not forward.
We may assume
\[ P(n_0),\ldots,P(k), \]but not
\[ P(k+1). \]The next case remains the conclusion that must be proved.
Common Error: Assuming All Natural Numbers
The phrase “assume all previous cases” does not mean assume the theorem for every natural number.
It means assume only the finite block
\[ P(n_0),P(n_0+1),\ldots,P(k) \]while proving \(P(k+1)\).
The proof remains noncircular because no future case is assumed.
Common Error: Failing to Show the Smaller Index Is in Range
Suppose the proof of \(P(k+1)\) invokes \(P(k-3)\).
We must verify that
\[ n_0\le k-3\le k. \]Otherwise \(P(k-3)\) may not be covered by the strong inductive hypothesis.
Range checks are a crucial part of strong induction proofs.
Common Error: Using Circular Factorization
In a factorization proof for \(k+1\), the smaller factors must actually be smaller than \(k+1\).
Writing
\[ k+1=1(k+1) \]does not help because it reintroduces the same number.
A useful composite factorization requires
\[ 1Common Error: Treating Strong Induction as a Different Conclusion Rule
Strong induction still proves one next case:
\[ P(k+1). \]The difference lies only in how much earlier information may be assumed.
The conclusion of the inductive step is not a whole block of new cases at once unless the proof is deliberately structured that way.
Common Error: Using Strong Induction When Direct Proof Is Simpler
A proof method should expose structure rather than add machinery.
If a statement follows immediately from a definition or algebraic identity, induction may be unnecessary.
Strong induction is most valuable when smaller cases genuinely support the next case.
A Reliable Procedure for Strong Induction
- State \(P(n)\) precisely.
- Identify the starting index \(n_0\).
- Determine how many initial cases are needed.
- Verify those base cases.
- Let \(k\) be arbitrary beyond the established base range.
- Assume \(P(j)\) for every \(j\) satisfying \(n_0\le j\le k\).
- Analyze the structure of \(k+1\).
- Select whichever earlier case or cases the structure requires.
- Verify that every selected index lies within the hypothesis range.
- Derive \(P(k+1)\).
- Conclude the theorem by strong induction.
Example: Full Strong-Induction Workflow
Prove that every integer \(n\ge2\) is either prime or can be written as a product of primes.
Step 1: Define the proposition.
\[ P(n): n\text{ is prime or a product of primes}. \]Step 2: Base case.
\(2\) is prime, so \(P(2)\) is true.
Step 3: Strong inductive hypothesis.
Assume
\[ P(2),P(3),\ldots,P(k) \]for some \(k\ge2\).
Step 4: Consider \(k+1\).
If \(k+1\) is prime, \(P(k+1)\) holds immediately.
Otherwise \(k+1\) is composite, so
\[ k+1=ab \]with
\[ 2\le a,b\le k. \]Step 5: Use earlier cases.
By the strong inductive hypothesis, each of \(a\) and \(b\) is prime or a product of primes.
Thus their product
\[ ab=k+1 \]is a product of primes.
Step 6: Conclude.
Therefore \(P(k+1)\) holds. By strong induction,
\[ \boxed{\text{every integer }n\ge2\text{ is prime or a product of primes}.} \]Practice 1: Prime Factor
Prove by strong induction that every integer \(n>1\) has a prime factor.
Practice 2: Product of Primes
Prove by strong induction that every integer \(n>1\) can be written as a product of primes.
Practice 3: Representation by 3s and 5s
Prove by strong induction that every integer \(n\ge8\) can be written as
\[ n=3a+5b \]for nonnegative integers \(a,b\).
Practice 4: Representation by 4s and 5s
Prove by strong induction that every integer \(n\ge12\) can be written as
\[ n=4a+5b \]for nonnegative integers \(a,b\).
Practice 5: Fibonacci Positivity
Let
\[ F_1=1,\qquad F_2=1,\qquad F_n=F_{n-1}+F_{n-2}. \]Prove that \(F_n>0\) for every \(n\ge1\).
Practice 6: Multiple Base Cases
Suppose proving \(P(k+1)\) requires both \(P(k)\) and \(P(k-2)\).
Explain why several starting cases may be required.
Practice 7: Range Check
A proof begins at \(n_0=5\) and, while proving \(P(k+1)\), tries to use \(P(k-4)\).
What condition on \(k\) guarantees that this case is available?
Practice 8: Ordinary or Strong Induction?
A recurrence satisfies
\[ a_{n+1}=2a_n+1. \]If proving a property of \(a_{n+1}\) uses only the property of \(a_n\), which induction method is the more natural choice?
Practice 9: Ordinary or Strong Induction?
To prove a statement about a composite integer \(n\), the argument factors \(n=ab\) and needs the theorem for both \(a\) and \(b\).
Which method is the more natural choice?
Practice 10: Identify the Error
A student says:
“Assume \(P(1),P(2),P(3),\ldots\) are all true. Then \(P(k+1)\) is true.”
Explain why this is not a valid strong-induction hypothesis.
Practice Answers
Practice 1
Base case: \(2\) is prime, so it has a prime factor.
Assume every integer from \(2\) through \(k\) has a prime factor. Consider \(k+1\).
If \(k+1\) is prime, it is its own prime factor. If it is composite, write
\[ k+1=ab \]with \(2\le a\le k\). By the strong inductive hypothesis, \(a\) has a prime factor \(p\). Then
\[ p\mid a \quad\text{and}\quad a\mid(k+1), \]so \(p\mid(k+1)\).
Practice 2
Base case: \(2\) is prime.
Assume every integer from \(2\) through \(k\) is prime or a product of primes. If \(k+1\) is prime, we are done. Otherwise
\[ k+1=ab \]with \(2\le a,b\le k\). By the hypothesis, \(a\) and \(b\) are each prime or products of primes. Therefore \(ab=k+1\) is a product of primes.
Practice 3
Verify
\[ 8=3+5,\qquad 9=3+3+3,\qquad 10=5+5. \]Assume all values from \(8\) through \(k\) have the required form, where \(k\ge10\). Since
\[ k-2\ge8, \]write
\[ k-2=3a+5b. \]Then
\[ k+1=3(a+1)+5b. \]Practice 4
Verify
\[ 12=4+4+4, \] \[ 13=4+4+5, \] \[ 14=4+5+5, \] \[ 15=5+5+5. \]Assume all values from \(12\) through \(k\) have the required form, where \(k\ge15\). Since
\[ k-3\ge12, \]write
\[ k-3=4a+5b. \]Then
\[ k+1=4(a+1)+5b. \]Practice 5
Base cases:
\[ F_1=1>0,\qquad F_2=1>0. \]Assume \(F_j>0\) for all \(1\le j\le k\), where \(k\ge2\). Then
\[ F_{k+1}=F_k+F_{k-1}>0. \]Therefore every \(F_n\) is positive.
Practice 6
The first inductive step must have both required earlier cases available. If the recurrence looks back two positions, one base case may not supply enough history. The proof should establish enough consecutive initial cases to support the first general step.
Practice 7
We need
\[ k-4\ge5. \]Therefore,
\[ \boxed{k\ge9}. \]Practice 8
Ordinary induction is the more natural choice because the next case depends only on the immediately preceding case.
Practice 9
Strong induction is the more natural choice because the factors \(a\) and \(b\) may be arbitrary smaller integers rather than \(n-1\).
Practice 10
The student has assumed the theorem for every future case, including the case being proved.
A valid strong inductive hypothesis assumes only a finite block of already prior cases:
\[ \boxed{P(n_0),P(n_0+1),\ldots,P(k).} \]The proof must then establish \(P(k+1)\).
What to Remember
Strong induction replaces the single-case hypothesis
\[ P(k) \]with the accumulated hypothesis
\[ \boxed{P(n_0),P(n_0+1),\ldots,P(k).} \]- use strong induction when the next case may depend on arbitrary smaller cases;
- establish enough base cases to support the recurrence or backward step;
- verify that every earlier case you invoke lies inside the hypothesis range;
- do not assume future cases;
- use factorization and decomposition to reduce the next case to smaller cases;
- remember that ordinary and strong induction are logically equivalent proof principles;
- choose the formulation that best matches the dependency structure of the problem.
The central strategic question is: When I break the \(k+1\) case into smaller pieces, which earlier cases do I need to know are already true?
Where We Go Next
Ordinary and strong induction move through statements indexed by integers. Some mathematical objects are built recursively from smaller objects rather than merely numbered in a sequence.
The next lesson, Structural Induction, adapts inductive reasoning to recursively defined structures such as expressions, strings, trees, and other discrete objects.