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 :)


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)}$$

  • $\begingroup$ Oh, right. I didn't notice I could get rid of that $\dfrac{-ab}{2n^2}$ easily. Thank you for pointing this out :) $\endgroup$ – Quintofron Aug 31 '12 at 0:56

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$.

  • $\begingroup$ In this case it's $(\ln n)! \geqslant (\ln n)^2/2$. Then, after taking $\log$s of both functions $(n^{\ln \ln \ln n}$ and $(\ln n)^2/2)$ it's simple to show $\lim_{n \rightarrow \infty} \dfrac{\ln \ln \ln n \ln n}{(\ln n)^3/2} = 0$. Hence $n^{\ln \ln \ln n} \prec (\ln n)^2/2 \leqslant (\ln n)!$. $\\$ Is there a simple way to justify that the estimation $z! \geqslant z^{z/2}$ works not only for natural numbers (proved in GKP), but real/complex as well (which is needed here)? $\endgroup$ – Quintofron Aug 31 '12 at 15:35
  • $\begingroup$ As for the third pair of functions, I took $log$s as well and obtained $\ln((n!)!) = \ln 1 + \ln 2 + \ldots + \ln n!$ and $\ln(((n-1)!)!(n-1)!^{n!}) = (\ln 1 + \ln 2 + \ldots + \ln(n-1)!)(1 + n!)$. I can't see yet how to finish the proof that $(n!)! \succ (n-1)!)!(n-1)!^{n!}$ (as stated in the answers to this exercise). $\endgroup$ – Quintofron Aug 31 '12 at 16:41
  • $\begingroup$ You only need it for real $z$. If you're willing to assume that $\Gamma(z)$ is an increasing function (which follows from the definition of $\Gamma$ as an integral) then it will suffice to show that $z! \ge (z+1)^{(z+1)/2}$ for large enough integers $z$. This lower bound is bigger than the previous one by a factor of about $\sqrt{ez}$, which is pretty much negligible. (At some point, if you're going to worry about this sort of thing, you should just throw in the towel and use Stirling.) $\endgroup$ – Michael Lugo Aug 31 '12 at 22:32

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".

  • $\begingroup$ I understand the line of reasoning, but have one little question: isn't it so that we should show at least one asymptotic inequality between the compared functions in order to prove either of them grows faster? Among the inequalities above, the one between $(n-1)!$ and $(n/e)^n$ is a '$\prec$' inequality (that's what we're heading for after all), but I don't know how to show this. Also, thanks for the effort you've made. $\endgroup$ – Quintofron Sep 1 '12 at 1:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.