25
$\begingroup$

How to show that $$\lim_{n\to\infty}\left[\sum^n_{k=1}\frac{1}{k}-\ln(n)\right]=0.5772\ldots$$

No clue at all. Need help! Appreciated!

$\endgroup$
  • 1
    $\begingroup$ Did you mean $\ln n$ rather than $\ln x$? $\endgroup$ – Michael Hardy Mar 28 '13 at 1:36
  • $\begingroup$ my bad, I'll correct it $\endgroup$ – user67253 Mar 28 '13 at 1:37
  • $\begingroup$ en.wikipedia.org/wiki/Euler%E2%80%93Mascheroni_constant $\endgroup$ – Dylan Yott Mar 28 '13 at 1:42
  • $\begingroup$ I give one of the shorter proofs here: math.stackexchange.com/questions/306371/… $\endgroup$ – Will Jagy Mar 28 '13 at 2:04
  • 2
    $\begingroup$ You mean $\color{Red}{=} \gamma \color{Red}{\approx} 0.5772$. Most often this is the definition of the Euler-Mascheroni constant $\gamma$ - so were you looking to show the limit exists or do you have a different definition of the constant? $\endgroup$ – anon Mar 28 '13 at 2:57
35
$\begingroup$

Showing that $\displaystyle\lim_{n\to\infty}\left(\sum_{k=1}^n\frac1k-\log(n)\right)$ exists

Note that $$ \frac1{n+1}\le\int_n^{n+1}\frac1x\,\mathrm{d}x\le\frac1n\tag{1} $$ Summing the right hand inequality shows that $$ \sum_{k=1}^n\frac1k-\log(n+1)\tag{2} $$ is increasing. Summing the left hand inequality shows that $$ \sum_{k=1}^n\frac1k-\log(n)\tag{3} $$ is decreasing.

Since $\displaystyle\lim_{n\to\infty}\log\left(\frac{n+1}{n}\right)=0$, $(2)$ and $(3)$ show that $\displaystyle\gamma=\lim_{n\to\infty}\left(\sum_{k=1}^n\frac1k-\log(n)\right)$ exists and is between $0$ and $1$.


Evaluating $\gamma$

Define the Harmonic Numbers $$ H(n)=1+\frac12+\frac13+\frac14+\dots+\frac1n\tag{4} $$ and the Alternating Harmonic Numbers $$ AH(n)=1-\frac12+\frac13-\frac14+\dots+(-1)^{n-1}\frac1n\tag{5} $$ and the Alternating Harmonic Tails $$ AHT(n)=\frac1{n+1}-\frac1{n+2}+\frac1{n+3}-\frac1{n+4}+\dots\tag{6} $$ Remember that $$ \begin{align} \log(2)&=1-\frac12+\frac13-\frac14+\frac15-\frac16+\dots\\ &=AH(n)+(-1)^nAHT(n)\tag{7} \end{align} $$ Notice that for $n\gt0$, $$ \begin{align} &H(2^n)-H(2^{n-1})\\ &=\left(1+\frac12+\frac13+\frac14+\dots+\frac1{2^n}\right)-\left(1+\frac12+\frac13+\frac14+\dots+\frac1{2^{n-1}}\right)\\ &=\left(1+\frac12+\frac13+\frac14+\dots+\frac1{2^n}\right)-\left(\frac22+\frac24+\frac26+\frac28+\dots+\frac2{2^n}\right)\\ &=\left(1-\frac12+\frac13-\frac14+\dots-\frac1{2^n}\right)\\ &=AH(2^n)\tag{8} \end{align} $$ Therefore, $$ \begin{align} H(2^n) &=1+\sum_{k=1}^n\left(H(2^k)-H(2^{k-1})\right)\\ &=1+\sum_{k=1}^nAH(2^k)\tag{9} \end{align} $$ Because $\displaystyle\gamma=\lim_{n\to\infty}\Big(H(2^n)-\log(2^n)\Big)$, subtract $n\log(2)$ from $(9)$ and rearrange terms to get $$ H(2^n)-\log(2^n) =1+\sum_{k=1}^n\left(AH(2^k)-\log(2)\right)\tag{10} $$ For $k\gt0$, $2^k$ is even, so we have from $(7)$ $$ \log(2)-AH(2^k)=AHT(2^k)\tag{11} $$ Using $(10)$ and $(11)$, we get $$ \gamma=1-\sum_{k=1}^\infty AHT(2^k)\tag{12} $$ Expedite the computation of $(12)$ using the following integral, $$ \begin{align} AHT(m) &=\sum_{j=1}^\infty\frac{(-1)^{j-1}}{m+j}\\ &=\int_0^1\frac{x^m}{1+x}\,\mathrm{d}x\\ &=\sum_{j=1}^\infty\frac1{j\binom{m+j}{j}2^j}\tag{13} \end{align} $$ where the last sum in $(13)$ is gotten by repeatedly integrating by parts. It converges far more quickly than the alternating harmonic tail, two lines above.

Using $(12)$ and $(13)$, it is not unreasonable to compute $$ \gamma=0.57721566490153286060651209\tag{14} $$ In fact, I used $(12)$ and $(13)$ to compute $10000$ digits of $\gamma$.


A Slightly Different Sum

Since $AHT(2^k-1)=2^{-k}-AHT(2^k)$, we can rewrite $(12)$ as $$ \gamma=\sum_{k=1}^\infty AHT(2^k-1)\tag{15} $$ and use $(13)$ and $(15)$ to get $(14)$, as well.


A Mathematica Implementation

Here is an implementation of the algorithm above to compute $d$ digits of $\gamma$.

AHT[m_,d_]:=Module[{p=10^(d+2), j=1, b=1, t, s=SetPrecision[1,d+4]-1}, While[b=b*2(m+j)/j; (t=j b)<=p, s=s+1/t; j=j+1]; SetPrecision[s,d]]

EulerG[d_]:=Module[{n=Ceiling[10d/3]}, Sum[AHT[2^k-1,d], {k,1,n}]]

$\endgroup$
13
$\begingroup$

Abel's partial summation technique:

Let $A(n) = \displaystyle \sum_{k=1}^n a(k)$. We then have \begin{align*} \sum_{n=1}^{N} a(n) f(n) & = \sum_{n=1}^{N} f(n) (A(n)- A(n-1)) = \sum_{n=1}^{N} A(n) f(n) - \sum_{n=1}^{N} A(n-1) f(n)\\ & = \sum_{n=1}^{N} A(n)f(n) - \sum_{n=0}^{N-1} A(n) f(n+1)\\ & = A(N)f(N) - A(0) f(1) - \sum_{n=1}^{N-1} A(n) (f(n+1)-f(n)) \end{align*} (The above is nothing but the discrete version of integration by parts).

$$\sum_{n=1}^{N} a(n) f(n) = \int_{1^-}^{N^+} f(t) d(A(t)) = f(t) A(t) \rvert_{1^-}^{N^+} - \int_{1^-}^{N^+} A(t) f'(t) dt$$ (The second integral can be interpreted as a Riemann-Stieltjes integral.)


Now to the main proof. Consider the sum $\displaystyle \sum_{n \leq N} \frac1n$. Choose $a(n) = 1$ and $f(n) = \frac1n$. Note that we have $A(t) = \lfloor t \rfloor = t - \{t\}$. Hence, we get that \begin{align*} \sum_{n \leq N} \frac1n & = \left. \frac{t-\{t\}}t \right \rvert_{1^-}^{N^+} + \int_{1^-}^{N^+} \frac{(t-\{t\})}{t^2} dt\\ & = 1 + \int_{1^-}^{N^+} \frac{dt}t - \int_{1^-}^{N^+} \frac{\{t\}}{t^2} dt\\ & = 1 + \log (N) - \int_{1^-}^{\infty} \frac{\{t\}}{t^2} dt + \int_{N^+}^{\infty} \frac{\{t\}}{t^2} dt\\ & = \left(1 - \int_{1^-}^{\infty} \frac{\{t\}}{t^2} dt \right) + \log(N) + \int_{N^+}^{\infty} \frac{\{t\}}{t^2} dt \end{align*} Note that $\displaystyle \int_{N^+}^{\infty} \frac{\{t\}}{t^2} dt \leq \int_{N^+}^{\infty} \frac{1}{t^2} dt = \frac1N$.

Also note that by the same argument, we also have that $\displaystyle 0 < \int_{1^-}^{\infty} \frac{\{t\}}{t^2} dt < 1$ and hence $\displaystyle 0 < \left(1 - \int_{1^-}^{\infty} \frac{\{t\}}{t^2} dt \right) < 1$. Denoting $\displaystyle \left(1 - \int_{1^-}^{\infty} \frac{\{t\}}{t^2} dt \right) = \gamma$, we get the following result. $$\sum_{n \leq N} \frac1n = \gamma + \log(N) + \mathcal{O} \left(\frac1N \right)$$ $\gamma \approx 0.5772\ldots$ and is called the Euler-Mascheroni constant. Hence, we have $$\lim_{n \to \infty} \left(\sum_{k = 1}^n \dfrac1k - \log(n) \right) = \displaystyle \left(1 - \int_{1^-}^{\infty} \frac{\{t\}}{t^2} dt \right) = \gamma \approx 0.5772$$


We can easily see that $\gamma$ must be greater than $\dfrac12$ from the figure below. $\gamma$ is the area between the blue curve, which is $\displaystyle \dfrac1{\lfloor x \rfloor}$ and the red curve, which is $\dfrac1x$. The curve $\dfrac1x$ between $(n,n+1)$ lies below the line segment joining $\left(n,\dfrac1n \right)$ and $\left(n+1, \dfrac1{n+1} \right)$. Hence, \begin{align} \gamma & = \text{Area between the blue and red curve}\\ & \geq \text{Area between the blue curve and the curve formed by the line segments }\\ & \text{joining $\left(n,\dfrac1n \right)$ and $\left(n+1, \dfrac1{n+1} \right)$}\\ & = \dfrac12 \times 1 \times \left(1-\dfrac12 \right) + \dfrac12 \times 1 \times \left(\dfrac12 - \dfrac13\right) + \dfrac12 \times 1 \times \left(\dfrac13 - \dfrac14\right) + \cdots\\ & = \dfrac12 \left(1 - \dfrac12 + \dfrac12 - \dfrac13 + \dfrac13 - \dfrac14 \pm\right) = \dfrac12 = 0.5 \end{align}

enter image description here

$\endgroup$

Your Answer

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