Check that $a_n = \sum_{k=1}^n \frac{1}{n+k}$ is bounded from above by $\frac 34$

Question

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.

Answer 1

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}.$

Answer 2

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*}

Answer 3

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

Answer 4

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}}.$$

Answer 5

you can use this theorem, for the case a = 1, to prove the inequality.

Answer 6

Pre-Calculus Approach to Bounding by $\boldsymbol{\frac7{10}\lt\frac34}$

Let $$ a_n=\sum_{k=1}^n\frac1{n+k}\tag1 $$ Then $$ \begin{align} a_n &=a_{n-1}+\frac1{2n-1}-\frac1{2n}\tag2\\ &\le a_{n-1}+\frac1{4n-3}-\frac1{4n+1}\tag3\\ &\le\frac7{10}-\frac1{4n+1}\tag4 \end{align} $$ Explanation:
$(2)$: $a_n-a_{n-1}=\frac1{2n-1}+\frac1{2n}-\frac1n$
$(3)$: $\frac1{2n-1}-\frac1{2n}\lt\frac1{4n-3}-\frac1{4n+1}$
$(4)$: $(3)$ says that $a_n+\frac1{4n+1}$ is a decreasing sequence so $a_n+\frac1{4n+1}\le a_1+\frac15=\frac7{10}$

---

Slight Improvement Using Subsequent Terms

The argument above says that $a_n\le\frac7{10}$. However, $(2)$ says that $a_n$ is an increasing sequence and $(3)$ says that $a_n+\frac1{4n+1}$ is a decreasing sequence. This means that $a_n\le a_k+\frac1{4k+1}$ for any pair $n,k$. $$ \begin{array}{c|c} k&a_k+\frac1{4k+1}&\text{approx}\\\hline 1&\frac7{10}&0.7\\ 2&\frac{25}{36}&0.69444444\\ 3&\frac{541}{780}&0.69358974\\ 4&\frac{9901}{14280}&0.69334734\\ 5&\frac{1747}{2520}&0.69325397\\ 6&\frac{96079}{138600}&0.69321068\\ 7&\frac{7244119}{10450440}&0.69318794\\ 8&\frac{99917}{144144}&0.69317488\\ \end{array} $$