4.6 Proof of the master theorem

4.6-1 $\star$

Give a simple and exact expression for $n_j$ in equation $\text{(4.27)}$ for the case in which $b$ is a positive integer instead of an arbitrary real number.

We state that $\forall{j \ge 0}, n_j = \left \lceil \frac{n}{b^j} \right \rceil$.

Indeed, for $j = 0$ we have from the recurrence's base case that $n_0 = n = \left \lceil \frac{n}{b^0} \right \rceil$.
Now, suppose $n_{j - 1} = \left \lceil \frac{n}{b^{j - 1}} \right \rceil$ for some $j > 0$. By definition, $n_j = \left \lceil \frac{n_{j - 1}}{b} \right \rceil$.
It follows from the induction hypothesis that $n_j = \left \lceil \frac{\left \lceil \frac{n}{b^{j - 1}} \right \rceil}{b} \right \rceil$.
Since $b$ is a positive integer, equation $\text{(3.4)}$ implies that $\left \lceil \frac{\left \lceil \frac{n}{b^{j - 1}} \right \rceil}{b} \right \rceil = \left \lceil \frac{n}{b^j} \right \rceil$.
Therefore, $n_j = \left \lceil \frac{n}{b^j} \right \rceil$.

P.S. $n_j$ is obtained by shifting the base $b$ representation $j$ positions to the right, and adding $1$ if any of the $j$ least significant positions are non-zero.

4.6-2 $\star$

Show that if $f(n) = \Theta(n^{\log_b a}\lg^k{n})$, where $k \ge 0$, then the master recurrence has solution $T(n) = \Theta(n^{\log_b a}\lg^{k + 1}n)$. For simplicity, confine your analysis to exact powers of $b$.

$$ \begin{aligned} g(n) & = \sum_{j = 0}^{\log_b n - 1} a^j f(n / b^j) \\ f(n / b^j) & = \Theta\Big((n / b^j)^{\log_b a} \lg^k(n / b^j) \Big) \\ g(n) & = \Theta\Big(\sum_{j = 0}^{\log_b n - 1}a^j\big(\frac{n}{b^j}\big)^{\log_b a}\lg^k\big(\frac{n}{b^j}\big)\Big) \\ & = \Theta(A) \\ A & = \sum_{j = 0}^{\log_b n - 1} a^j \big(\frac{n}{b^j}\big)^{\log_b a}\lg^k\frac{n}{b^j} \\ & = n^{\log_b a} \sum_{j = 0}^{\log_b n - 1}\Big(\frac{a}{b^{\log_b a}}\Big)^j\lg^k\frac{n}{b^j} \\ & = n^{\log_b a}\sum_{j = 0}^{\log_b n - 1}\lg^k\frac{n}{b^j} \\ & = n^{\log_b a} B \\ \lg^k\frac{n}{d} & = (\lg n - \lg d)^k = \lg^k{n} + o(\lg^k{n}) \\ B & = \sum_{j = 0}^{\log_b n - 1}\lg^k\frac{n}{b^j} \\ & = \sum_{j = 0}^{\log_b n - 1}\Big(\lg^k{n} - o(\lg^k{n})\Big) \\ & = \log_b n\lg^k{n} + \log_b n \cdot o(\lg^k{n}) \\ & = \Theta(\log_b n\lg^k{n}) \\ & = \Theta(\lg^{k + 1}{n}) \\ g(n) & = \Theta(A) \\ & = \Theta(n^{\log_b a}B) \\ & = \Theta(n^{\log_b a}\lg^{k + 1}{n}). \end{aligned} $$

4.6-3 $\star$

Show that case 3 of the master method is overstated, in the sense that the regularity condition $af(n / b) \le cf(n)$ for some constant $c < 1$ implies that there exists a constant $\epsilon > 0$ such that $f(n) = \Omega(n^{\log_b a + \epsilon})$.

$$ \begin{aligned} af(n / b) & \le cf(n) \\ \Rightarrow f(n / b) & \le \frac{c}{a} f(n) \\ \Rightarrow f(n) & \le \frac{c}{a} f(bn) \\ & = \frac{c}{a} \left(\frac{c}{a} f(b^2n)\right) \\ & = \frac{c}{a} \left(\frac{c}{a}\left(\frac{c}{a} f(b^3n)\right)\right) \\ & = \left(\frac{c}{a}\right)^i f(b^i n) \\ \Rightarrow f(b^i n) & \ge \left(\frac{a}{c}\right)^i f(n). \end{aligned} $$

Let $n = 1$, then we have

$$f(b^i) \ge \left(\frac{a}{c}\right)^i f(1) \quad (*).$$

Let $b^i = n \Rightarrow i = \log_b n$, then substitue back to equation $(*)$,

$$ \begin{aligned} f(n) & \ge \left(\frac{a}{c}\right)^{\log_b n} f(1) \\ & \ge n^{\log_b \frac{a}{c}} f(1) \\ & \ge n^{\log_b a + \epsilon} & \text{ where $\epsilon > 0$ because $\frac{a}{c} > a$ (recall that $c < 1$)} \\ & = \Omega(n^{\log_b a + \epsilon}). \end{aligned} $$