Prove $\sum\limits_{n \le k/2} \frac 1 n < \log k$ for Pólya's inequality

Question

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:

Answer 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.

Answer 2

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

Answer 3

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