4.6 Proof of the master theorem

4.6-1

Let's prove that if b is a positive integer, then $\lceil \lceil \frac{n}{b} \rceil \frac{1}{b} \rceil = \lceil \frac{n}{b^2} \rceil$.

Since $\lceil \frac{n}{b} \rceil \geq \frac{n}{b}$, so $\lceil \frac{n}{b} \rceil \frac{1}{b} \geq \frac{n}{b}\frac{1}{b} = \frac{n}{b^2}$, thus $\lceil \lceil \frac{n}{b} \rceil \frac{1}{b} \rceil \geq \lceil \frac{n}{b^2} \rceil$.

And we have $\frac{n}{b}\frac{1}{b} \leq \lceil\frac{n}{b}\frac{1}{b} \rceil = \lceil\frac{n}{b^2} \rceil$, hence $\frac{n}{b} \leq b\lceil \frac{n}{b^2} \rceil$. Because both b and $\lceil \frac{n}{b^2} \rceil$ are integers, so $b\lceil \frac{n}{b^2} \rceil$ is also a integer. So $\lceil \frac{n}{b} \rceil \leq b\lceil \frac{n}{b^2} \rceil$. So $\lceil \frac{n}{b} \rceil\frac{1}{b} \leq \lceil \frac{n}{b^2} \rceil$, so $\lceil \lceil \frac{n}{b} \rceil\frac{1}{b} \rceil \leq \lceil \frac{n}{b^2} \rceil$.

Thus $\lceil \lceil \frac{n}{b} \rceil\frac{1}{b} \rceil = \lceil \frac{n}{b^2} \rceil$, so $n_j = \lceil \frac{n}{b^{j - 1}} \rceil$ if j > 0. If j = 0, $n_j = n$, so we can get a more simpler expression, $n_j = \lceil \frac{n}{b^j} \rceil$.

You can get some useful lemmas here.

4.6-2

From lemma 4.2 we know $T(n) = \Theta(n^{\log_b{a}}) + \sum_{j = 0}^{\log_b{n - 1}} a^jf(\frac{n}{b^j})$.

$$ \begin{eqnarray} \sum_{j = 0}^{\log_b{n - 1}} a^jf(\frac{n}{b^j}) &=& \sum_{j = 0}^{\log_b{n - 1}} a^jf(\frac{n}{b^j}) \\ &=& \sum_{j = 0}^{\log_b{n - 1}} a^j\Theta((\frac{n}{b^j})^{\log_b{a}}\lg^k{\frac{n}{b^j}}) \\ &=& \sum_{j = 0}^{\log_b{n - 1}} a^j\Theta(\frac{n^{\log_b{a}}}{(b^{\log_b{a}})^j}\lg^k{\frac{n}{b^j}}) \\ &=& \sum_{j = 0}^{\log_b{n - 1}} a^j\Theta(\frac{n^{\log_b{a}}}{a^j}\lg^k{\frac{n}{b^j}}) \\ &=& \sum_{j = 0}^{\log_b{n - 1}}\Theta(n^{\log_b{a}}\lg^k{\frac{n}{b^j}}) \\ &=& n^{\log_b{a}}\sum_{j = 0}^{\log_b{n - 1}}\Theta(\lg^k{\frac{n}{b^j}}) \\ &=& n^{\log_b{a}}\sum_{j = 0}^{\log_b{n - 1}}\Theta((\lg{n} - j\lg{b})^k) \end{eqnarray} $$

We have:

$$ \begin{eqnarray} \sum_{j = 0}^{\log_b{n - 1}}\Theta((\lg{n} - j\lg{b})^k) &\leq& \sum_{j = 0}^{\log_b{n - 1}}\lg^k{n} \\ &=& \log_b{n}\lg^k{n} \\ &=& \frac{\lg^{k + 1}{n}}{\lg{b}} \\ &=& O(\lg^{k + 1}{n}) \end{eqnarray} $$

But I don't know how to prove $\sum_{j = 0}^{\log_b{n - 1}}\Theta((\lg{n} - j\lg{b})^k) = \Omega(\lg^{k + 1}{n})$.

4.6-3

We have $af(\frac{n}{b}) \leq cf(n)$, so $f(n) \geq \frac{a}{c}f(\frac{n}{b})$, and:

$$ \begin{eqnarray} f(n) &\geq& \frac{a}{c}f(\frac{n}{b}) \\ &\geq& (\frac{a}{c})^2f(\frac{n}{b^2}) \\ &\geq& \ldots \\ &\geq& (\frac{a}{c})^{\log_b{n}}f(1) \\ &=& n^{\log_b{\frac{a}{c}}}f(1) \\ &=& n^{\log_b{a + \epsilon}}f(1) \text{ (c < 1)} \\ &=& \Omega(n^{\log_b{a + \epsilon}}) \end{eqnarray} $$

So $f(n) = \Omega(n^{\log_b{a + \epsilon}})$.