# Can one show that $\sum_{n=1}^N\frac{1}{n} -\log N - \gamma \leqslant \frac{1}{2N}$ without using the Euler-Maclaurin formula?

I would like to prove that $$\sum_{n=1}^N\frac{1}{n} -\log N - \gamma \leqslant \frac{1}{2N}$$ without using the Euler-Maclaurin summation formula. The motivation for this is that I have come very close to doing so (see the answer provided below) but annoyingly have not actually proved the above.

Some may ask why I don't just use the formula. I'm writing a set of analytic number theory notes for my own use and it seems an unwieldy result to introduce and prove, given that the above inequality is all I need, and given that I have gotten so close without using Euler-Maclaurin!

-

Let $$\gamma_n = \sum_{k=1}^n \frac{1}{k} - \log n.$$ Our goal is to show that $$\gamma_n - \lim_{m \to \infty} \gamma_m \leq \frac{1}{2n}.$$ It is enough to show that, for $n<m$, we have $$\gamma_n - \gamma_m \leq \frac{1}{2n}.$$ This has the advantage of dealing solely with finite quantities.

Now, $$\gamma_n - \gamma_m = \int_{n}^m \frac{dt}{t} - \sum_{k=n+1}^m \frac{1}{k} =\sum_{j=n}^{m-1} \int_{j}^{j+1} \left( \frac{1}{t} - \frac{1}{j+1} \right) \cdot dt .$$

At this point, if I were at a chalkboard rather than a keyboard, I would draw a picture. Draw the hyperbola $y=1/x$ and mark off the interval between $x=n$ and $x=m$. Divide this into $m-n$ vertical bars of width $1$. Each bar stretches up to touch the hyperbola at its right corner. There is a little wedge, bounded by $x=j$, $y=1/(j+1)$ and $y=1/x$. We are adding up the area of each of these wedges.1

Because $y=1/x$ is convex, the area of this wedge is less than that of the right triangle with vertices at $(j,1/(j+1))$, $(j+1, 1/(j+1))$ and $(j,1/j)$. This triangle has base $1$ and height $1/j - 1/(j+1)$, so its area is $(1/2) (1/j - 1/(j+1))$. So the quantity of interest is $$\leq \sum_{j=n}^{m-1} \frac{1}{2} \left( \frac{1}{j} - \frac{1}{j+1} \right) = \frac{1}{2} \left( \frac{1}{n} - \frac{1}{m} \right) \leq \frac{1}{2n}.$$

Of course, this is just a standard proof of Euler-Maclaurin summation, but it is a lot more geometric and easy to follow in this special case.

1 By the way, since this area is positive, we also get the corollary that $\gamma_n - \gamma_m > 0$, so $\gamma_n - \gamma >0$, another useful bound.

-
(+1) Just to point out a typo: In "Draw the hyperbola y=1/x and mark off the interval between x=n and x=n.", the second n should be an m. – John Bentin Jun 9 '11 at 13:52
It is really annoying. This is exactly the kind of geometric proof I went for, using areas, and I always failed! Thanks for showing how it's done +1. – Sputnik Jun 18 '11 at 10:20

One can check that $S(N):=\sum_{n=1}^N\frac{1}{n} -\log N - \gamma = \int_N^\infty \frac{x-[x]}{x^2} \: dx$, where $[x]$ is the integer part of $x$. Moreover $$\int_n^{n+1} \frac{x-[x]}{x^2}\: dx = \log\Big(\frac{n+1}{n}\Big) - \frac{1}{n+1} < \frac{1}{n} - \frac{1}{n+1} -\frac{1}{2n^2} +\frac{1}{3n^3}, \qquad (1)$$ by the Taylor series for $\log(1+x)$. But we have that $$n(n+1)(3n-1) = 3n^3 + 2n^2 -n > 3n^3$$ so $$\frac{1}{n(n+1)} < \frac{3n-1}{3n^3} = \frac{1}{n^2} - \frac{1}{3n^3}.$$ Therefore, from equation $(1)$ we find $$S(N) < \sum_{n=N}^\infty \frac{1}{n(n+1)} -\frac{1}{2n^2} +\frac{1}{3n^3} < \sum_{n=N}^\infty \frac{1}{n^2} - \frac{1}{3n^3} -\frac{1}{2n^2} +\frac{1}{3n^3},$$ and so finally, $$S(N) < \frac{1}{2}\sum_{n=N}^\infty \frac{1}{n^2} < \frac{1}{2(N-1)},$$ for all $N \in \mathbb{N}$, by a standard approximation for $\sum \frac{1}{n^2}$.

-
By the way, does the difference between $1/2(N-1)$ and $1/2N$ really matter? Unless you are heading for hard bounds in the end, I would guess that $1/2N + O(1/N^2)$ is good enough for whatever you want, and you already have that. – David Speyer Jun 9 '11 at 12:11
@David: I'll admit that it doesn't really matter, but it is just nicer to be able to write that something is $O(\frac{1}{N})$ with a simple implied constant like $\frac{1}{2}$, which is actually the best possible constant as well. I guess it was more a matter of elegance for me! – Sputnik Jun 18 '11 at 10:18

What follows is a variant of the method suggested by Fahad Sperinck, which almost gave the desired bound. Although we obtain a pretty short proof of the inequality, I think that the "right" proof is the one in the post by David Speyer. (A proof based on geometry is "right," as is a combinatorial proof.)

Let us start as Fahad Sperinck did, from $$\int_n^{n+1} \frac{x-[x]}{x^2}\: dx = \log\Big(\frac{n+1}{n}\Big) - \frac{1}{n+1} < \frac{1}{n} - \frac{1}{n+1} -\frac{1}{2n^2} +\frac{1}{3n^3}.$$

Ultimately, we will summing from $N$ to infinity. If we keep this fact in mind, the chunk $$\frac{1}{n}-\frac{1}{n+1}$$ sums beautifully to $1/N$, and should be left as is. If we could show that the part that is taken away, namely $$\frac{1}{2n^2}-\frac{1}{3n^3}$$ is bigger than $$\frac{1}{2}\left(\frac{1}{n}-\frac{1}{n+1}\right),$$ we would be finished.

Now I will do some unofficial scribbling, don't look. I want to show that $1/2n^2-1/3n^3 \ge 1/2(n)(n+1)$, so I want to show that $(3n-2)/6n^3\ge 1/2n(n+1)$, so I want to show that $(3n-2)/3n^2 \ge 1/(n+1)$, so I want to show that $(3n-2)(n+1) \ge 3n^2$, and this is clearly true if $n \ge 2$, just multiply out the stuff on the left.

Now if I had the energy I would hide my tracks, and have the desired inequality drop out as if by magic.

Comment: Somehow, one acquires the habit of thinking of $n^2$ and $1/n^2$ as "nice" and of $n(n+1)$ and $1/n(n+1)$ as not so nice. In many ways, the opposite is true. Certainly that is the case from the combinatorial point of view.

The calculations in the post were fine, the problem was that of giving away a tiny bit too much. That was, maybe, because the strategy was directed at getting to something that looks like $1/n^2$, which was viewed as tractable and desirable. But $1/n(n+1)$, aka $1/n-1/(n+1)$, arises naturally in the problem, and is much more tractable.

-
Nice exposition! I am a big fan of Penn and Teller's videos where they do magic tricks while showing you how they are done, and this has the same feel. – David Speyer Jun 9 '11 at 14:41
The beauty, clarity and simplicity of your posts are such an enrichment of this site. Many thanks for all the time and effort you invest in your contributions. – t.b. Aug 10 '11 at 14:05