1
$\begingroup$

I'm trying to understand a theorem in a paper on page 14/24. We are given that

$Z = (nq-1) \log \left(\frac{M+nq-1}{nq-1} \right) + M \log \left(\frac{M+nq-1}{M} \right) + \frac{1}{2} \log \left( \frac{M+nq-1}{(nq-1)M} \right) + O(1) .$

Since $e^a > \left(1+\frac{a}{b} \right)^b$ for all $a > 0$ and positive integers $b$, the second term equals

$\log \left(1 + \frac{nq-1}{M} \right)^M < \log e^{nq-1}$

for all positive M and $nq-1 > 0$. This much I'm following, but then it goes on saying:

Since $0 < q < n$ and $n \leq M \leq qn^2$,

$\dfrac{1}{2(nq-1)} \log \left( \frac{M+nq-1}{(nq-1)M} \right)\to 0 \quad \text{for } n \to \infty .$

Where does the factor $\frac{1}{2(nq-1)}$ come from? This might even be trivial, but somehow I'm totally unable to see it.

  • 0
    maybe the author wants only to show that $2(nq-1)$ tends to $\infty$ faster than $\log \frac{M + nq -1}{(nq-1)M}$.2011-06-08

1 Answers 1

1

OK, thanks to the paper, I figured it out. What they do is rewrite

$Z = (nq-1) \log \dfrac{M+nq-1}{nq-1} + M \log \dfrac{M+nq-1}{M} + \dfrac{1}{2} \log \dfrac{M+nq-1}{(nq-1)M} + O(1)$

with their formula for the second term

$M\log\left(1 + \dfrac{nq-1}{M}\right) < (nq-1)\log e$

which gives

$Z < (nq-1) \log \dfrac{M+nq-1}{nq-1} + (nq-1)\log e + \dfrac{1}{2} \log \dfrac{M+nq-1}{(nq-1)M} + O(1)$

Of course, it has become an inequality, particularly an upper bound for $Z$. Now separate out the factor $(np-1)$ and you'll get

$Z < (nq-1) \left( \log \dfrac{M+nq-1}{nq-1} + \log e + \dfrac{1}{2(nq-1)} \log \dfrac{M+nq-1}{(nq-1)M} + O\left(\frac{1}{nq-1}\right) \right)$

Now, see the third term is exactly what they are computing the limit of. Since that goes to zero, and the $O\left(\frac{1}{nq-1}\right)$ term does as well, you get the end result

$Z < (nq-1)\left( \log \dfrac{M+nq-1}{nq-1} + \log e \right) \; .$

  • 0
    Ahh, I see. Thanks a lot!2011-06-08