# Finding the smallest integer $n$ such that $1+1/2+1/3+…+1/n≥9$?

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.

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

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.

-
... $H_n$ is the sum you are computing. – meh Apr 27 '13 at 19:52
This nails it: $e^{9-0.5772} \approx 4549.62$. – lhf Apr 27 '13 at 21:17
@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}}$$

-
Very nice, thanks a lot. – kiranovalobas 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
@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
@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.

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

-

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

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