TransWikia.com

About a proof of a proposition in "Concrete Mathematics" by Donald E. Knuth et al..

Mathematics Asked on December 5, 2021

I am reading "Concrete Mathematics" by Donald Knuth, et al..

There is the following proposition in this book without a proof:

$n^{alpha_1} (log n)^{alpha_2} (log log n)^{alpha_3} prec n^{beta_1} (log n)^{beta_2} (log log n)^{beta_3} iff (alpha_1, alpha_2, alpha_3) < (beta_1, beta_2, beta_3)$.
Here ‘$(alpha_1, alpha_2, alpha_3) < (beta_1, beta_2, beta_3)$‘ means lexicographic order.
Here ‘$f(n) prec g(n)$‘ means $lim_{n to infty} frac{f(n)}{g(n)} = 0$.

I proved this proposition as follows, but I am not sure that my proof is a proof which the authors expect.
If my proof is not a proof which the authors expect, please show me a proof which the authors expect.

My proof is the following:

Lemma:
Let $alpha$ be any real number.
Let $beta$ be a positive real number.
Then,
$lim_{x to infty} frac{(log x)^alpha}{x^beta}=0$.

Proof of lemma:
Let $m$ be a natural number such that $alpha + 1 < m$.
Let $x$ be a positive real number.
By Taylor’s Theorem, there exists $theta in (0, 1)$ such that $$e^x = 1+x+frac{x^2}{2!}+cdots+frac{x^m}{m!}+frac{e^theta}{(m+1)!}x^{m+1} > frac{x^m}{m!}.$$
If $x > 1$, then $x^m > x^{alpha+1}$, so $$frac{e^x}{x^alpha} > frac{x^m}{m! x^alpha} > frac{x}{m!} to +infty(x to +infty).$$
$frac{(log x)^alpha}{x^beta}=frac{(frac{beta log x}{beta})^alpha}{e^{beta log x}}=frac{1}{beta^alpha} frac{(beta log x)^alpha}{e^{beta log x}} = frac{1}{beta^alpha} frac{1}{frac{e^{beta log x}}{(beta log x)^alpha}} to 0 (x to infty)$.

Proof of the proposition:
Let $alpha_1 < beta_1$.
$$frac{n^{alpha_1} (log n)^{alpha_2} (log log n)^{alpha_3}}{n^{beta_1} (log n)^{beta_2} (log log n)^{beta_3}} = frac{(log n)^{alpha_2 – beta_2} (log log n)^{alpha_3 – beta_3}}{n^{beta_1 – alpha_1}}.$$
If $alpha_3 leq beta_3$, then by the above lemma, it is obvious that $frac{(log n)^{alpha_2 – beta_2} (log log n)^{alpha_3 – beta_3}}{n^{beta_1 – alpha_1}} to 0$.
So, we assume that $alpha_3 > beta_3$.
$$frac{(log n)^{alpha_2 – beta_2} (log log n)^{alpha_3 – beta_3}}{n^{beta_1 – alpha_1}} < frac{(log n)^{alpha_2 – beta_2} (log n)^{alpha_3 – beta_3}}{n^{beta_1 – alpha_1}} = frac{(log n)^{alpha_2 – beta_2+alpha_3 – beta_3}}{n^{beta_1 – alpha_1}} to 0$$ by the above lemma.
Let $alpha_1 = beta_1$ and $alpha_2 < beta_2$.
$$frac{n^{alpha_1} (log n)^{alpha_2} (log log n)^{alpha_3}}{n^{beta_1} (log n)^{beta_2} (log log n)^{beta_3}} = frac{(log log n)^{alpha_3 – beta_3}}{(log n)^{beta_2 – alpha_2}} to 0$$ by the above lemma.
Let $alpha_1 = beta_1$ and $alpha_2 = beta_2$ and $alpha_3 < beta_3$.
$$frac{n^{alpha_1} (log n)^{alpha_2} (log log n)^{alpha_3}}{n^{beta_1} (log n)^{beta_2} (log log n)^{beta_3}} = frac{1}{(log log n)^{beta_3 – alpha_3}} to 0.$$

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP