3
$\begingroup$

In Introduction to Analytic Number Theory, theorem 8.21, Apostol's proves Pólya's inequality. The last step of the proof requires showing:

$\sum\limits_{n \le k/2} \frac 1 n < log \; k$

my proof of the theorem shows that we need $k > 1$. Is this a standard inequality? What is an easy way to prove it? I have to code it into a theorem prover!

Here is the proof of the book:

enter image description here

enter image description here

$\endgroup$
  • 1
    $\begingroup$ You can bound this sum by something like $\int_1^{k/2+1}\frac{1}{x} dx=\log(k/2+1)$ $\endgroup$ – Julian Mejia May 28 at 17:37
  • $\begingroup$ If $k = 1$ then both left and right parts are $0$, so inequality doesn't hold. Even if $k = 2$, right part is less than $1$, and left part is $1$. From calculator, for $k = 8$ right part is $2.079$ and left part is $2.083$, and for $k=10$ it's already $2.30$ and $2.28$. Are you sure it isn't enough that it holds for large enough $k$? (then left part is $\log k + \gamma - 1 + O(\frac{1}{k})$, and as $\gamma < 1$, this inequality holds - however, as difference is small, we need sophisticated enough tools) $\endgroup$ – mihaild May 28 at 17:47
  • 1
    $\begingroup$ @JulianMejia it will be $\log(k / 2) + 1$ - first addend is $1$, $i$-th is at most $\log(i + 1) - \log i$, and this bound isn't enough. For example, if $k = 2$, this sum is $1$ and your bound is $\log(2) < 1$. $\endgroup$ – mihaild May 28 at 17:49
  • $\begingroup$ @mihaild , yes you are right. I can just get bound $\log k+1-\log 2$. $\endgroup$ – Julian Mejia May 28 at 17:52
  • $\begingroup$ @mihaild i posted the complete proof, it doesn't say anything about large k $\endgroup$ – Javier May 28 at 17:58
2
$\begingroup$

Let's write $H_m = \sum\limits_{n=1}^m \frac{1}{n}$. Then we need to show:

$(1) \; k = 2m + 1 \implies H_m < \log(2m + 1)$ and $(2) \; k = 2m + 2 \implies H_m < \log(2m + 2)$

It's enough to prove $H_m < \log(2m + 1)$.

We have $\log(2m + 1) = \log(2 + \frac{1}{m}) + \log m = \log 2 + \log m + \log(1 + \frac{1}{2m})$.

From, for example, Approximating Euler's constant by Hirschhorn (we actually need a weaker result than theirs, but it's the only reference I found) we have $H_m < \log m + \gamma + \frac{1}{2m}$. So we need $\gamma + \frac{1}{2m} \leqslant \log2 + \log(1 + \frac{1}{2m})$ or $\log 2 - \gamma + \log(1 + \frac{1}{2m}) - \frac{1}{2m} \geqslant 0$.

Derivative of left side is $\frac{1}{2m^2}\cdot\left(\frac{1}{-1 + 1 / 2m} + 1\right) > 0$, so if the inequality holds for some $m$, it holds for all greater $m$. From wolfram, it holds for $m = 2$. For $m = 1$, we can manually check $H_1 = 1$ and $\log(3) > \log(e) > 1$.

(I would like to see some proof involving less calculations, but as I commented we at least need to somehow get $\gamma < 1$)

$\endgroup$
2
$\begingroup$

Let me combine all the ideas I find to prove that $\forall k \ge 1. H_m < \log(2*m+1)$. As noted by @mihaild this is sufficient for the proof of the theorem. We can proceed by induction.

For $k = 1$ , we have $1 < \log(3) = 1.09\ldots$ which holds.

For $k > 1$, we assume $H_m < \log(2*m+1)$ and would like to show $H_{m+1} < \log(2*(m+1)+1)$.

We have $H_{m+1} = H_m + \frac 1 {m+1} < \log(2m+1) + ?$. To fill this placeholder we note that $\log(2m+1) + \log(x) = \log(2*(m+1)+1)$ when $x = \frac{2m+3}{2m+1}$ and in that case we would just need to prove that $\frac 1 {m+1} < \log(1+\frac 2 {2m+1})$. But this is true since the function $f(x) = (x+1) \log(1+ \frac 2 {2x+1}) - 1 > 0$ in $]\frac{-1} 2,+\infty[$. To see this is for the cases we are interested is useful to remember that $e$ is the unique number for which $\Big(1+\frac 1 {x}\Big)^{x} < e < \Big(1+ \frac 1 {x}\Big)^{x+1}$ for all $x > 0$ (see wikipedia).

Application on Polya's inequality

In fact, what is needed to conclude the proof of Polya's inequality is:

For $k \ge 2$ we have

  1. If $k$ is odd then $H_{\frac k 2} < \log(k)$.

  2. If $k$ is even then $H_{\frac k 2 - 1} + \frac 1 k < \log(k)$

For 1. the proof follows easily from the above.

For 2. one notes $h(\frac k 2 - 1) < \log(2*(\frac k 2 - 1)+1) = \log(k-1)$ by the above. Then $\log(k-1) + \frac 1 k < \log(k)$ since the function $x*\log(1+\frac 1 {x-1}) - 1$ is again positive in $[1,+\infty[$. The same inequality as before is used to establish this.

$\endgroup$
  • $\begingroup$ $\frac 1 {m+1}< \log(1+\frac 2 {2m+1})$ comes directly from $e<(1+\frac{1}{x})^{x+\frac{1}{2}}$ . $\endgroup$ – user90369 Jun 4 at 8:44
0
$\begingroup$

The corrected inequation with $~k\geq 3~$: $$\sum\limits_{n\leq\frac{k-1}{2}}\frac{1}{n} < \ln k$$

It’s enough to proof $~\displaystyle \sum\limits_{v=1}^m\frac{1}{v} < \ln(2m+1)~$ for $~m\geq 1~$.

We can use $~\displaystyle e<\left(1+\frac{1}{x}\right)^{x+\frac{1}{2}}~$ for $~x>0~$ . A short proof for that is my note here .

Let $~\displaystyle x:=v-\frac{1}{2}~$ with $~v\in\mathbb{N}~$ .

It’s $~\displaystyle e<\left(1+\frac{1}{v-\frac{1}{2}}\right)^v~$ and it follows:

$$\displaystyle \frac{1}{v} < \ln\left(1+\frac{2}{2v-1}\right) = \ln\left(1+\frac{1}{2v-1}\right) + \ln\left(1+\frac{1}{2v}\right)$$

We get the proof:

$$\sum\limits_{v=1}^m\frac{1}{v} < \sum\limits_{v=1}^m\ln\left(1+\frac{2}{2v-1}\right) = \sum\limits_{v=1}^{2m}\ln\left(1+\frac{1}{v}\right) = \ln(2m+1)$$

$\endgroup$

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.