4
$\begingroup$

Let $H_n$ denote the partial harmonic sum

$$H_n = \sum_{j=1}^n \frac{1}{j} \ \ .$$

I saw in some lecture notes that $H_n \approx \ln(n)$ without any explanation given. I tried to understand this approximation using Taylor series. Recall that the Taylor expansion of $\ln(x)$ for $x>0$ is

$$\ln(x) = 2 \sum_{j=1}^{\infty} \frac{ \bigg[ \displaystyle\frac{(x-1)}{(x+1)} \bigg]^{(2j-1)} }{2j-1} \ \ .$$

I tried to use this to obtain the connection, however I was unable to see the relationship between $H_n$ and $\ln(n)$.

I performed some crude numerical calculations and I'm not sure whether the approximation is correct because $H_n$ does not appear to be close to $\ln(n)$ for the values of $n$ that I have tried.

Can someone please help me understand this approximation or confirm my suspicions that there is an error in the notes.

If there is an error in the notes, does a relationship exist between the partial harmonic sum and the logarithm however?

$\endgroup$

2 Answers 2

5
$\begingroup$

Claim: $$H_n = \ln n + C + O\left(\frac{1}{n}\right)$$ where $C$ is the Euler–Mascheroni constant ($=0.5772156649...$)

Proof: For any natural $k$ and $x$ such that $k-1 \le x < k$, we have $[x] = k-1$. Hence, we also have $$\frac{1}{k} = \frac{1}{[x] + 1}$$ Therefore, $$\frac 1k = \int_{k-1}^k \frac 1k dx = \int_{k-1}^k \frac{dx}{[x]+1}$$ Now, summing the above equality from $1$ to $n$, we get $$\sum_{k=1}^n\frac 1k = \sum_{k=1}^n\int_{k-1}^k \frac 1k dx = \int_{0}^n \frac{dx}{[x]+1}$$ We subtract the following equality from the above one: $$\ln(n+1) = \int_0^n \frac{dx}{x+1}$$ to get $$\sum_{k=1}^n \frac 1k - \ln(n+1) = \int_0^n \left( \frac{1}{[x]+1} - \frac{1}{x+1}\right)dx = \int_0^n \frac{x - [x]}{([x]+1)(x+1)}dx =: C_n$$ We denote $C = \lim C_n$ since $0 \le x-[x] < 1$ implies $$0 \le \frac{x - [x]}{([x]+1)(x+1)} < \frac{1}{x^2}, \ \ x\ge 1$$ which implies the improper integral (note: $\lim C_n$ was an improper integral) is convergent. Now, if we integrate the above inequality from $n$ to $\infty$, we get $$0 \le \int_n^\infty \frac{x - [x]}{([x]+1)(x+1)}dx \le \int_n^\infty \frac{dx}{x^2} = \frac 1n$$ Hence, we have $$\int_0^n \frac{x - [x]}{([x]+1)(x+1)}dx = C + O\left(\frac 1n\right), \ \ n\in \mathbb N$$ Therefore, we conclude $$\sum_{k=1}^n \frac{1}{k} = \ln(n+1) + C + O\left(\frac 1n\right)$$ Finally, noting that $\ln(n+1) = \ln n + O(1/n)$ completes the proof. $\square$

$\endgroup$
6
  • $\begingroup$ is $[x]$ the floor of $x$ (i.e.$\lfloor x \rfloor$ ) Is there a special name for $C$? $\endgroup$
    – NM_
    Dec 24, 2020 at 9:26
  • $\begingroup$ Side note : this $C$ is known as the Euler Mascheroni constant. $\endgroup$
    – Anthony
    Dec 24, 2020 at 9:27
  • $\begingroup$ @NM_ Yes, added the name. Anthony, thanks. $\endgroup$
    – VIVID
    Dec 24, 2020 at 9:28
  • $\begingroup$ Very elegant solution, $\sqrt{i \sqrt{i d}}$ ! Merry Xmas $\endgroup$ Dec 24, 2020 at 10:08
  • 1
    $\begingroup$ @VIVID. Me neither ! Moreover, I hate this time of the year. Cheers :-) $\endgroup$ Dec 24, 2020 at 10:16
2
$\begingroup$

You may also use creative telescoping by noticing that $\frac{1}{k}$ is pretty close to $\log(k+1)-\log(k)=\log\left(1+\frac{1}{k}\right)$ for any large $k$. Indeed

$$ H_n -\log(n+1) = \sum_{k=1}^{n}\underbrace{\left(\frac{1}{k}-\log\left(1+\frac{1}{k}\right)\right)}_{\Theta(1/k^2)}=O(1) $$ and the approximation can be further improved by noticing that $\frac{1}{k}-\log\left(1+\frac{1}{k}\right)$ is pretty close to $\log\left(\frac{12k+1}{12k-5}\right)-\log\left(\frac{12k+13}{12k+7}\right)$:

$$ H_n = \log(n+1)+\gamma-\sum_{k>n}\left(\frac{1}{k}-\log\left(1+\frac{1}{k}\right)\right) $$

$$ H_n = \log(n+1)+\gamma-\log\left(\frac{12n+13}{12n+7}\right)+\sum_{k>n}\left(\frac{1}{k}-\log\left(1+\frac{1}{k}\right)-\log\left(\frac{12k+1}{12k-5}\right)-\log\left(\frac{12k+13}{12k+7}\right)\right) $$

$$\boxed{H_n=\log(n+1)+\gamma+\log\left(\frac{12n+7}{12n+13}\right)+O\left(\frac{1}{n^3}\right)}$$

where $\gamma$ is the Euler-Mascheroni constant, corresponding to $\sum_{k\geq 1}\left(\frac{1}{k}-\log\left(1+\frac{1}{k}\right)\right)$.

$\endgroup$

You must log in to answer this question.

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