4
$\begingroup$

I'm convinced that

$$H_n \approx\log(n+\gamma) +\gamma$$ is a better approximation of the $n$-th harmonic number than the classical $$H_n \approx \log(n) +\gamma$$ Specially for small values of $n$. I leave some values and the error:

Table of values Table 2

Just to make things clearer, I calculate the value between two numbers as follows. Say $n$ is the optimal and $a$ is the apporximation, then $E = \frac{n-a}{n}$. $L_1$ stands for my approximation and $L_2$ for the classical one, and the errors $E_2$ and $E_1$ correspond to each of those (I mixed up the numbers).

It is clear that this gives an over estimate but tends to the real value for larger $n$.

So, is there a way to prove that the approximation is better?


NOTE: I tried using the \begin{tabular} environment but nothing seemed to work. Any links on table making in this site?

$\endgroup$
5
  • 1
    $\begingroup$ LaTeX text formatting commands usually don't work, but you could put your numbers in a \begin{array} or \begin{matrix}. It might be somewhat slow. $\endgroup$ Feb 3, 2012 at 3:14
  • $\begingroup$ I might be misunderstanding, but if you're trying to compute "relative error" of the two approximations, shouldn't you be doing $\left|\dfrac{(\text{approximation})-(\text{true value})}{\text{true value}}\right|$? From that, you can try to look at the asymptotic behavior of the two errors as $n\to\infty$... $\endgroup$ Feb 3, 2012 at 3:25
  • $\begingroup$ That's what I'm doing. I chose the largest first to get a positive number. $\endgroup$
    – Pedro
    Feb 3, 2012 at 12:01
  • $\begingroup$ meta: How do I insert a table when asking a question? $\endgroup$ Aug 4, 2012 at 8:59
  • $\begingroup$ @MartinSleziak Good to know. $\endgroup$
    – Pedro
    Aug 4, 2012 at 14:37

3 Answers 3

13
$\begingroup$

Actually, you do better still with $ H_n \approx \gamma + \log \left( n + \frac{1}{2} \right),$ with $$ H_n = \gamma + \log \left( n + \frac{1}{2} \right) + O \left( \frac{1}{n^2} \right). $$ As you can see from the other answers, this minimizes the error among approximations of type $H_n \approx \gamma + \log \left( n + c \right)$ with constant $c,$ by erasing the $\frac{1}{n} $ error term.

A fuller version of the asymptotic above is just

$$ H_n = \gamma + \log \left( n + \frac{1}{2} \right) + \frac{1}{24 \left( n + \frac{1}{2} \right)^2} - \frac{7}{960 \left( n + \frac{1}{2} \right)^4} + \frac{31}{8064 \left( n + \frac{1}{2} \right)^6} - \frac{127}{30720 \left( n + \frac{1}{2} \right)^8} + O \left( \frac{1}{n^{10}} \right). $$

$\endgroup$
5
  • 1
    $\begingroup$ $n+1/2$ is certainly easier to deal with than $n+\gamma$... :) $\endgroup$ Feb 3, 2012 at 3:47
  • $\begingroup$ @WillJagy Where do I find theory on such expansion? $\endgroup$
    – Pedro
    Feb 3, 2012 at 20:02
  • $\begingroup$ @Peter, the standard asymptotic (in powers of $\frac{1}{n}$) comes from the relationship with the digamma function, see en.wikipedia.org/wiki/… and the first formula in the section en.wikipedia.org/wiki/… I did the version with adding $(1/2)$ myself, but it is surely equivalent to the other. There is a good reason that adding $(1/2)$ will erase the first error term in any similar problem, but the explanation is intricate. $\endgroup$
    – Will Jagy
    Feb 3, 2012 at 21:27
  • $\begingroup$ Ok, thanks for the info. $\endgroup$
    – Pedro
    Feb 4, 2012 at 16:46
  • $\begingroup$ $H_n\approx log\left(2n+1\right)+\gamma-log(2)$ is better because $log(2)-\gamma < \gamma$. See math.stackexchange.com/a/1602945/134791 for a series linking $H_n$ and $log\left(2n+1\right)$ $\endgroup$ Jan 27, 2016 at 21:41
10
$\begingroup$

The asymptotic expansion of the Harmonic numbers $H_n$ is given by

$$\log n+\gamma+\frac{1}{2n}+\mathcal{O}\left(\frac{1}{n^2}\right).$$

The Maclaurin series expansion of the natural logarithm tells us $\log(1+x)=x+\mathcal{O}(x^2)$, and we can use this in your formula by writing $\log(n+\epsilon)=\log n+\log(1+\epsilon/n)$ and expanding:

$$\log(n+\gamma)+\gamma=\log n+\gamma\;\;\;+\frac{\gamma}{n}+\mathcal{O}\left(\frac{1}{n^2}\right).$$

Your approximation is asymptotically better than the generic one because the $\gamma=0.577\dots$ in its expansion is closer to the true coefficient $\frac{1}{2}$ than the illicit coefficient $0$ in the generic formula given by the usual $H_n\sim \log n +\gamma+0/n$. This also explains why it is asymptotically an over estimation.


As marty said in his answer, the expansion comes from the Euler-Maclaurin formula:

$$\sum_{n=a}^b f(n)=\int_a^b f(x)dx+\frac{f(a)+f(b)}{2}+\sum_{k=1}^\infty \frac{B_{2k}}{(2k)!}\left(f^{(2k-1)}(b)-f^{(2k-1)}(a)\right).$$

Here we let $a=1,b=n$ (rewrite the index to a different letter) and $f(x)=1/x$.

$\endgroup$
2
  • 1
    $\begingroup$ Maybe you can remove al the colours now. Asaf will be thankfull. $\endgroup$
    – Pedro
    May 15, 2012 at 16:28
  • 1
    $\begingroup$ As you wish. ${}$ $\endgroup$
    – anon
    May 15, 2012 at 18:40
3
$\begingroup$

The true approximation, from the Euler-Maclaurin formula, is $$H_n = \ln n + \gamma + 1/2n + O(1/n^2).$$

Your expansion is $\ln (n+\gamma) + \gamma = \ln \ n + ln(1+\gamma/n)+\gamma = \ln \ n + \gamma + \gamma/n + O(1/n^2) $.

Since $\gamma = .577...$, your error is about $.077/n$, which is better by .077/.5 ~ .154 ~ 1/6 which explains the table.

I see another answer has just been posted. If it differs much from mine, I will be surprised.

$\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.