3.2 Standard notations and common functions

3.2-1

If f(n) and g(n) are monotonically increasing functions, then if $m \leq n$, we have $f(m) \leq f(n)$ and $g(m) \leq g(n)$. So we get $f(m) + g(m) \leq f(n) + g(n)$ when $m \leq n$. So the function f(n) + g(n) is monotonically increasing.

Let $m_1 = g(m)$ and $n_1 = g(n)$. Because $m_1 \leq n_1$, so $f(m_1) \leq f(n_1)$, so f(g(n)) is monotonically increasing.

if f(n) and g(n) are nonnegative, because $f(m) \leq f(n)$ and $g(m) \leq g(n)$, so we can multiply the inequations and have $f(m) \cdot g(m) \leq f(n) \cdot g(n)$. Thus $f(n) \cdot g(n)$ is monotonically increasing.

3.2-2

$a^{\log_bc} = a^{\frac{\log_ac}{\log_ab}} = (a^{\log_ac})^\frac{1}{\log_ab} = c^\frac{1}{\log_ab} = c^{\log_ba}$.

3.2-3

According to Stirling's approximation, we have:

$$\sqrt{2\pi}n^{n + \frac{1}{2}}e^{-n} \leq n! \leq en^{n + \frac{1}{2}}e^{-n}$$

So:

$$\lg{(\sqrt{2\pi}n^{n + \frac{1}{2}}e^{-n})} \leq \lg{(n!)} \leq \lg{(en^{n + \frac{1}{2}}e^{-n})}$$

Notice that:

$$ \begin{eqnarray} \lg{(\sqrt{2\pi}n^{n + \frac{1}{2}}e^{-n})} &=& \lg{(\sqrt{2\pi})} + \lg{n^{n + \frac{1}{2}}} + \lg{e^{-n}} \\ &=& \lg{(\sqrt{2\pi})} + (n + \frac{1}{2})\lg{n} - n\lg{e} \\ &=& n(\lg{n} - \lg{e}) + \lg{(\sqrt{2\pi})} + \frac{1}{2}\lg{n} \\ &\geq& n(\lg{n} - \lg{\sqrt{n}}) + \lg{(\sqrt{2\pi})} + \frac{1}{2}\lg{n} \text{ (when } n \geq e^2 \text{)} \\ &=& n\lg{\frac{n}{\sqrt{n}}} + \lg{(\sqrt{2\pi})} + \frac{1}{2}\lg{n} \\ &=& \frac{1}{2}n\lg{n} + \lg{(\sqrt{2\pi})} + \frac{1}{2}\lg{n} \\ &\geq& \frac{1}{2}n\lg{n} \end{eqnarray} $$

And:

$$ \begin{eqnarray} \lg{(en^{n + \frac{1}{2}}e^{-n})} &=& \lg{e} + \lg{n^{n + \frac{1}{2}}} + \lg{e^{-n}} \\ &=& \lg{e} + (n + \frac{1}{2})\lg{n} + \lg{e^{-n}} \\ &=& n\lg{n} + \lg{e} + \frac{1}{2}\lg{n} + \lg{e^{-n}} \\ &=& n\lg{n} + \lg{\frac{e\sqrt{n}}{e^n}} \\ &\leq& n\lg{n} + \lg{1} \text{ (when } n \geq 1 \text{)} \\ &=& n\lg{n} \end{eqnarray} $$

So now we get:

$$\frac{1}{2}n\lg{n} \leq \lg{(n!)} \leq n\lg{n} \text{ (when } n \geq e^2 \text{)}$$

which means: there exist positive constants $c_1 = \frac{1}{2}$, $c_2 = 1$ and $n_0 = 8$ such that:

$$0 \leq c_1n\lg{n} \leq \lg(n!) \leq c_2n\lg{n},\ for \ all \ n \geq n_0$$

So $\lg{(n!)} = \Theta(n\lg{n})$.

When $n \geq 4$, we have:

$$ \begin{eqnarray} n! &=& n * (n - 1) * \ldots * 4 * 3 * 2 * 1 \\ &=& n * (n - 1) * \ldots * 2 * 2 * 3 * 2 * 1 \\ &>& 2 * 2 * \ldots * 2 * 2 * 3 * 2 * 1 \\ &=& 2^n * 1 \\ &=& 2^n \end{eqnarray} $$

So for any positive constant $c_1$, there exist positive constant $n_1 = 4$, such that $0 \leq c_1(2^n) < n! \ for\ all\ n \geq n_1$.

So $n! = w(2^n)$.

When $n \geq 2$, we have:

$$ \begin{eqnarray} n! &=& n * (n - 1) * \ldots * 2 * 1 \\ &<& n * n * \ldots * n * n \\ &=& n^n \end{eqnarray} $$

So for any positive constant $c_2$, there exist positive constant $n_2 = 2$, such that $0 \leq n! < c_2n^n \ for\ all\ n \geq n_2$.

So $n! = o(n^n)$.

3.2-4

Suppose $\lceil \lg{n} \rceil!$ is polynomially bounded, then there exist positive constants c, k and $n_0$ such that $0 \leq \lceil \lg{n} \rceil! \leq cn^k$ for all $n \geq n_0$. So $\lg{(\lceil \lg{n} \rceil!)} \leq \lg{(cn^k)}$.

But:

$$ \begin{eqnarray} \lg{(\lceil \lg{n} \rceil!)} - \lg{(cn^k)} &\geq& \lg{((\lg{n})!)} - \lg{(cn^k)} \\ &\geq& \frac{1}{2}\lg{n} * \lg{(\lg{n})} - \lg{(cn^k)} \text{ (reuse the inequation in 3.2-3)} \\ &=& \frac{1}{2}\lg{n} * \lg{(\lg{n})} - \lg{c} - k\lg{n} \\ &=& \lg{n}(\frac{1}{2}\lg{(\lg{n})} - k) - \lg{c} \end{eqnarray} $$

Since both k and c are constants and $\lg{n}$ is a monotonically increasing function, so $\lg{n}(\frac{1}{2}\lg{(\lg{n})} - k) - \lg{c}$ is monotonically increasing. First we let $(\frac{1}{2}\lg{(\lg{n})} - k) \geq 1$ and we get $n \geq 2^{2^{2k + 2}}$. So $\lg{n}(\frac{1}{2}\lg{(\lg{n})} - k) - \lg{c} \geq \lg{n} - \lg{c}$ when $n \geq 2^{2^{2k + 2}}$. Then let $\lg{n} - \lg{c} \geq 0$ and we get $n \geq c$. So we find a $n_0 = max(2^{2^{2k + 2}}, c)$ such that $\lg{(\lceil \lg{n} \rceil!)} - \lg{(cn^k)} \geq 0 \text{ for all } n \geq n_0$.

So we know that the hypothesis is not correct, thus $\lceil \lg{n} \rceil!$ is not polynomially bounded.

Now let's prove that $\lceil \lg{\lg{n}} \rceil!$ is polynomially bounded.

$$ \begin{eqnarray} \lg{(\lceil \lg{\lg{n}} \rceil!)} - \lg{(cn^k)} &\leq& \lceil \lg{\lg{n}} \rceil\lg{(\lceil \lg{\lg{n}} \rceil)} - \lg{(cn^k)} \text{ (reuse the inequation in 3.2-3)} \\ &=& \lceil \lg{\lg{n}} \rceil\lg{(\lceil \lg{\lg{n}} \rceil)} - \lg{c} - k\lg{n} \\ &<& (\lg{\lg{n}} + 1)\lg{(\lg{\lg{n}} + 1)} - \lg{c} - k\lg{n} \\ \end{eqnarray} $$

Let $\lg{n} = x, x > 0$, so $(\lg{\lg{n}} + 1)\lg{(\lg{\lg{n}} + 1)} - \lg{c} - k\lg{n} = (\lg{x} + 1)\lg{(\lg{x} + 1)} - \lg{c} - kx = f(x)$.

So $f'(x) = \frac{\lg{(\lg{x} + 1)} + 1}{x} - k$.

Let $g(x) = \frac{\lg{(\lg{x} + 1)} + 1}{x}$, so $g'(x) = \frac{\frac{1}{\lg{x} + 1} - (\lg{(\lg{x} + 1)} + 1)}{x^2}$. It's easy to see that g'(x) is a monotonically decreasing function and g'(1) = 0, so $g(x) \leq 0 \text{ on } [1, +\infty)$. So g(x) is monotonically decreasing on $[1, +\infty)$ and g(1) = 1.

So $f'(x) \leq 1 - k \text{ on } [1, +\infty)$. And for some constants k, $f'(x) \leq 0$. Thus f(x) is also a monotonically decreasing function on $[1, +\infty)$ for some constants k. And $f(1) = -\lg{c} - k < 0$, so f(x) < 0 on $[1, +\infty)$.

So there exist positive constants c, k and $n_0 = 2$ such that $\lg{(\lceil \lg{\lg{n}} \rceil!)} - \lg{(cn^k)} < f(x) < 0 \text{ for all } n \geq n_0$. So $\lceil \lg{\lg{n}} \rceil! \leq cn^k$. So $\lceil \lg{\lg{n}} \rceil!$ is polynomially bounded.

3.2-5

Here is the definition of $\lg^*{n}$. So $\lg{(\lg^*{n})} = \lg{(1 + \lg^*{(\lg{n})})}$. Let $\lg^*{(\lg{n})} = x$, so it's obvious $f(x) = \lg{(1 + x)}$ grows slower than $g(x) = x$, so $\lg^*{(\lg{n})}$ is asymptotically larger.

3.2-6

$$ \begin{eqnarray} \phi^2 - \phi - 1 &=& (\frac{1 + \sqrt{5}}{2})^2 - \frac{1 + \sqrt{5}}{2} - 1 \\ &=& \frac{1 + 2\sqrt{5} + 5}{4} - \frac{2 + 2\sqrt{5}}{4} - \frac{4}{4} \\ &=& \frac{6 + 2\sqrt{5} - 2 - 2\sqrt{5} - 4}{4} \\ &=& 0 \end{eqnarray} $$

$$ \begin{eqnarray} \hat\phi^2 - \hat\phi - 1 &=& (\frac{1 - \sqrt{5}}{2})^2 - \frac{1 - \sqrt{5}}{2} - 1 \\ &=& \frac{1 - 2\sqrt{5} + 5}{4} - \frac{2 - 2\sqrt{5}}{4} - \frac{4}{4} \\ &=& \frac{6 - 2\sqrt{5} - 2 + 2\sqrt{5} - 4}{4} \\ &=& 0 \end{eqnarray} $$

So the golden ratio $\phi$ and its conjugate $\hat\phi$ both satisfy the equation $x^2 = x + 1$.

3.2-7

Basis: let's show that the statement holds for i = 1 and i = 2.

$\frac{\phi - \hat\phi}{\sqrt{5}} = \frac{\frac{1 + \sqrt{5}}{2} - \frac{1 - \sqrt{5}}{2}}{\sqrt{5}} = \frac{\frac{1 + \sqrt{5} - 1 + \sqrt{5}}{2}}{\sqrt{5}} = \frac{\frac{2\sqrt{5}}{2}}{\sqrt{5}} = 1 = F_1$

$\frac{\phi^2 - \hat\phi^2}{\sqrt{5}} = \frac{(\frac{1 + \sqrt{5}}{2})^2 - (\frac{1 - \sqrt{5}}{2})^2}{\sqrt{5}} = \frac{\frac{1 + 2\sqrt{5} + 5 - 1 + 2\sqrt{5} - 5}{4}}{\sqrt{5}} = \frac{\frac{4\sqrt{5}}{4}}{\sqrt{5}} = 1 = F_2$

Inductive step: if $F_i = \frac{\phi^i - \hat\phi^i}{\sqrt{5}}$ holds, let's show $F_{i + 1} = \frac{\phi^{i + 1} - \hat\phi^{i + 1}}{\sqrt{5}}$ holds.

$$ \begin{eqnarray} F_{i + 1} &=& F_i + F_{i - 1} \\ &=& \frac{\phi^i - \hat\phi^i}{\sqrt{5}} + \frac{\phi^{i - 1} - \hat\phi^{i - 1}}{\sqrt{5}} \\ &=& \frac{\phi^{i - 1}(\phi + 1) - \hat\phi^{i - 1}(\hat\phi + 1)}{\sqrt{5}} \\ &=& \frac{\phi^{i - 1}\phi^2 - \hat\phi^{i - 1}\hat\phi^2}{\sqrt{5}} \text{( reuse the equation in 3.2-7)} \\ &=& \frac{\phi^{i + 1} - \hat\phi^{i + 1}}{\sqrt{5}} \end{eqnarray} $$

So $F_i = \frac{\phi^i - \hat\phi^i}{\sqrt{5}}$ holds for all i.

3.2-8

According to the symmetry property, if $k\ln{k} = \Theta(n)$, then $n = \Theta(k\ln{k})$. So there exist positive constants $c_1$, $c_2$ and $n_0$ such that:

$$0 \leq c_1k\ln{k} \leq n \leq c_2k\ln{k} \text{, for all } n \geq n_0 \text{ (1)}$$

So:

$$0 \leq \ln{(c_1k\ln{k})} \leq \ln{n} \leq \ln{(c_2k\ln{k})}$$

$$0 \leq \ln{c_1} + \ln{k} + \ln{(\ln{k})} \leq \ln{n} \leq \ln{c_2} + \ln{k} + \ln{(\ln{k})} \text{ (2)}$$

Let's divide equation 1 by equation 2, so we get:

$$0 \leq \frac{c_1k\ln{k}}{\ln{c_1} + \ln{k} + \ln{(\ln{k})}} \leq \frac{n}{\ln{n}} \leq \frac{c_2k\ln{k}}{\ln{c_2} + \ln{k} + \ln{(\ln{k})}}$$

Because:

$$\frac{n}{\ln{n}} \geq \frac{c_1k\ln{k}}{\ln{c_1} + \ln{k} + \ln{(\ln{k})}} \geq \frac{c_1k\ln{k}}{\ln{k} + \ln{k} + \ln{k}} = \frac{c_1}{3}k$$

$$\frac{n}{\ln{n}} \leq \frac{c_2k\ln{k}}{\ln{c_2} + \ln{k} + \ln{(\ln{k})}} \leq \frac{c_2k\ln{k}}{\ln{k}} = c_2k$$

So we have $\frac{c_1}{3}k \leq \frac{n}{\ln{n}} \leq c_2k$.

So there exist positive constants $c_3 = \frac{c_1}{3}$, $c_4 = c_2$ and $n_1 = n_0$ such that:

$$c_3k \leq \frac{n}{\ln{n}} \leq c_4k \text{ for all } n \geq n_1$$

So $\frac{n}{\ln{n}} = \Theta(k)$, which also means $k = \Theta(\frac{n}{\ln{n}})$.