# 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(n/2) + n^2 \]

## Solution:

Let us guess that \(T(n) = n^2 lg(n) \). Therefore, our induction hypothesis is that there exists a \(c\) and an \(n_0\) such that \[T(n) \geq cn^2lg(n) \] \(\forall n_0 > n and c > 0 \).

For the

base case(\(n=1\)), we have \(T(1) = 1 > c 1^2lg1 \) . This is true for all \(c>0\).Now for the inductive step, assume the hypothesis is true for \(m<n\), thus: \[T(m) \geq cm^2 lg(m) \] So: \(T(n) = 4T(n/2) + n^2\) \( \geq 4c\frac{n^2}{4}lg\frac{n}{2} + n^2 \) \( = cn^2lg(n) - cn^2lg(2) + n^2 \) \( = cn^2lg(n) + (1-c)n^2\) If we now pick as \(c<1\), then \[T(n) = \Omega(cn^2lg(n) \]

Use the substitution method to show that \[T(n) = 2T(n/2) + n\] is \(O(nlg(n)\)

Solution:We are trying to prove that \(T(n) \leq cnlg(n) \). So we start by assuming that the bound holds for \(n/2\) , thus:\[\begin{align} T(n) &\leq c(n \ 2)lg(n/2) \\ &\leq cnlg(n \ 2) + n \\ &= cnlg(n) - cnlg(2) + n \\ &\leq cnlg(n) \\ \end{align} \]

Since the last step holds for any \(c > 1\), we are done.

## A stronger method

When recurrences describe themselves by making certain discontinuous jumps, it is more rigourous to use strong induction to show that our guess is valid.
Basically, what we do is chose 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(nlog^2(n)) \) \[\large{ T(n) = \begin{cases} 1 \ \ n =1 \\ 2T(\rfloor \frac{n}{2} \lfloor) + nlog(n) \ \ n > 1 \end{cases}} \]

Solution:

Theorem:There is a constant \(c\) such that \(\forall n \geq 2\) \[T(n) \leq cnlog^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 2clog^2(2) \] We now show that \(\forall n > 2\), that \(P(2),P(3),...,P(n-1) \implies P(n) \).

Suppose \(P(1),..,P(n-1)\) holds. \(T(n) = 2T(\rfloor n/2 \lfloor ) + nlog(n) \leq 2c(\rfloor n/2 \lfloor )log^2(\rfloor n/2 \lfloor ) + nlog(n) \) \[\leq 2c(n/2)log^2(n/2) + nlog(n) \] \[=cn(log(n) - 1)^2 + nlog(n) \] \[=cnlog^2(n) - 2cnlog(n) + cn + nlog(n) \] \[\leq cnlog^2(n) - cnlog(n) + cn \ if c \geq 0.5 \] \[\leq cnlog^2(n) \] Therefore \(P(n)\) holds

\(T_{0}=1, T_{1}=3, 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\)

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

Proof. 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 stepAssume \(n ≥ 3\) and \(P(k)\) for all \(k\) such that\( 0 ≤ k ≤ n\).\[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}\]

The difference between regular and strong induction 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(n/2)\)

In an inductive case where you are trying to bound \(T(n)\), you would (by the inductive hypothesis) replace \(T(n/2)\) with \(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(n^3) \)

Solution: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(n^3) \)

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{align} T(n) &= T(n-2) + n^2 \\ &\leq c(n-2)^3 + n^2 \\ &< cn^2(n-2) + n^2 \\ &= n^2 (c(n-2) + 1 ) \\ &\leq n^2(c(n-2) + 2c) \ for c \geq 0.5 \\ &= cn^2 \end{align} \] \(P(n)\) therefore holds

**Cite as:**The substitution method for solving recurrences.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/the-substitution-method-for-solving-recurrences/