29
$\begingroup$

I'm searching for a really simple and beautiful proof that the sequence $(u_n)_{n \in \mathbb{N}} = \sum\nolimits_{k=1}^n \frac{1}{k} - \log(n)$ converges.
At first I want to know if my answer is OK.

My try:
$\lim\limits_{n\to\infty} \left(\sum\limits_{k=1}^n \frac{1}{k} - \log (n)\right) = \lim\limits_{n\to\infty} \left(\sum\limits_{k=1}^n \frac{1}{k} + \sum\limits_{k=1}^{n-1} [\log(k)-\log(k+1)]\right)$

$ = \lim\limits_{n\to\infty} \left(\frac{1}{n} + \sum\limits_{k=1}^{n-1} \left[\log(\frac{k}{k+1})+\frac{1}{k}\right]\right) = \sum\limits_{k=1}^{\infty} \left[\frac{1}{k}-\log(\frac{k+1}{k})\right]$
Now we prove that the last sum converges by the comparison test:
$\frac{1}{k}-\log(\frac{k+1}{k}) < \frac{1}{k^2} \Leftrightarrow k<k^2\log(\frac{k+1}{k})+1$
which surely holds for $k\geqslant 1$


As $ \sum\limits_{k=1}^{\infty} \frac{1}{k^2}$ converges $ \Rightarrow \sum\limits_{k=1}^{\infty} \left[\frac{1}{k}-\log(\frac{k+1}{k})\right]$ converges and we name this limit $\gamma$
q.e.d

$\endgroup$
9
  • 1
    $\begingroup$ Hint: look at the function $y=1/x$ compared to "step functions" above and below that curve, and look at what happens when you integrate. $\endgroup$
    – Old John
    Jan 6, 2014 at 23:59
  • 1
    $\begingroup$ math.stackexchange.com/questions/306371/… $\endgroup$
    – Will Jagy
    Jan 7, 2014 at 0:01
  • 1
    $\begingroup$ the diagrams are not very good, but you can get the idea here. $\endgroup$
    – Old John
    Jan 7, 2014 at 0:05
  • 2
    $\begingroup$ @OldJohn, I see, actually a link to a Macalester College discussion of the harmonic series. Natural mistake. $\endgroup$
    – Will Jagy
    Jan 7, 2014 at 0:09
  • 2
    $\begingroup$ @OldJohn, true, never met her. There is a running joke on a TV series called NCIS, in which FBI agent Fornell married a woman whom NCIS agent Gibbs had divorced. At one point Fornell says "In my defense, I didn't believe him." $\endgroup$
    – Will Jagy
    Jan 7, 2014 at 0:28

6 Answers 6

40
$\begingroup$

One elegant way to show that the sequence converges is to show that it's both decreasing and bounded below.

It's decreasing because $u_n-u_{n-1} = \frac1n - \log n + \log(n-1) = \frac1n + \log(1-\frac1n) < 0$ for all $n$. (The inequality is valid because $\log(1-x)$ is a concave function, hence lies beneath the line $-x$ that is tangent to its graph at $0$; plugging in $x=\frac1n$ yields $\log(1-\frac1n) \le -\frac1n$.)

It's bounded below because $$ \sum_{j=1}^n \frac1j > \int_1^{n+1} \frac{dt}t = \log (n+1) > \log n, $$ and so $u_n>0$ for all $n$. (The inequality is valid because the sum is a left-hand endpoint Riemann sum for the integral, and the function $\frac1t$ is decreasing.)

$\endgroup$
10
$\begingroup$

Upper Bound

Note that $$ \begin{align} \frac1n-\log\left(\frac{n+1}n\right) &=\int_0^{1/n}\frac{t\,\mathrm{d}t}{1+t}\\ &\le\int_0^{1/n}t\,\mathrm{d}t\\[3pt] &=\frac1{2n^2} \end{align} $$ Therefore, $$ \begin{align} \gamma &=\sum_{n=1}^\infty\left(\frac1n-\log\left(\frac{n+1}n\right)\right)\\ &\le\sum_{n=1}^\infty\frac1{2n^2}\\ &\le\sum_{n=1}^\infty\frac1{2n^2-\frac12}\\ &=\sum_{n=1}^\infty\frac12\left(\frac1{n-\frac12}-\frac1{n+\frac12}\right)\\[9pt] &=1 \end{align} $$


Lower Bound

Note that $$ \begin{align} \frac1n-\log\left(\frac{n+1}n\right) &=\int_0^{1/n}\frac{t\,\mathrm{d}t}{1+t}\\ &\ge\int_0^{1/n}\frac{t}{1+\frac1n}\,\mathrm{d}t\\[3pt] &=\frac1{2n(n+1)} \end{align} $$ Therefore, $$ \begin{align} \gamma &=\sum_{n=1}^\infty\left(\frac1n-\log\left(\frac{n+1}n\right)\right)\\ &\ge\sum_{n=1}^\infty\frac1{2n(n+1)}\\[3pt] &=\sum_{n=1}^\infty\frac12\left(\frac1n-\frac1{n+1}\right)\\[6pt] &=\frac12 \end{align} $$


A Better Upper Bound

Using Jensen's Inequality on the concave $\frac{t}{1+t}$, we get $$ \begin{align} \frac1n-\log\left(\frac{n+1}n\right) &=\frac1n\left(n\int_0^{1/n}\frac{t\,\mathrm{d}t}{1+t}\right)\\ &\le\frac1n\frac{n\int_0^{1/n}t\,\mathrm{d}t}{1+n\int_0^{1/n}t\,\mathrm{d}t}\\ &=\frac1{n(2n+1)} \end{align} $$ Therefore, since the sum of the Alternating Harmonic Series is $\log(2)$, $$ \begin{align} \gamma &=\sum_{n=1}^\infty\left(\frac1n-\log\left(\frac{n+1}n\right)\right)\\ &\le\sum_{n=1}^\infty\frac1{n(2n+1)}\\ &=\sum_{n=1}^\infty2\left(\frac1{2n}-\frac1{2n+1}\right)\\[6pt] &=2(1-\log(2)) \end{align} $$

$\endgroup$
10
  • $\begingroup$ can you copy the last part of your answer here ? $\endgroup$ Nov 10, 2017 at 9:52
  • $\begingroup$ @robjohn may I know how do you get the inequality $$n\ \int_{0}^{\frac {1} {n}} \dfrac {t\ \mathrm {d} t} {1 + t} \leq \dfrac {n\ \int_{0}^{\frac {1} {n}} t\ \mathrm {d} t} {1 + n\ \int_{0}^{\frac {1} {n}} t\ \mathrm {d}t}\ ?$$ Is it the consequence of Jensen's inequality? Thanks. $\endgroup$
    – Anacardium
    Nov 1, 2020 at 13:44
  • $\begingroup$ It is Jensen with the concave function $\varphi(t)=\frac{t}{1+t}$ and then $n\int_0^{\frac1n}\varphi(t)\,\mathrm{d}t\le\varphi\left(n\int_0^{\frac1n}t\,\mathrm{d}t\right)$. $\endgroup$
    – robjohn
    Nov 1, 2020 at 13:51
  • $\begingroup$ Since $\varphi$ is concave on $[0,\infty)$ it follows that for any $x,y \geq 0$ we have $\varphi (tx + (1-t)y) \geq t\ \varphi (x) + (1-t)\ \varphi (y),$ for all $t \in [0,1].$ Am I right? $\endgroup$
    – Anacardium
    Nov 1, 2020 at 14:02
  • 3
    $\begingroup$ @AmbicaGovind: I don't quite understand your objection. The sum is a sum of positive terms. As long as the partial sums are bounded above (they are bounded above by $1$), the sum converges. $\endgroup$
    – robjohn
    Dec 22, 2021 at 17:26
4
$\begingroup$

All we use here is the power series expansion for $\log(1+z)$ with $|z|<1$:

$$ \log(1+z)=z-{z^2\over2}+{z^3\over3}-{z^4\over4}+\cdots\tag1 $$

It suffices to note that

$$ \log N=\log{N+1\over1}+\mathcal O\left(\frac1N\right)=\sum_{n\le N}\log{n+1\over n}+\mathcal O\left(\frac1N\right) $$

Thus, we have

$$ \sum_{n\le N}\frac1n-\log N=\sum_{n\le N}\left\{\frac1n-\log\left(1+\frac1n\right)\right\}+\mathcal O\left(\frac1N\right)\tag2 $$

As $n\to+\infty$, we know from (1) that

$$ \log\left(1+\frac1n\right)=\frac1n+\mathcal O\left(1\over n^2\right) $$

This is sufficient for us to show that the partial sum on the right hand side of (2) will converge when $N\to+\infty$. Thus, we know the left hand side of (2) converges too.

$\endgroup$
3
$\begingroup$

Here is a proof which is slightly ore elementary than the ones above.

Consider the following well-known inequality $$\frac1{n+1}<\log (n+1)-\log n<\frac1n\tag{$*$}$$ (it can be easily proves that using that $f_n=(1+1/n)^{n+1}$ and $e_n=(1+1/n)^n$ are decreasing and increasing, respectively, and both converge towards $e$)

First, by $(1)$ it follows that $$\sum_{k=1}^n \frac1k>\sum_{k=1}^n (\log(k+1)-\log k)=\log(n+1)>\log n,$$ so $u_n=\sum_{k=1}^n \frac1k - \log n$ is bounded below by $0$. But on the other hand by $(1)$ it also follows that $$u_{n+1}-u_n =\frac1{n+1}-\log (n+1)+\log n<0,$$ so the sequence is strictly decreasing. Hence by the Monotone convergence theorem $(u_n)_n$ is convergent, so we are done.

$\endgroup$
2
$\begingroup$

Your proof is nice. A simple proof by using graph:

By using Rieamann sums of $y=\frac1x$: $$\sum_{k=2}^n\frac1k<\ln(n)<\sum_{k=1}^{n-1}\frac1k$$ $$-\sum_{k=1}^{n-1}\frac1k<-\ln(n)<-\sum_{k=2}^{n}\frac1k$$ $$\frac1n<u_n<1.$$ So, $(u_n)$ is bounded. On the other hand, $$u_{n}-u_{n+1}=\ln(n+1)-\ln(n)-\frac1{n+1}=\int_n^{n+1}\frac1x dx-\frac1{n+1}>\frac1{n+1}-\frac1{n+1}=0.$$ So, $(u_n)$ is a bounded decreasing sequence. We are done.

$\endgroup$
-2
$\begingroup$

You can also prove it by drawing the curve of 1/x and then you can draw some rectangles (with lines on $x=1,2,...,n$) and shade them (which will be little above the curve) and find the area of the shaded rectangles that will be the sum $1+1/2+/1/3+...+1/n$ and find the area underneath the curve which will be greater than the area of the shaded rectangles. That way you can prove that the sequence is bounded below. Further to find if it is decreasing or increasing, you can find the value of $s_{n+1}-s{n}$ with the help of same method and it will be lower than 0 so you can conclude that it is decreasing. After that you can easily prove that it is converging to Euler's constant which is $1+1/2+1/3+....+1/n-logn$.

(not an exact answer...just to clear some reasoning)

$\endgroup$
4
  • $\begingroup$ Are you sure that it's an answer? $\endgroup$ Feb 15, 2020 at 4:58
  • 1
    $\begingroup$ Yes I am. ..this gets really easy with graphical method. Draw the curve of 1/x and you will get it $\endgroup$ Feb 15, 2020 at 15:53
  • 1
    $\begingroup$ @MansiTyagi You shouldn't be that sure, seriously. Your method can be great to give a supporting diagram to help to understand some reasoning, but it is not at all a proof and thus not an answer. $\endgroup$
    – DonAntonio
    Aug 6, 2020 at 7:51
  • $\begingroup$ @DonAntonio Thanks for pointing out my mistake.. I'm sorry..and i edited the explanation. $\endgroup$ Nov 26, 2021 at 8:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .