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 am trying to find the smallest $n$ such that $1+1/2+1/3+....+1/n \geq 9$,

I wrote a program in C++ and found that the smallest $n$ is $4550$.

Is there any mathematical method to solve this inequality.

share|improve this question
    
See this section of the "harmonic series" entry in Wikipedia. –  amWhy Apr 27 '13 at 19:55

5 Answers 5

up vote 10 down vote accepted

What you are looking for is $H_n = \sum_{1 \le k \le n} k^{-1}$. It is known that $H_n \approx \ln n + \gamma - \dfrac{1}{12 n^2} + \dfrac{1}{120 n^4} - \dfrac{1}{252 n^6} + O\left(\dfrac{1}{n^8}\right)$, where $\gamma \approx 0.5772156649$ is Euler's constant.

share|improve this answer
    
... $H_n$ is the sum you are computing. –  meh Apr 27 '13 at 19:52
1  
This nails it: $e^{9-0.5772} \approx 4549.62$. –  lhf Apr 27 '13 at 21:17
1  
@julien Right, copied the signs wrong :-( In any case, the approximation without the series already gives enough to solve your question. This is an asymptotic series the error is less than the first omited term. –  vonbrand Apr 27 '13 at 21:49
    
@julien, note that $B_{2 n} \sim (-1)^n \left( \dfrac{n}{\pi e} \right)^{2 n}$, so the series does not converge. It can be shown that the error is less than the first term left out. –  vonbrand Apr 28 '13 at 13:16
    
Right, thanks. I found that on wikipedia afterwards. Can it really be shown that the error is less than the first term left out at every order? Will Jagy, who knows this formula pretty well, says this is for sure only for very little orders. And yes, it can be shown then. And even more. We have inequalities. That is the point of my answer, inspired by Will Jagy. And this is why it is not sufficient to just give an asymptotic expansion. The more difficult part comes after that. –  1015 Apr 28 '13 at 13:32

We have $$\sum_{k=1}^N \dfrac1k \sim \log(N) + \gamma + \dfrac1{N} - \dfrac1{12N^2} + \mathcal{O}(1/N^3)$$ We want the above to be equal to $9$, i.e., $$9 = \log(N) + \gamma + \dfrac1{N} - \dfrac1{12N^2} + \underbrace{\mathcal{O}(1/N^3)}_{\text{can be bounded by }1/N^3}$$ We have $\log(N) + \gamma < 9 \implies N \leq 4550$. Also, $\log(N) + \gamma +\dfrac1{N} > 9 \implies N \geq 4550$. Hence, $$N = 4550$$


Here is the asymptotic from Euler–Maclaurin. We have $$\sum_{k=a}^b f(k) \sim \int_a^b f(x)dx + \dfrac{f(a) + f(b)}2 + \sum_{k=1}^{\infty} \dfrac{B_{2k}}{(2k)!}\left(f^{(2k-1)}(b)-f^{(2k-1)}(a)\right)$$ In our case, we have $f(x) = \dfrac1x$, $a=1$ and $b=N$. This gives us $$\sum_{k=1}^N \dfrac1k \sim \log(N) + \gamma + \dfrac{1}{2N} - \sum_{k=1}^{\infty} \dfrac{B_{2k}}{2k}\dfrac1{N^{2k}}$$

share|improve this answer
    
Very nice, thanks a lot. –  Kamal Apr 27 '13 at 19:54
    
What if $O(1/N^3)=10^{10^{10}}/N^3$? I know it is not... –  1015 Apr 27 '13 at 20:03
    
@julien Valid point. But as you said, it is not. –  user17762 Apr 27 '13 at 20:12
4  
@WillJagy I am aware of the asymptotic exapnsion of the harmonic series...I am afraid you don't see my point. The problem is to know whether the remainder is $\leq \frac{1}{N^k}$ or $\leq \frac{10^{10^{10^{10}}}}{N^k}$. In the latter case, how do you find the first $n$ that makes your sequence greater than $9$ just looking at the truncation? –  1015 Apr 27 '13 at 20:25
1  
@WillJagy Do you really not see my point? I did not mean to bother anyone... –  1015 Apr 27 '13 at 20:52

The idea was given to me by Will Jagy. I am just writing it down because he suggested I do so.

Let $H_n:=\sum_{k=1}^n\frac{1}{k}$ the $n$-th harmonic number. It is known (see here or user17762's answer above) that $$ H_n=\ln n+\gamma+\frac{1}{2n}+O\left( \frac{1}{n^2}\right) $$ where $\gamma$ denotes Euler-Mascheroni constant. It is not sufficient to know that to answer your question. You need inequalities, or a precise control of the error term in the expansion. Here are two inequalities which suffice.

Claim: we have $$ S_n:=\ln n+\gamma <H_n< \ln n+\gamma+\frac{1}{2n}=:T_n $$ for all $n\geq 1$.

Application: with the lhs, a calculator, and $\gamma\simeq 0.5772156649$, we find $H_{4550}>9.00009817>9$. With the rhs, we get $H_{4549}<8.99998828<9$. So $n=4550$ is indeed the first such $n$.

Proof of the claim: first, let us show that $x_n:=H_n-S_n$ decreases. Indeed $$ x_n-x_{n+1}=-\ln n+\ln(n+1)-\frac{1}{n+1}=-\ln\left(1-\frac{1}{n+1} \right)-\frac{1}{n+1}>0 $$ where the last inequality follows for instance from the study of $f(x)=-\ln(1-x)-x$ on $(0,1)$. Since $\lim x_n=0$, it follows that $x_n>0$ for all $n\geq 1$. That is the lhs inequality.

Now let $y_n:=H_n-T_n$ and let us check that it increases. We have $$ y_{n+1}-y_n=\frac{1}{2(n+1)}+\frac{1}{2n}-\ln\left(1+\frac{1}{n}\right)>0 $$ where the inequality follows from the fact that the corresponding function of $x$, instead of $n$, is decreasing on $(0,+\infty)$ with limit $0$ at $+\infty$. So $y_n$ is increasing with limit $0$. This means that $y_n<0$ for all $n\geq 1$, which proves the rhs inequality. QED.

share|improve this answer
    
@WillJagy Here it is. Actually, I took a lazier path which suffices. Please let me know if there is anything wrong. Thanks a lot for showing me these inequalities. –  1015 Apr 27 '13 at 23:42
    
That's right. The fact that this is decisive for threshold 9 is somewhat a matter of luck. The usual practice is to get the size of the window an extra order smaller then the last term added, that being $1/n$. In this case, that would mean considering your $T_n$ and $U_n = T_n - \frac{1}{12 n^2}.$ For example, what you have written does not suffice to find the first $H_n$ that exceeds 2, or exceeds 3, or 5, or 12. –  Will Jagy Apr 28 '13 at 1:37
    
@WillJagy Yes. I started doing it with the order $2$ on the left and $4$ on the right. But I took a little break in doing so, which was more cumbersome, to try some computations. And I was surprised to see that these easier estimates suffice. –  1015 Apr 28 '13 at 2:14
    
Well, if you do one more step, (and I recommend just the one additional) you will find that, as is common for strictly alternating asymptotic series, the true value is bounded between consecutive terms in the asymptotic series. This is not guaranteed when all you have is an asymptotic series, but is guaranteed for strictly alternating convergent infinite series. So you see, I was never worried about the issue that bothered you. –  Will Jagy Apr 28 '13 at 2:46
    
@WillJagy As I don't know Bernoulli numbers very well, I don't know that $\frac{|B_{2k}|}{2kN^{2k}}$ is nonincreasing. Otherwise, I would not have worried about that either as I know Leibniz criterion and its consequences. Is it really straightforward to see that the latter is nonincreasing? –  1015 Apr 28 '13 at 2:50

In case you do not understand vonbrand and user17762's reasoning, both are using the fact that $\int_1^n \frac{dk}{k}=\ln{n}$, and that a sum can be approximated by an integral (for large n values) with a correcting factor. Here the correcting factor is $\gamma$, the Euler-Mascheroni constant.

share|improve this answer

You can look up "digamma function" for more info. A version I made up myself, which uses a symmetry property to give every other power, is $$ H_n = \log \left( n + \frac{1}{2} \right) + \gamma + \frac{1}{6(2n+1)^2} - \frac{7}{60(2n+1)^4} + \frac{31}{126(2n+1)^6} - \frac{127}{120(2n+1)^8} + \frac{511}{66(2n+1)^{10}} - O \left( \frac{1}{(2n+1)^{12}} \right) $$ with $$ \gamma = 0.5772156649015328606065... $$

I put part of this in my programmable calculator, just the 1/6 blah - 7/60 blahblah. Because of the alternating signs, this is definitive, too small with $n=4549,$ big enough with $n=4550.$ There is no guarantee the $\pm$ signs continue to alternate, and the rational coefficients are allowed to grow, note $511/66 \approx 7.74. $ The use of asymptotic expansions is to truncate at a convenient place and know enough about the possible error. Interesting to put this on a high precision program, with extremely high precision demanded for $\gamma,$ and look at the error of what I wrote multiplied by $(2n+1)^{12}.$

share|improve this answer
    
@julien, I think you should post your own answer. –  Will Jagy Apr 27 '13 at 20:47

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.