25
$\begingroup$

Other than the general inductive method,how could we show that $\sum_{r=0}^n \frac{(-1)^r}{r+1}\binom{n}{r} = \frac1{n+1}$

Apart from induction, I tried with Wolfram Alpha to check the validity, but I can't think of an easy (manual) alternative.

Please suggest an intuitive/easy method.

5 Answers 5

26

Look at $\int_0^1(1-x)^n dx$ This is easy to compute by substitution.

Now compute it the hard way, by expanding using the Binomial Theorem, and integrating term by term.

  • 2
    @Alexander Thumm: True, but not necessarily to the person who asked the question.2011-05-12
20

Note that $\begin{align*}\frac{(n+1)\binom{n}{r}}{r+1} &= \frac{(n+1)n!}{(r+1)r!(n-r)!} = \frac{(n+1)!}{(r+1)!(n-r)!}\\ &= \frac{(n+1)!}{(r+1)!((n+1)-(r+1))!} = \binom{n+1}{r+1}.\end{align*}$ Therefore, $\begin{align*} (n+1)\sum_{r=0}^{n}(-1)^r\frac{\binom{n}{r}}{r+1} &= \sum_{r=0}^{n}(-1)^r\frac{(n+1)\binom{n}{r}}{r+1}\\ &= \sum_{r=0}^{n}(-1)^r\binom{n+1}{r+1}\\ &= -\sum_{r=0}^n(-1)^{r+1}\binom{n+1}{r+1}\\ &= -\sum_{s=1}^{n+1}(-1)^s\binom{n+1}{s}\qquad(\text{setting }s=r+1)\\ &= \left(-\sum_{s=0}^{n+1}(-1)^s\binom{n+1}{s}\right) + (-1)^0\binom{n+1}{0}\\ &= -(1-1)^{n+1} + 1\\ &= 1. \end{align*}$

Dividing through by $n+1$ gives the desired result.

Once you realize that $\frac{(n+1)\binom{n}{r}}{r+1} = \binom{n+1}{r+1},$ it should be obvious that you are dealing with a binomial expansion of some $(n+1)$st power. Then it's just a matter of figuring out which power, and whether any terms are missing.

  • 0
    @Amy:$ $I meant `\displaystyle`, sorry; the standard commands are `\displaystyle` for display-style output; `\textstyle` for in-line style output; and `\scriptstyle` and `\scriptscriptstyle` are the other two.2011-05-13
10

Here's a probabilistic proof of the equivalent identity $\frac{n}{n+1} = \sum\limits_{r=1}^n \frac{(-1)^{r+1}}{r+1}\binom{n}{r} .$

Choose $n+1$ numbers at random from (the uniform distribution on) $[0,1]$ and call them $x_1, x_2, \ldots, x_{n+1}$. If we select $r$ numbers from $\{x_2, \ldots, x_{n+1}\}$, the probability that $x_1$ is larger than all $r$ of them is $\frac{1}{r+1}$.

Question: What's the probability that at least one of $x_2, \ldots, x_{n+1}$ is larger than $x_1$?

Answer 1: Using the complement, it's $1 - \frac{1}{n+1} = \frac{n}{n+1}$.

Answer 2: By the principle of inclusion-exclusion, it's also $\sum\limits_{r=1}^n (-1)^{r+1}\binom{n}{r} \frac{1}{r+1}.$

(For those not familiar with inclusion-exclusion, it's the generalization of the identity $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ from 2 sets to $n$ sets. First you add in the probabilities of all the singleton sets, but that double-counts the probabilities of the intersections of two sets, so you subtract those off, but then you have to add back the probabilities of the intersections of three sets, etc.)

0

My answer use partial integration.

enter image description here