A couple of asymptotics exercises 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 :)
 A: 9.13: Right.  The point is that $\ln(1 + z + o(z)) = z + o(z)$ is a statement that is true as $z \to 0$, not as $z \to \infty$.  Similarly for any  function $f$ that is differentiable at $a$, $f(a+z+o(z)) = f(a) + f'(a) z + o(z)$ as $z \to 0$.
9.14: You're fine up to $$ n^{n+b} \exp(a(1 - \dfrac{a}{2n} + \dfrac{b}{n} - \dfrac{ab}{2n^2} + O(n^{-2})))$$
except that you can absorb the $-ab/(2n^2)$ in the $O(n^{-2})$.  Then that becomes
$$ \eqalign{n^{n+b}& e^a \exp\left(\frac{ab-a^2/2}{n} + O(n^{-2})\right)\cr
&= n^{n+b} e^a\left(1 + \frac{ab-a^2/2}{n} + O(n^{-2})\right)}$$
A: In exercise 9.2, you have the right idea on the first part.  
For the second part, consider the logs of both sides. The log of the left-hand side is $\log \log \log n \log n$.  A crude but useful lower bound for the factorial is $z! > z^{z/2}$. (See p. 112 of GKP.)  Therefore $\log z! > (z/2) \log z$.  Similar tricks should work for the third entry.  (Stirling's approximation would be useful but is probably overkill.)
For the fourth entry, it helps to know that $H_n \approx \log n$ and $F_n \approx \phi^n$.
A: For the third part of 9.2, we can use the bounds $n \log n - n < \log n! < n \log n$, which amount to a weak form of Stirling's formula.  (Alternatively we could write (n/e)^n < n! < n^n$.)
We want to show that for large enough $n$, we have 
$$(n!)! > ((n-1)!)! (n-1)!^{n!}$$.
Taking logs, we want to show that
$$ \log (n!)! > \log ((n-1)!)! + n! \log (n-1)!. $$
Call this equation (1).  The left-hand side of (1) satisfies
$$ \log (n!)! > n! \log n! - n! $$
and the right-hand side of (1) satisfies
$$ \log ((n-1)!)! + n! \log (n-1)! < (n-1)! \log (n-1)! + n! \log (n-1)! = (n+1) \cdot (n-1)! \log (n-1)!.$$
Putting this all together, it suffices to show that
$$ n! \log n! - n! > (n+1) \cdots (n-1)! \log (n-1)! $$
for large enough $n$.  But after some rearrangement (which I leave to you) this is equivalent to showing that
$$ n \log n - n > \log (n-1)! $$
for large enough $n$.  Exponentiating both sides, it suffices to show that $(n/e)^n > (n-1)!$ for large enough $n$, or alternatively that $n(n/e)^n > n!$ for large enough $n$.  Now recall ``Stirling's inequality'' $n! < e \sqrt{n} (n/e)^n$ (from the first part of the Wikipedia article; it follows that the inequality we ned holds when $n > e^2$.
I make no guarantees that this is the shortest solution. In fact I suspect it's not, because GKP categorize this exercise as a "warmup".
