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?
 A: *

*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$

A: 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.
A: 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.
A: Using generating functions it is straightforward. Note that
$$
\sum_{k\ge 0}\binom{n}k(-1)^k\frac1{k+1}=(-1)^n\sum_{k\ge 0}\binom{n}k(-1)^{n-k}\frac1{k+1}\\
=\left[\frac{x^n}{n!}\right](-1)^n\left(\sum_{k\ge 0}(-1)^k\frac{x^k}{k!}\right)\left(\sum_{k\ge 0}\frac{x^k}{(k+1)!}\right)\\
=\left[\frac{x^n}{n!}\right](-1)^ne^{-x}\cdot\frac{e^x-1}x=\left[\frac{x^n}{n!}\right](-1)^n\frac{1-e^{-x}}x\\
=\left[\frac{x^n}{n!}\right](-1)^n\sum_{k\ge 1}(-1)^{k-1}\frac{x^{k-1}}{k!}
=\frac1{n+1}
$$
where the notation $[x^n/n!]f(x)$ means "the $n$-th coefficient that appear in the exponential power series expansion of $f$".
