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

• My bad, I meant 3/4. Editing original post. Commented Nov 10, 2017 at 16:25
• Isn't it enough to compute the limit? The sequence is convergent and increasing, so the limit is the supremum of its image. Since it is $\log 2$ then it is trivially less than 3/4. I'm not sure about what kind of solution you're looking for. Commented Nov 10, 2017 at 16:35
• Sure, but I'm not sure that seeing'' that the limit is $\log 2$ can be done without some integral calculus. Commented Nov 10, 2017 at 16:37
• Isn't the integral test for the graph of $\frac{1}{x}$ simply enough to see this? Commented Nov 10, 2017 at 17:23

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

• Not the way I was thinking of, but I do like this one quite a bit. It even gives a better lower bound. If I ever recall what I did, I will keep you guys posted! Commented Nov 14, 2017 at 14:19

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

• Very cute answer. Since the $a_n$ can be seen as increasing, you only need to know it is true for $n$ a multiple of $5$. Commented Nov 29, 2017 at 18:35
• More generally, replace $5$ with $m$, you get that $a_{mn}\leq \frac{1}{2m}+a_m.$ This gives you better and better upper bounds. Commented Nov 29, 2017 at 18:53

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

• You've been around long enough to know how to use \begin{align}...\end{align}`. And the main step here is opaque. Use your words. Commented Nov 12, 2017 at 0:54
• @ThomasAndrews I think Michael prefers to not use the align commands, and although opaque as you put it, it still answers the question, and quite finely in my opinion. Perhaps he could elaborate on what By C-S actually means, so in that case, C-S = Cauchy-Schwarz Inequality. Commented Feb 19, 2018 at 9:12
• @user477343 Whatever he prefers, it formats terribly on various browsers. On my iPad, it lost the $\leq \frac{3}{4}.$ It looks horrible even without that - it is hard to tell where the expressions begin and end without careful eye-balling. Commented Feb 20, 2018 at 16:56

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

• "I solved it several years ago but can't recall my solution ... but can't recover the proper way to do it (without relying on integral calculus)." Commented Nov 12, 2017 at 0:53

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

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