# Proof $\sum\limits_{n \le k/2} \frac 1 n < \log k$ to show Pólya's inequality

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:

• You can bound this sum by something like $\int_1^{k/2+1}\frac{1}{x} dx=\log(k/2+1)$ – Julian Mejia May 28 at 17:37
• 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) – mihaild May 28 at 17:47
• @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$. – mihaild May 28 at 17:49
• @mihaild , yes you are right. I can just get bound $\log k+1-\log 2$. – Julian Mejia May 28 at 17:52
• @mihaild i posted the complete proof, it doesn't say anything about large k – Javier May 28 at 17:58

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

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.

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

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