Check that $a_n = \sum_{k=1}^n \frac{1}{n+k}$ is bounded from above by $\frac 34$ Any ideas on how to check that
$
a_n = \sum_{k=1}^n\frac{1}{n+k} \le \frac 34\,?
$
It's pretty easy to see that the sequence is monotonic and has an almost trivial upper bound of $1$ (and a trivial lower bound of $1/2$).
I solved it several years ago but can't recall my solution. I do remember I scratched my head for a while, though. I'm quite sure one needs to get an upper bound through some algebraic manipulation to get $\sum_{k=2}^\infty \frac {1}{k^2}$ (well, some polynomial of order 2 in $k$) but can't recover the proper way to do it (without relying on integral calculus).
Wolframalpha suggests that $\lim_n a_n = \ln(2)$, which can be easily seen by integration. Is there a `more' elementary way to see it? My guess would be no.
 A: Replace $n$ by $5n$ and split the sum into $5$ parts
\begin{eqnarray*}
\sum_{k=1}^{5n} \frac{1}{5n+k} = \sum_{k=1}^{n} \frac{1}{5n+k} +\sum_{k=1}^{n} \frac{1}{6n+k} +\sum_{k=1}^{n} \frac{1}{7n+k} +\sum_{k=1}^{n} \frac{1}{8n+k} +\sum_{k=1}^{n} \frac{1}{9n+k} \\ \leq \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8} + \frac{1}{9}   = \frac{1879}{2520} < \frac{3}{4}.
\end{eqnarray*}
A: You have:
$$\begin{align}S&=\sum_{k=0}^{n-1}\frac{1}{n+1+k}\\&\quad\text{and}\\
S&=\sum_{k=0}^{n-1}\frac{1}{2n-k}\end{align}$$
So $$\begin{align}2S&=\sum_{k=0}^{n-1} \left(\frac{1}{n+1+k}+\frac{1}{2n-k}\right)\\
&=\sum_{k=0}^{n-1}\frac{3n+1}{(n+1+k)(2n-k)}
\end{align}$$
The shape of $(n+1+k)(2n-k)$ is increasing for $k<\frac{n-1}{2}$ and decreasing for $k>\frac{n-1}{2}$. So the minimum value here for $k=0,\dots,n-1$ is either when $k=0$ or $k=n-1$, which are the same value, $(n+1)2n$.
So:
$$\frac{3n+1}{(n+1+k)(2n-k)}\leq \frac{3n+1}{2n(n+1)}$$ and summing we get:
$$2S\leq \frac{n(3n+1)}{2n(n+1)}=\frac{3n+1}{2n+2}<\frac{3n+3}{2n+2}=\frac{3}{2}$$
We also get $(n+1-k)(2n-k)\leq \left(\frac{3n+1}{2}\right)^2$. So:
$$2S\geq \frac{4n(3n+1)}{(3n+1)^2}=\frac{4n}{3n+1}$$ or $$S\geq \frac{2n}{3n+1}$$
That's not really much of a lower bound, since $a_9>\frac{2}{3}.$
A: By C-S $$\sum_{k=1}^n\frac{1}{n+k}=\sum_{k=1}^n\left(\frac{1}{n+k}-\frac{1}{n}\right)+1=1-\sum_{k=1}^n\frac{k}{n(n+k)}=$$
$$=1-\sum_{k=1}^n\frac{k^2}{n^2k+nk^2}\leq1-\frac{\left(\sum\limits_{k=1}^nk\right)^2}{n^2\sum\limits_{k=1}^nk+n\sum\limits_{k=1}^nk^2}=1-\frac{\frac{n^2(n+1)^2}{4}}{\frac{n^3(n+1)}{2}+\frac{n^2(n+1)(2n+1)}{6}}\leq\frac{3}{4}$$
A: If you already proved that $H_{2n}-H_n$ is increasing with respect to $n$ you are essentially done.
Here $H_n$ is the $n$-th harmonic number, $\sum_{k=1}^{n}\frac{1}{k}$, and by Riemann sums
$$\lim_{n\to +\infty}\left(H_{2n}-H_n\right)=\lim_{n\to +\infty} \sum_{k=1}^{n}\frac{1}{k+n}=\lim_{n\to +\infty}\frac{1}{n}\sum_{k=1}^{n}\frac{1}{1+\frac{k}{n}}=\int_{0}^{1}\frac{dx}{1+x}=\log 2.$$
As an alternative,
$$ H_{2n}-H_n = \sum_{k=1}^{2n}\frac{(-1)^{k+1}}{k}$$
is clearly related with the Taylor series of $\log(1+x)$ at the origin.
Thus it is enough to prove $\log(2)<\frac{3}{4}$. We can do much better. By computing a polynomial remainder we have
$$ \int_{0}^{1}\frac{x^4(1-x)^4}{1+x}\,dx =-\frac{621}{56}+16\log 2,$$
where the integrand function is positive but bounded by $\frac{1}{4^4}$ on $[0,1]$. It follows that:
$$ H_{2n}-H_n \leq \log(2) < \color{red}{\frac{39}{56}}.$$
A: you can use this theorem, for the case a = 1, to prove the inequality.

