# Show that $a_n = \frac{1}{n+1} + \frac{1}{n+2} + \cdots + \frac{1}{2n} \leq 1$ for each n.

It is known that $a_{n+1} > a_n$.

I tried to prove this 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?

• There are $n$ terms, each $\le \frac{1}{n+1}$. – André Nicolas Sep 15 '15 at 4:05

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

• Please note I had a typo in (2), that I managed to fix within the 5 minute window. – André Nicolas Sep 15 '15 at 4:19
• As always, very well done. Concise, complete, and simple! +1 – Mark Viola Sep 15 '15 at 4:20
• In fixing the typo in (2) I introduced one in (1). Now fixed! – André Nicolas Sep 15 '15 at 4:22

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.