Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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. –  Dylan Moreland Feb 3 '12 at 3:14
    
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$... –  J. M. Feb 3 '12 at 3:25
    
That's what I'm doing. I chose the largest first to get a positive number. –  Pedro Tamaroff Feb 3 '12 at 12:01
    
    
@MartinSleziak Good to know. –  Pedro Tamaroff Aug 4 '12 at 14:37
add comment

3 Answers

up vote 12 down vote accepted

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

share|improve this answer
1  
$n+1/2$ is certainly easier to deal with than $n+\gamma$... :) –  J. M. Feb 3 '12 at 3:47
    
@WillJagy Where do I find theory on such expansion? –  Pedro Tamaroff Feb 3 '12 at 20:02
    
@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. –  Will Jagy Feb 3 '12 at 21:27
    
Ok, thanks for the info. –  Pedro Tamaroff Feb 4 '12 at 16:46
add comment

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

share|improve this answer
1  
Maybe you can remove al the colours now. Asaf will be thankfull. –  Pedro Tamaroff May 15 '12 at 16:28
1  
As you wish. ${}$ –  anon May 15 '12 at 18:40
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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