Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

4 Answers

up vote 21 down vote accepted

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.

share|improve this answer
    
@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
2  
@Alexander Thumm: True, but not necessarily to the person who asked the question. –  André Nicolas May 12 '11 at 7:33
add comment

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.

share|improve this answer
2  
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
1  
@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
1  
@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.)

share|improve this answer
add comment

My answer use partial integration.

![my answer capture][1]

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.