The Substitution Method for Solving Recurrences

The substitution method for solving recurrences is famously described using two steps:

1. Guess the form of the solution.
2. 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:

$$T(n) = 4T\left(\frac{n}2\right) + n^2.$$

---

Let us guess that $T(n) = n^2 \lg(n)$. Then our induction hypothesis is that there exists a $c$ and an $n_0$ such that

$$T(n) \geq cn^2\lg(n) \ \forall n > n_0 \ \text{ and } \ c > 0.$$

For the base case $(n=1),$ we have $T(1) = 1 > c 1^2\lg1.$ This is true for all $c>0$.

Now, for the inductive step, assume the hypothesis is true for $m<n.$ Then

$$T(m) \geq cm^2 \lg(m).$$

So,

$$\begin{aligned} T(n) &= 4T\left(\frac n2\right) + n^2\\ &\geq 4c\frac{n^2}{4}\lg\frac{n}{2} + n^2 \\ &= cn^2\lg(n) - cn^2\lg(2) + n^2 \\ &= cn^2\lg(n) + (1-c)n^2. \end{aligned}$$

If we now pick as $c<1$, then

$$T(n) = \Omega\big(cn^2\lg(n)\big).\ _\square$$

Use the substitution method to show that

$$T(n) = 2T\left(\frac n2\right) + n$$

is $O\big(n\lg(n)\big).$

---

We are trying to prove that $T(n) \leq cn\lg(n)$. So we start by assuming that the bound holds for $\frac n2:$

$$\begin{aligned} T(n) &\leq c\left(\frac n2\right)\lg\left(\frac n2\right) \\ &\leq cn\lg\left(\frac n2\right) + n \\ &= cn\lg(n) - cn\lg(2) + n \\ &\leq cn\lg(n). \end{aligned}$$

Since the last step holds for any $c > 1$, we are done. $_\square$

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 $P.$

Suppose $\forall n \geq b$

$$P(b), P(b+1), ..., P(n-1) \implies P(n).$$

Then, $\forall n \geq b$, $P(n)$ holds.

Note that $P(b)$ is effectively a base case since there are no preceding cases.

Use strong induction to show that $T(n) = O\big(n\log^2(n)\big):$

$$T(n) = \begin{cases} \begin{aligned} 1 \qquad & n =1 \\ 2T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + n\log(n) \qquad & n > 1. \end{aligned} \end{cases}$$

---

Theorem: There is a constant $c$ such that $\forall n \geq 2,\ T(n) \leq cn\log^2(n).$

Inductive hypothesis: Let $P(n)$ be the claim in the theorem for a particular $c$ and $n$.

For any $n$, we show that $P(2),P(3),...,P(n-1) \implies P(n)$.

Note that $P(2)$ holds if $c \geq 2$, because

$$T(2) = 2T(1) + 2 = 4 \leq 2c\log^2(2).$$

We now show that $\forall n > 2$, $P(2),P(3),...,P(n-1) \implies P(n)$.

Suppose $P(1),..,P(n-1)$ holds. Then

$$\begin{aligned} T(n) = 2T \left( \left\lfloor \frac n2 \right\rfloor \right) + n\log(n) &\leq 2c \left( \left\lfloor \frac n2 \right\rfloor \right) \log^2 \left( \left\lfloor \frac n2 \right\rfloor \right) + n\log(n) \\ &\leq 2c \left( \frac n2 \right) \log^2 \left( \frac n2 \right) + n\log(n) \\ &=cn \big( \log(n) - 1 \big)^2 + n\log(n) \\ &=cn \log^2(n) - 2cn \log(n) + cn + n\log(n) \\ &\leq cn \log^2(n) - cn \log(n) + cn &&(\text{if } c \geq 0.5) \\ &\leq cn \log^2(n). \end{aligned}$$

Therefore, $P(n)$ holds. $_\square$

Given $T_{0}=1, T_{1}=3,$ and $T_{2}=9,$ let

$$T_{n} = T_{n-1} + 3T_{n-2} + 3T_{n-3}$$

for $n\geq3$. Show by induction that $T_{n}\leq 3^{n}$ for all $n\geq0.$

---

The proof is by strong induction with hypothesis $P(n) = T_{n} ≤ 3^{n}$.

Base Cases

• $n=0: T_{0}=1=3^{0}$
• $n=1: T_{1}=3\leq 3^{1}$
• $n=2: T_{1}=9\leq 3^{2}.$

Inductive Step: Assume $n ≥ 3$ and $P(k)$ for all $k$ such that$0 ≤ k ≤ n$. Then

$$\begin{aligned} T_{n} = T_{n-1} + 3T_{n-2} + 3T_{n-3} &≤ 3^{n-1} + (3)3^{n-2} + (3)3^{n-3} \\ &= 3^{n-2}(3 + 3 + 1)\\ &= (7)3^{n-2}\\ &< (9)3^{n-2}\\ &=3^{n}.\ _\square \end{aligned}$$

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 $c$ when considering different choices of $n$. Suppose $P(n)$ is $(T(n) \leq cn),$ and suppose the recurrence for $T(n)$ somehow involves $T\left(\frac n2\right).$

In an inductive case where you are trying to bound $T(n)$, you would (by the inductive hypothesis) replace $T\left(\frac n2\right)$ with $\frac{cn}2$ at the right moment, and you would end up showing that $T(n) \leq cn.$ The constants must be the same, or else the proof is meaningless.

Here is one more example to solidify this reasoning:

$$T(n) = T(n-2) + n^2$$

Show that $T(n) = O\big(n^3\big).$

---

We have to show that for all $n \geq 1$,

$$P(n) : T(n) \leq cn^2$$

holds for a sufficiently large $c$. This implies that $T(n) = O\big(n^3\big).$

Base Cases $(n=1$ and $n=2):$ Both hold if $c$ is larger than $T(1)$ and $T(2)$.

Inductive Case: For $n>2$, we show that $P(n-2) \implies P(n)$.

Assume that $P(n-2)$ holds. Then

$$\begin{aligned} T(n) &= T(n-2) + n^2 \\ &\leq c(n-2)^3 + n^2 \\ &< cn^2(n-2) + n^2 \\ &= n^2 \big(c(n-2) + 1\big) \\ &\leq n^2\big(c(n-2) + 2c\big) \ \text{ for } c \geq 0.5 \\ &= cn^2. \end{aligned}$$

$P(n)$ therefore holds. $_\square$