Can I show $\frac{1}{n+1} + \frac{1}{n+2} + \cdots + \frac{1}{2n} \leq 1$ by induction?

Question

It is known that $a_{n+1} > a_n$. I tried to prove

$$\frac{1}{n+1} + \frac{1}{n+2} + \cdots + \frac{1}{2n} \leq 1$$ via induction.

Base case: $a_0 = \frac{1}{0+1} = 1 \leq 1$

Inductive step: assume $a_n \leq 1$, prove $a_{n+1} \leq 1$.

$a_n = \frac{1}{n+1} + \frac{1}{n+2} + \cdots + \frac{1}{2n} \leq 1$ $\frac{1}{n+2} + \frac{1}{n+3}+ \cdots + \frac{1}{2n} + \frac{1}{2n+1} + \frac{1}{2n+2} \leq 1-\frac{1}{n+1} + \frac{1}{2n+1} + \frac{1}{2n+2}$

But $-\frac{1}{n+1} + \frac{1}{2n+1} + \frac{1}{2n+2}$ is positive, so I'm not sure where to go from here.

Normally, the inductive step would involve a change on the right hand side, but in this case, it remains the same. Makes me wonder if induction is even the correct approach?

Answer 1

The result is "obvious." There are $n$ terms in the sum, each $\le \frac{1}{n+1}$. So the sum is $\le \frac{n}{n+1}$, which is $\lt 1$.

If we, unreasonably, want to prove the result by induction, we run into the problem mentioned in the OP. The solution is to strengthen the induction hypothesis. We prove by induction that our sum is $\le \frac{n}{n+1}$.

So suppose we know that for a particular $k$ we have $$\frac{1}{k+1}+\frac{1}{k+2}+\cdots +\frac{1}{2k}\le \frac{k}{k+1}.\tag{1}$$ We want to show that $$\frac{1}{k+2}+\frac{1}{k+3}+\cdots +\frac{1}{2k}+\frac{1}{2k+1}+\frac{1}{2k+2}\le \frac{k+1}{k+2}.\tag{2}$$ Now if we use the induction hypothesis (1) and play a bit with inequalities, we can prove (2).

Answer 2

According to Wolfram Alpha, this series is equivalent to $ \psi^{(0)}(2n+1)-\psi^{(0)}(n+1)$ where $ \psi^{(0)}(x)$ is the $n^{th}$ derivative of the digamma function. Using this, you could show the continuity for the function for values of $n > 0$, show that the limit as n approaches infinity is $log(2)$ (easily proven), and show that the function is continuously increases (by showing derivative is positive for $n>0$?)

Note that this actually shows that the series is always $< log(2)$, a stronger statement than that given by the induction argument.