# 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 F 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 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.)

This an old question, but I recently remembered a nice proof using partial fractions from an exam paper;

Consider the partial fraction expansion $$\frac{n!}{x(x+1)...(x+n)}=\frac{c_{0}}{x} + \frac{c_{1}}{x+1}+...+\frac{c_{n}}{x+n}$$ where $$c_{r}$$, $$r=0,1,2,...n$$ are constants. Multiplying both sides by $$x+r$$ and substituting $$x=-r$$, we have $$c_{r} = (-1)^{r}\binom{n}{r}$$

Now, sub $$x=1$$ into the original equation to get

$$\sum_{r=0}^{n}\frac{(-1)^{r}}{r+1}\binom{n}{r}=\frac{n!}{(n+1)!} = \frac{1}{n+1}$$ 