24
$\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.

4 Answers 4

25

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.

  • 0
    @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$.2011-05-12
  • 0
    @user6312:Got it,thanks!2011-05-12
  • 0
    @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.2011-05-12
  • 0
    @user6312: Since we are working with polynomials, your calculation is purely algebraic.2011-05-12
  • 2
    @Alexander Thumm: True, but not necessarily to the person who asked the question.2011-05-12
19

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.

  • 3
    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$.2011-05-12
  • 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.2011-05-13
  • 0
    @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.2011-05-13
  • 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).2011-05-13
  • 0
    @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... (-;2011-05-13
  • 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