# 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. – Paolo Intuito Nov 10 '17 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. – Gibbs Nov 10 '17 at 16:35
• Sure, but I'm not sure that seeing'' that the limit is $\log 2$ can be done without some integral calculus. – Paolo Intuito Nov 10 '17 at 16:37
• Isn't the integral test for the graph of $\frac{1}{x}$ simply enough to see this? – Aritro Pathak Nov 10 '17 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! – Paolo Intuito Nov 14 '17 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$. – Thomas Andrews Nov 29 '17 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. – Thomas Andrews Nov 29 '17 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. – Thomas Andrews Nov 12 '17 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. – Mr Pie Feb 19 '18 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. – Thomas Andrews Feb 20 '18 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)." – Thomas Andrews Nov 12 '17 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}$$