# Alternating sum of binomial coefficients multiplied by (1/k+1)

I'm trying to prove that

$$\sum_{k=0}^n {n \choose k} (-1)^k \frac{1}{k+1} = \frac{1}{n+1}$$

So far I've tried induction (which doesn't really work at all), using well known facts such as

$$\sum_{k=0}^n {n \choose k} (-1)^k = 0$$

and trying to apply identities like

$${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$$

Would anyone be able to point me towards the right method? Should I be looking to apply an identity or is there a method I'm missing?

• Note that $$(1-x)^{n} = \sum_{k=0}^{n} {n \choose k}(-1)^{n-k}\ x^{k} =(-1)^{n}\sum_{k=0}^{n}{n\choose k} (-1)^{-k}x^{k} =(-1)^{n}\sum_{k=0}^{n}{n\choose k} (-1)^{k}x^{k}$$ And since $\displaystyle \int_{0}^{1} x^{k} \ dx = \frac{1}{k+1}$. Its worth looking at $\displaystyle \int_{0}^{1} (1-x)^{n} \ dx$
• This is a good hint, but shouldn't the expression for the sum be $$\binom{n}{k}(-1)^{n-k}x^k$$ or $$\binom{n}{k}(-1)^kx^{n-k}$$ right? – cjferes Oct 8 '14 at 15:28
• @cjferes thanks. I have edited it. – crskhr Oct 8 '14 at 15:40
• Note that $\sum_{k=0}^n {n \choose k} (-1)^k x^{k} = (1-x)^{n}$, then integral on $[0,1]$. – Alfred Chern Oct 9 '14 at 2:36
• The expression for the sum should be ${n\choose k}(1)^{n-k}\ (-x)^{k}$but not ${n \choose k}(-1)^{n-k}\ x^{k}$ – Alfred Chern Oct 9 '14 at 2:40

From $(k+1)\binom{n+1}{k+1} = (n+1)\binom{n}{k}$ we get

\begin{align*} \sum_{k=0}^n \binom{n}{k} (-1)^k \frac{1}{k+1} &= \frac{1}{n+1} \sum_{k=0}^n \binom{n+1}{k+1}(-1)^k \\ &= \frac{1}{n+1} \Bigl( 1 + \sum_{r=0}^{n+1} \binom{n+1}{r} (-1)^{r-1} \Bigr) \\ &= \frac{1}{n+1} \end{align*} as required.

This is a special case ($x=1$) of the identity $$\sum_{k=0}^n \binom{n}{k}\frac{(-1)^k}{k+x} = \frac{1}{x\binom{n+x}{n}}$$ which is proved in Concrete Mathematics, section 5.3, page 188. The outline of the proof is:

Show that the n-th difference of $1/x$ is $$\frac{(-1)^n}{\binom{n+x}{n}}$$ This is easy using the methods of finite calculus, cf. chapter 2 of that same book; it is analogous to the n-th derivative of $1/x$.

And show that the n-th difference of any function $f(x)$ is given by $$\Delta^n f(x) = \sum_k \binom{n}{k} (-1)^{n-k} f(x+k)$$

This can be proved by induction, but it also has a cute proof using the concept of the shift operator $E(f(x) = f(x+1)$ and writing $\Delta^n$ as $(E-1)^n$.

Then using $f(x)=1/x$ the result follows.

Try it as a Abel summation, i.e.

$$\sum f(k)\Delta g(k)\delta k=f(k)g(k)-\sum g(k+1)\Delta f(k)\delta k$$

where

$$\sum_{a}^{b}f(k)\delta k=\sum_{k=a}^{b-1}f(k)$$