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.$$
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP