Recently I've been following the chapter on asymptotics in Concrete Mathematics. The subject matter of it is relatively new to me though and I'm having some difficulties dealing with asymptotic quantities, as I'm still trying to sort out the fundamentals.
What follows are a few sample exercises from the aforementioned book and my attempts at solving them:
9.2 Which function grows faster:
- $n^{\ln n}$ or $(\ln n)^n$
- $n^{\ln \ln \ln n}$ or $(\ln n)!$
- $(n!)!$ or $((n-1)!)!(n-1)!^{n!}$
- $F^2_{\lceil H_n \rceil}$ or $H_{F_n}$ (here $F_n$ denotes the $n$th element of the Fibonacci sequence, while $H_n$ is the $n$th harmonic number)
In order to formally justify that either function is little-$o$ of the other one, I'd show that their quotient converges to $0$ as $n$ approaches $\infty$. This has let me prove that $n^{\ln n} = e^{(\ln n)^2} \prec e^{n \ln c} $ $\prec e^{n \ln\ln n} $ $= (\ln n)^n$. I don't know how to approach the other pairs of functions though. Those involving the Pi function (I don't have any experience in dealing with it) or sequences don't seem to be as straightforward as the first example.
9.13 Evaluate $(n + 2 + O(n^{-1}))^n$ with relative error $O(n^{-1})$.
Ok, so I'm working towards expressing the formula in the form $f(n)(1 + O(n^{-1}))$.
\begin{equation} \begin{split} (n + 2 + O(n^{-1})) &= (n(1 + 2n^{-1} + O(n^{-2})))^n = n^n(1 + 2n^{-1} + O(n^{-2}))^n \\ &= n^n \exp(n(\ln(1 + 2n^{-1} + O(n^{-2}))) \\ &= n^n \exp(n(2n^{-1} + O(n^{-2}))) \hspace{12pt} \text{// by the $ln(1+z)$ approx.}\\ &= n^n \exp(2 + O(n^{-1}))) = n^n e^2 e^{O(n^{-1})} \\ &= n^n e^2 (1 + O(n^{-1})) \hspace{12pt} \text{// by the $e^x$ approx.} \end{split} \end{equation}
Are all these transformations legal and correct? From what I know, we can apply an asymptotic expansion (as in $\ln(1 + z)$ in this case) when $z \rightarrow 0$ as $n \rightarrow \infty$. Am I right in concluding, that an approximated expression with the absolute error that doesn't converge to $0$ cannot be expanded this way (e.g. $ln(1 + n^{-1} + O(n))$)?
9.14 Prove that $(n + a)^{n + b} = n^{n + b}e^{a}(1 + a(b - \dfrac{a}{2})n^{-1} + O(n^{-2}))$.
I transform the LHS so as to make it easier to compare with what we have on the RHS.
\begin{equation} \begin{split} (n+a)^{n+b} &= (n(1 + \dfrac{a}{n}))^{n+b} = n^{n+b}(1 + \dfrac{a}{n})^{n+b} = n^{n+b} \exp((n+b) \ln(1 + \dfrac{a}{n})) \\ &= n^{n+b}exp((n+b)(\dfrac{a}{n} - \dfrac{a^2}{2n^2} + O((n^{-3}))) \hspace{12pt} \text{// by the $ln(1+z)$ approx.} \\ &= n^{n+b} \exp(a - \dfrac{a^2}{2n} + O(n^{-2}) + \dfrac{ab}{n} - \dfrac{a^2b}{2n^2} + O(n^{-3})) \\ &= n^{n+b} e^a \exp(\dfrac{-a^2}{2n} + \dfrac{ab}{n} - \dfrac{a^2b}{2n^2} + O(n^{-2}))\\ &= \ldots \end{split} \end{equation}
(First I'd like to make sure that the step from the 3rd to the 4th line is formally correct - is it enough to say that $O(n^{-3}) \subset O(n^{-2})$)? Anyway, I don't really know how to move from here. One attempt would be to use the $e^z$ expansion, but the result doesn't look very nice. Or I have made a mistake I can't yet see.
It looks like I've written a pretty long post. :) I know some of my questions may sound trivial (or there may be some basic mistakes above), but I'm trying to make head and tail of that whole asymptotics and need a little assistance :)