# 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$. May 12, 2011 at 5:07
• @user6312:Got it,thanks! May 12, 2011 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. May 12, 2011 at 5:23
• @user6312: Since we are working with polynomials, your calculation is purely algebraic. May 12, 2011 at 7:00
• @Alexander Thumm: True, but not necessarily to the person who asked the question. May 12, 2011 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$. May 12, 2011 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. May 13, 2011 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. May 13, 2011 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). May 13, 2011 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... (-; May 13, 2011 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}$$ 