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

$\endgroup$
0
27
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ @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$. $\endgroup$ May 12 '11 at 5:07
  • $\begingroup$ @user6312:Got it,thanks! $\endgroup$
    – Quixotic
    May 12 '11 at 5:14
  • $\begingroup$ @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. $\endgroup$ May 12 '11 at 5:23
  • $\begingroup$ @user6312: Since we are working with polynomials, your calculation is purely algebraic. $\endgroup$ May 12 '11 at 7:00
  • 2
    $\begingroup$ @Alexander Thumm: True, but not necessarily to the person who asked the question. $\endgroup$ May 12 '11 at 7:33
21
$\begingroup$

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.

$\endgroup$
6
  • 3
    $\begingroup$ 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$. $\endgroup$
    – Mike F
    May 12 '11 at 7:21
  • 1
    $\begingroup$ @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. $\endgroup$ May 13 '11 at 4:15
  • $\begingroup$ @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. $\endgroup$
    – amWhy
    May 13 '11 at 4:19
  • 1
    $\begingroup$ @Amy: No problem! If you want the formula to be in-line but "large", that's when you use \displaymode (inside single dollar signs). $\endgroup$ May 13 '11 at 4:31
  • $\begingroup$ @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... (-; $\endgroup$
    – amWhy
    May 13 '11 at 4:38
11
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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}$$

$\endgroup$
0
$\begingroup$

My answer use partial integration.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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