# How to prove $\sum\limits_{r=0}^n \frac{(-1)^r}{r+1}\binom{n}{r} = \frac1{n+1}$?

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.

-

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.

-
@Tretwick Marian: No. But integrating in the "wrong" direction will get you $-1/(n+1)$, and then the negative of your complicated expression, so no harm done. In substituting, you may have forgotten that $dx=-du$. –  André Nicolas May 12 '11 at 5:07
@user6312:Got it,thanks! –  Quixotic May 12 '11 at 5:14
@Tretwick Marian: Please note that the calculation can be done purely algebraically, as thoroughly described by Arturo Magidin. The techniques set out there are very useful. –  André Nicolas May 12 '11 at 5:23
@user6312: Since we are working with polynomials, your calculation is purely algebraic. –  Alexander Thumm May 12 '11 at 7:00
@Alexander Thumm: True, but not necessarily to the person who asked the question. –  André Nicolas May 12 '11 at 7:33

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.

-
Obvious remark: you can also get $(n+1) \binom{n}{r} = (r+1) \binom{n+1}{r+1}$ by counting in two ways the pairs $(x,S)$ with $x \in S \subset \{1,2,\ldots,n+1\}$, $|S|=r+1$. –  Mike May 12 '11 at 7:21
@Amy: Enclosing a formula between double dollar signs automatically puts it in "displaymode". There is no need to add \displaymode; that command is so that in-line formulas will be typeset as if they were in display. –  Arturo Magidin May 13 '11 at 4:15
@Arturo: Thanks for the pointer...I did both, ($$and displaymode, as you saw. Good to know I only need one. I had no issues at all with your answer: it was great. I just found the in-line fraction and (n + 1) choose (r + 1) difficult to read, that's all. – amWhy May 13 '11 at 4:19 @Amy: No problem! If you want the formula to be in-line but "large", that's when you use \displaymode (inside single dollar signs). – Arturo Magidin May 13 '11 at 4:31 @Arturo: I've already made use of your tip. Are both \displaymode and \displaystyle equivalent, in terms of output? I'm kind of learning this as I go... (-; – amWhy May 13 '11 at 4:38 show 1 more comment 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.)

-
[1]: http://i.stack.imgur.com/SEg1x.jpg my answer image