The substitution method for solving recurrences is famously described using two steps:
- Guess the form of the solution.
- Use induction to show that the guess is valid.
This method is especially powerful when we encounter recurrences that are non-trivial and unreadable via the master theorem. We can use the substitution method to establish both upper and lower bounds on recurrences.
The name comes from the substitution of the guessed answer for the function when the inductive hypothesis is applied to smaller values. This method is powerful but it is only applicable to instances where the solutions can be guessed.
Determine a tight asymptotic lower bound for the following recurrence:
Let us guess that . Then our induction hypothesis is that there exists a and an such that
For the base case we have This is true for all .
Now, for the inductive step, assume the hypothesis is true for Then
If we now pick as , then
Use the substitution method to show that
We are trying to prove that . So we start by assuming that the bound holds for
Since the last step holds for any , we are done.
When recurrences describe themselves by making certain discontinuous jumps, it is more rigorous to use strong induction to show that our guess is valid. Basically, what we do is to choose a predicate
Then, , holds.
Note that is effectively a base case since there are no preceding cases.
Use strong induction to show that
Theorem: There is a constant such that
Inductive hypothesis: Let be the claim in the theorem for a particular and .
For any , we show that .
Note that holds if , because
We now show that , .
Suppose holds. Then
Given and let
for . Show by induction that for all
The proof is by strong induction with hypothesis .
Inductive Step: Assume and for all such that. Then
The difference between regular and strong inductions is slight. In regular induction, each case depends on the one that immediately precedes it. In strong induction, each case depends (perhaps) on one or more preceding cases, but not necessarily the preceding one. The “perhaps” part holds for cases that are, in effect, base cases.
There’s one kind of error that’s easy to make in inductive proofs: using different choices of when considering different choices of . Suppose is and suppose the recurrence for somehow involves
In an inductive case where you are trying to bound , you would (by the inductive hypothesis) replace with at the right moment, and you would end up showing that The constants must be the same, or else the proof is meaningless.
Here is one more example to solidify this reasoning:
We have to show that for all ,
holds for a sufficiently large . This implies that
Base Cases and Both hold if is larger than and .
Inductive Case: For , we show that .
Assume that holds. Then