3
$\begingroup$

I recently came across the following exercise:

Prove that $$\sum_{k=1}^n \frac{1}{n+k} \le \frac{3}{4}$$ for every natural number $n \ge 1$.

I immediately tried by induction, by I did not succeed as - after some trivial algebraic manipulations - I arrive at $\sum_{k=0}^{n+1} \frac{1}{n+k} \le \frac{3}{4} + \text{something non-negative}$.

Thus the solution I have found goes via comparison with the integral of $1/x$: more precisely, $$ \sum_{k=1}^n \frac{1}{n+k} \le \int_1^n \frac{dx}{n+x} =\ln(2n) - \ln(n+1) = \ln(2) + \ln\left(\frac{n}{n+1}\right) $$ and the conclusion follows easily as $\ln 2 \le 3/4$ and the last term is non-positive.

I would like to ask first if my solution is correct; secondly, do you have other solutions? I believe it should be very easy to prove.

$\endgroup$
  • $\begingroup$ Your inequality can't possible be true as for n=1, you would have $1/2 \leq 0$ $\endgroup$ – user172377 Aug 6 '17 at 7:57
  • $\begingroup$ Oh right. Well, let us say that we check $n=1$ by hands and that my inequality holds for $n>1$. :) $\endgroup$ – Romeo Aug 6 '17 at 8:00
  • $\begingroup$ Try factoring out an n from the denominator, then you can easily see that the limit of the sum is equal to the riemann integral $\int_{0}^{1} \frac{dx}{1+x} =ln 2 \leq 3/4$ $\endgroup$ – user172377 Aug 6 '17 at 8:06
  • $\begingroup$ Of course this is true only in the limit, hence you still have work to do here. $\endgroup$ – user172377 Aug 6 '17 at 8:17
  • $\begingroup$ It looks like the sum is indeed increasing with n, meaning the result is easy now. If we let $S_n$ be the given sum, then since $S_n$ is increasing, $lim_{n\to \infty}S_n = sup_{n} S_n = ln2$, therefore for every n, $S_n \leq sup_n S_n \leq ln2 \leq 3/4$ as needed. $\endgroup$ – user172377 Aug 6 '17 at 8:34
4
$\begingroup$

By C-S $$\sum_{k=1}^n\frac{1}{n+k}=1-\sum_{k=1}^n\left(\frac{1}{n}-\frac{1}{n+k}\right)=1-\frac{1}{n}\sum_{k=1}^n\frac{k}{n+k}=$$ $$=1-\frac{1}{n}\sum_{k=1}^n\frac{k^2}{nk+k^2}\leq1-\frac{\left(\sum\limits_{k=1}^nk\right)^2}{n\sum\limits_{k=1}^n(nk+k^2)}=1-\frac{\frac{n(n+1)^2}{4}}{n\cdot\frac{n(n+1)}{2}+\frac{n(n+1)(2n+1)}{6}}=$$ $$=\frac{7n-1}{2(5n+1)}<0.7\leq\frac{3}{4}.$$ Done!

I think it's interesting that $\ln2=0.6931...$.

C-S forever!!!

$\endgroup$
  • $\begingroup$ Interesting is that $\frac{7n-1}{2(5n+1)}=\frac 7 {10}-\frac 6{25n}+O\left(\frac{1}{n^2}\right)$ to compare with $S_n=\log (2)-\frac{1}{4 n}+O\left(\frac{1}{n^2}\right)$ I gave in a deleted answer based on the asymptotics. Look how close to each other are the coefficients. By the way, $\to +1$. $\endgroup$ – Claude Leibovici Aug 6 '17 at 14:54
2
$\begingroup$

$$\sum_{k=1}^{n}\frac{1}{n+k}\leq \sum_{k=1}^{n}\frac{1}{\sqrt{(n+k)(n+k-1)}}\stackrel{\text{CS}}{\leq}\sqrt{n\sum_{k=1}^{n}\left(\frac{1}{n+k-1}-\frac{1}{n+k}\right)}$$ immediately leads to $H_{2n}-H_n = \sum_{k=1}^{n}\frac{1}{n+k}\leq \frac{1}{\sqrt{2}}<\frac{3}{4}$.

$\endgroup$
1
$\begingroup$

All you really need to do is change the lower limit in the integral from $1$ to $0$, which gives the simpler result

$$\sum_{k=1}^n{1\over n+k}\le\int_0^n{dx\over n+x}=\ln(2n)-\ln n=\ln2$$

One way to see that $1$ is the wrong lower limit to use is that, in general, the number of terms in the sum should equal the difference of the upper and lower limits in the integral. That's because the integral comparison test usually compares each term with the area beneath a curve over a unit segment.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.