# Proof $\sum\limits_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} +O\left(\frac1{\log^2 n}\right)$

More precisely,

$$\sum_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} -\frac{\pi^2 + 6 \gamma^2}{12 \log^2 n} +O\left(\frac1{\log ^3 n}\right).$$

This is Theorem 4 from Flajolet, Sedgewick (1995) and was obtained using Hankel integration. It is related to analysis of quadtrees and digital search trees.

I know from 'Concrete Mathematics' that similar-looking sums can be obtained and solved using discrete form of derivatives, $\nabla f(x)=f(x+1)-f(x)$ and so $n^{\text{th}}$ difference is

$$\nabla^n f(x)=\sum_{k=0}^{n} \binom{n}{k} (-1)^{n-k} f(x+k)$$

and I know how to use it for simple functions such as $f(x)=\dfrac1{x}$, but I have no idea how solve something like the one above.

-
Are you asking for a proof at the level of the Concrete Mathematics book? Maybe there is one, but then one needs to ask why Flajolet and Sedgewick chose to use Hankel integration. So maybe there isn't one. –  Gerry Myerson Sep 16 '11 at 5:36
For the record, $\sum_{k=1}^n \binom{n}{k} (-1)^k H_k = - \frac{1}{n}$. So approximating $\log k$ by the $k$th harmonic number doesn't give you the same asymptotically dominant term. –  Mike Spivey Sep 16 '11 at 5:38
@Srivatsan: Given the 1995 citation year, the cited theorem would come from this paper. –  Ｊ. Ｍ. Sep 16 '11 at 15:21
Here's an idea that hopefully someone with better manipulational skill than me can finish: if you replace the logarithm with the Frullani integral, you obtain the integral $$\int_0^\infty \frac{1-\exp(-t)-(1-\exp(-t))^n}{t}\mathrm dt$$. That might be a bit more tractable manipulationally... –  Ｊ. Ｍ. Sep 16 '11 at 15:41
If $f(x)=1/x$ is simple to use here's the expression :) $$\sum_{k=1}^n \binom{n}{k}(-1)^k \log k= \int_0^1 \sum _{k=1}^{n-1}\binom{n-1}{k} \frac{(-1)^{k-1}}{k+x} \, dx= \int_0^1 \left(\frac{1}{x}-\frac{\Gamma (n) \Gamma (x)}{\Gamma (n+x)}\right) \, dx.$$ –  Andrew Sep 16 '11 at 17:22

Thanks go to Andrew, J. M., and David Speyer! The following solution leans heavily on what these three have already posted.

(In the interest of having a complete solution I've added the argument that gets from the OP's sum to Andrew's reformulation of it.)

Part 1: Getting to Andrew's gamma function formula.

Since $$\int_0^1\sum_{m=1}^{k-1}\frac1{x+m}\, dx = \sum_{m=1}^{k-1}(\log(m+1) - \log m) = \log k,$$ we can rewrite the original formula as $$\sum_{k=1}^n \binom{n}{k}(-1)^k \log k= \sum_{k=2}^n \binom{n}{k}(-1)^k\int_0^1\sum_{m=1}^{k-1}\frac1{x+m}\, dx = \int_0^1 \sum_{m=1}^{n-1} \frac1{x+m} \sum_{k=m+1}^n \binom{n}{k}(-1)^k\, dx.$$ Since alternating row sums of binomial coefficients are easy to evaluate (see, for instance, Concrete Mathematics, Identity 5.16), this becomes (and then switching the index back to $k$) $$\int_0^1 \sum_{m=1}^{n-1} \frac1{x+m} (-1)^{m-1} \binom{n-1}{m}\, dx = \int_0^1 \sum _{k=1}^{n-1}\binom{n-1}{k} \frac{(-1)^{k-1}}{k+x} \, dx$$ $$= \int_0^1 \left(\frac{1}{x} - \sum _{k=0}^{n-1}\binom{n-1}{k} \frac{(-1)^k}{k+x}\right) \, dx.$$ The remaining binomial sum is actually the partial fractions decomposition of $\frac{(n-1)!}{x(x+1)\cdots (x+n-1)}$. (This is identity 5.41 in Concrete Mathematics. From another perspective - also discussed in Concrete Mathematics - the binomial sum is $(-1)^n$ times the $n-1$ difference of $\frac{1}{x} = (x-1)^{\underline{-1}}$. Applying the finite difference rule $\Delta x^{\underline{m}} = m x^{\underline{m-1}}$ successively $n-1$ times thus gets us to $\frac{(n-1)!}{x(x+1)\cdots (x+n-1)}$.)

Thus our original sum is equivalent to $$\int_0^1 \left(\frac{1}{x} - \frac{(n-1)!}{x(x+1)\cdots (x+n-1)}\right) dx = \int_0^1 \left(\frac{1}{x} - \frac{\Gamma(n) \Gamma(x)}{\Gamma(n+x)}\right) dx,$$ which is the formula Andrew mentions in the comments.

Part 2: Rewriting the expression.

Now, rewrite like so: $$\int_0^1 \left( \frac{1}{x} - \frac{\Gamma(n) \Gamma(x)}{\Gamma(n+x)} \right) dx = \int_0^1 \left( \frac{1}{x}\left(1- \frac{\Gamma(n) \Gamma(x+1)}{\Gamma(n+x)} \right)\right) dx.$$

For $0 < x < 1$, $$\Gamma(x+1) = 1 - \gamma x + \frac{\zeta(2) + \gamma^2}{2}x^2 + O(x^3).$$ (This is the Maclaurin series for $\Gamma(x+1)$; see Expression 8.321 in Gradshteyn and Ryzhik. The only reason I know this is because I had to track it down for a paper I wrote a couple of years ago.) Also, $$\frac{\Gamma(n)}{\Gamma(n+x)} = n^{-x}\left(1 + O\left(\frac{1}{n}\right)\right).$$ (See the DLMF.)

Putting all this together means we want the asymptotic value of $$\int_0^1 \frac{1-n^{-x}\left(1+ O\left(\frac{1}{n}\right)\right)\left(1 - \gamma x + \frac{\zeta(2) + \gamma^2}{2}x^2 + O(x^3)\right)}{x} dx. \tag{1}$$

Part 3: Obtaining the dominant terms.

Following David Speyer and J.M., we'll first extract what turns out to be the dominant part of (1): $$\int_0^1 \frac{1-n^{-x}}{x}dx = \int_0^1 \frac{1-e^{-x \log n}}{x}dx = \int_0^{\log n} \frac{1-e^{-u}}{u} du = \text{Ein}(\log n),$$ where $\text{Ein}(x)$ is the complementary exponential integral. Now, $\text{Ein}(x) = E_1(x) + \log x + \gamma$, where $E_1(x)$ is the usual exponential integral (again, see the DLMF), and $E_1(x) < e^{-x} \log (1 + 1/x)$ (DLMF once again), so putting all of this together we have $$\int_0^1 \frac{(1-n^{-x})}{x}dx = \log \log n + \gamma + O\left(\frac{1}{n}\right).$$

Part 4: Obtaining the remaining terms.

Now we consider the rest of (1). This is $$\left(1+ O\left(\frac{1}{n}\right)\right)\int_0^1 n^{-x}\left(\gamma - \frac{\zeta(2) + \gamma^2}{2}x + O(x^2)\right) dx$$ $$=\left(1+ O\left(\frac{1}{n}\right)\right)\left(\gamma \left(\frac{n-1}{n \log n}\right) - \frac{\zeta(2) + \gamma^2}{2}\left(\frac{n - \log n -1}{n (\log n)^2}\right) + O\left(\frac{1}{(\log n)^3}\right)\right)$$ $$=\frac{\gamma }{\log n} - \frac{\zeta(2) + \gamma^2}{2(\log n)^2} + O\left(\frac{1}{(\log n)^3}\right),$$ which is the rest of the expression requested by the OP.

-
Looks good! One small correction: Note that $\int_0^1 (1-n^{-x})/x dx$ is not equal to $\log \log n + \gamma$, rather, its equal to that plus an error coming from changing the upper bound in JM's integral from $\log n$ to $\infty$. So that's one more error term to keep track of. –  David Speyer Sep 17 '11 at 22:48
@David: I added the error term and cleaned up that part of the argument. Thanks again for catching my omission. –  Mike Spivey Sep 18 '11 at 3:24
I sure wish I could upvote this more than once. The series for the gamma function is new to me (and I'm surprised the DLMF has no mention of it); I really should be digging deeper into G&R more. Thanks for this answer! –  Ｊ. Ｍ. Sep 19 '11 at 16:14
@J.M.: You know, the series for the gamma function was a lot of what got me to my answer. As soon as I saw the first two subconstant terms in the question I thought that series was involved somehow. With that in mind, I floundered around in the vicinity of the correct approach for a while, but it wasn't until I saw what David Speyer and you had done that it fell into place. –  Mike Spivey Sep 22 '11 at 4:38
@David: Thanks, and a sheepish facepalm from me. :) For example, the explanation of $\Gamma'(1)$ is in MathWorld's entry on the gamma function. $\Gamma''(1)$ can be obtained from the formulas there as well. –  Mike Spivey Oct 2 '11 at 16:33

Here is a non-rigorous approach which gives the right leading order term first two terms. I'm writing it here in the hope that someone will follow up and turn it into an actual proof. This post is CW, in case some one wants to add to what I've come up with.

I start with Andrew's formula: $$\sum_{k=1}^n (-1)^k \binom{n}{k} \log k = \int_0^1 \left( \frac{1}{x} - \frac{\Gamma(n) \Gamma(x)}{\Gamma(n+x)} \right) dx = \int_0^1 \left( \frac{1}{x} - \frac{(n-1)!}{x(x+1)(x+2) \cdots (x+n-1)} \right) dx$$ $$=\int_0^1 \frac{dx}{x} \left( 1- \frac{1}{(1+x)(1+x/2) \cdots (1+x/(n-1))} \right)$$

Let's look at that denominator. $$\prod_{k=1}^{n-1} (1+x/k) = \exp \left( \sum_{k=1}^{n-1} \log \left(1+\frac{x}{k}\right) \right) \approx \exp \left( \sum_{k=1}^{n-1} \frac{x}{k} \right) \approx e^{x \log n}.$$

I could make these estimates more precise, but I'm not going to bother because I don't have a rigorous proof. So, roughly, we want to compute $$\int_0^1 \frac{1-e^{-x \log n}}{x} dx = \int_0^{\log n} \frac{1-e^{-u}}{u} du$$ where we have substituted $u = x \log n$. Let $[u>1]$ be $1$ for $u>1$ and $0$ for $u<1$. Then we can write this integral as $$\int_0^{\log n} \frac{[u>1] du}{u} + \int_0^{\log n} \frac{1-[u>1]-e^{-u}}{u} du = \log \log n + \int_0^{\log n} \frac{1-[u>1]-e^{-u}}{u} du$$

One can check that the integral $\int_0^{\infty} (1-[u>1]-e^{-u})/u \ du$ converges to some constant $\gamma$, as JM points out below. So, if we make our estimates precise, this method will give $$\log \log n + \gamma + o(1) \quad \mbox{as n \to \infty}.$$

"Concrete" methods should be able to improve the approximation $\sum_{k=1}^{n-1} \log \left(1+\frac{x}{k}\right) \approx x \log n$ a good deal. Once we see what that improved version looks like, we can try to figure out what to do with the rest of the argument.

-
$C$ evaluates to $\gamma$. To see this, split up the Iverson bracket, ending with two integrals. After a few substitutions, you end up with $$\int_{-1}^0 \frac{e^u-1}{u}\mathrm du+\int_{-\infty}^{-1} \frac{e^u}{u}\mathrm du$$ The first is $\gamma-\mathrm{Ei}(-1)$, and the second is $\mathrm{Ei}(-1)$... –  Ｊ. Ｍ. Sep 17 '11 at 18:35
Heh, should've checked Wolfram functions; they have a more general expression. –  Ｊ. Ｍ. Sep 18 '11 at 1:21
@David: does the approximation of the sum with logarithms with $x \log n$ come from Taylor series expansion of $\log (1+\frac{x}{k})$ function around 0? –  sigma.z.1980 Oct 2 '11 at 2:17
@sigma.z.1980 Yes. –  David Speyer Oct 2 '11 at 14:39