# Prove that combinatoric sum approaches $-\infty$

This question arose from a small part of a larger problem that I've been working on recently.

How can I show that: $$\lim_{n \to \infty} \sum_{k=1}^n \frac{(-1)^k}{k} {n \choose k} = -\infty$$

Computationally, this appears to be the case: successive partial sums decrease without bound (albeit rather slowly) with increasing $n$. However, I've had trouble finding a closed form for the sum or showing the result analytically. Any help would be much appreciated!

• WolframAlpha says your Limit is $-1$ – Dr. Sonnhard Graubner Jun 20 '17 at 15:55
• Representing the sum by the integral $$\int_{0}^{1}\frac{(1-x)^n -1}{x}\,dx$$ is one possible approach. This tells that your integral diverges to $-\infty$ at logarithmic speed. – Sangchul Lee Jun 20 '17 at 15:59
• @Dr.SonnhardGraubner Wolframalpha "is wrong". – user228113 Jun 20 '17 at 16:09

## 2 Answers

\begin{align} \sum_{k=1}^n\frac{(-1)^k}k{n\choose k} &=\int_0^1\sum_{k=1}^n(-1)^k{n\choose k}x^{k-1}\,dx =\int_0^1\frac{(1-x)^n-1}{x}\,dx\\\ &=-\int_0^1\frac{1-y^n}{1-y}\,dy =-\int_0^1\sum_{k=1}^n y^{k-1}\,dy =-\sum_{k=1}^n\frac1k. \end{align}

You are dealing with the binomial transform of the sequence of harmonic numbers. The first claim has already been shown by Lord Shark, and the fact that $H_n\approx \log(n)$ follows from

$$H_n = \sum_{k=1}^{n}\frac{1}{k} = O(1) + \sum_{k=1}^{n}\log\left(\frac{1+\frac{1}{2k}}{1-\frac{1}{2k}}\right)\stackrel{\text{Telescopic!}}{=}O(1)+\log(2n+1).$$