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.

I would like your help with proving that for every $0 \leq k \leq n$,

$$\binom{n}{k}^{-1}=(n+1)\int_{0}^{1}x^{k}(1-x)^{n-k}dx . $$

I tried to integration by parts and to get a pattern or to use the binomial formula somehow, but it didn't go well.

Thanks a lot!

share|improve this question
4  
Repeated integration by parts ought to work. Every time you differentiate the $1-x$ term and antidifferentiate the $x$ term, you get a factor of $(n-k)/(k+1)$ coming out; eventually, you've differentiated the $1-x$ term clean away, and you can just evaluate the integral of the $x$ power that remains. Try it again, then write it up as an answer (if it works). –  Gerry Myerson Nov 28 '11 at 22:06
3  
I added the [special-functions] tag since this is a special case of the beta function. (I replaced the [calculus] tag with [definite-integral].) –  Srivatsan Nov 28 '11 at 22:18
2  
If you only want integer $k$ and $n$, then integration by parts and induction (Paul's answer) work very simply. If you want real $k$ and $n$, you have to move to the Beta function (my answer) which requires a bit more machinery. I can append my answer with a proof of the relation between the Beta and Gamma functions if desired. –  robjohn Nov 28 '11 at 22:32
1  
Analytic methods can get you the bottom line, but to really see the intuition, look at the probabilistic method I posted below. –  Michael Hardy Nov 28 '11 at 23:51

7 Answers 7

up vote 14 down vote accepted

Use induction on $k$. For $k=0$, we have $$(n+1)\int_{0}^{1}(1-x)^{n}dx=-(1-x)^{n+1}\Big|_0^1=1=\binom{n}{0}^{-1}.$$ Now assume that it's true for all $k\leq n-1$ (if $k=n$ we are done), i.e. $$\binom{n}{k}^{-1}=(n+1)\int_{0}^{1}x^{k}(1-x)^{n-k}dx.$$ Consider $(n+1)\int_{0}^{1}x^{k+1}(1-x)^{n-k-1}dx$. By integration by parts, $$(n+1)\int_{0}^{1}x^{k+1}(1-x)^{n-k-1}dx=-\frac{(n+1)}{n-k}\int_{0}^{1}x^{k+1}d((1-x)^{n-k})$$ $$=-\frac{(n+1)}{n-k}\Big[x^{k+1}(1-x)^{n-k}\Big|_0^1-\int_{0}^{1}(1-x)^{n-k}d(x^{k+1})\Big]=\frac{(n+1)(k+1)}{n-k}\int_{0}^{1}x^{k}(1-x)^{n-k}dx.$$ Hence, by the induction assumption (the above equality), $$(n+1)\int_{0}^{1}x^{k+1}(1-x)^{n-k-1}dx=\frac{k+1}{n-k}\binom{n}{k}^{-1}=\binom{n}{k+1}^{-1},$$ as required.

share|improve this answer

Let's do it somewhat like the way the Rev. Thomas Bayes did it in the 18th century (but I'll phrase it in modern probabilistic terminology).

Suppose $n+1$ independent random variables $X_0,X_1,\ldots,X_n$ are uniformly distributed on the interval $[0,1]$.

Suppose for $i=1,\ldots,n$ (starting with $1$, not with $0$) we have: $$Y_i = \begin{cases} 1 & \text{if }X_i<X_0 \\ 0 & \text{if }X_i>X_0\end{cases}$$

Then $Y_1,\ldots,Y_n$ are conditionally independent given $X_0$, and $\Pr(Y_i=1\mid X_0)= X_0$.

So $\Pr(Y_1+\cdots+Y_n=k\mid X_0) = \dbinom{n}{k} X_0^k (1-X_0)^{n-k},$ and hence $$\Pr(Y_1+\cdots+Y_n=k) = \mathbb{E}\left(\dbinom{n}{k} X_0^k (1-X_0)^{n-k}\right).$$

This is equal to $$ \int_0^1 \binom nk x^k(1-x)^{n-k}\;dx. $$

But the event is the same as saying that the index $i$ for which $X_i$ is in the $(k+1)$th position when $X_0,X_1,\ldots,X_n$ are sorted into increasing order is $0$.

Since all $n+1$ indices are equally likely to be in that position, this probability is $1/(n+1)$.

Thus $$\int_0^1\binom nk x^k(1-x)^{n-k}\;dx = \frac{1}{n+1}.$$

share|improve this answer
1  
I love it when such different methods come together in answer. (+1) –  robjohn Nov 28 '11 at 23:55
3  
When I saw the equation, I thought "probability". Only I couldn't come up with a probabilistic argument. Well done! –  Byron Schmuland Nov 29 '11 at 0:20
    
Thank you, Byron. –  Michael Hardy Nov 29 '11 at 0:23
4  
I had this exact proof in mind but thought that actually writing it out would be a chore. Thanks for writing this, so I don't have to. –  Michael Lugo Nov 29 '11 at 0:28

The method in Michael Hardy's answer is my favorite, but here's my second favorite (using the binomial theorem as you suggested): $$\sum_{k=0}^n t^k \int_0^1 {n \choose k} x^k (1 - x)^{n-k} \, dx = \int_0^1 (1 + (t-1)x)^n \, dx = \frac{t^{n+1} - 1}{(t-1)(n+1)} = \frac{1 + t + \cdots + t^n}{n+1}.$$

Generating functions are surprisingly useful for evaluating certain types of discrete families of integrals. For example, to evaluate $$I_k(x) = \int_0^x u^k e^u \, du$$

simply observe that $$\sum I_k(x) \frac{t^k}{k!} = \int_0^x e^{ut} e^u \, du = \frac{e^{(t+1)x} - 1}{t+1}.$$

See also this MO question.

share|improve this answer
2  
Incidentally, the quantity $\sum_{k=0}^n t^k \int_0^1 {n \choose k} x^k (1 - x)^{n-k} \, dx$ is just the probability-generating function of the distribution considered by Michael's answer. –  Srivatsan Nov 29 '11 at 1:17
    
Mmmm... generating functions :-) (+1) –  robjohn Nov 29 '11 at 1:40

Yet another way: Show that $$\frac{1}{\binom{n}{k}(n+1)}$$ and $$\int_0^1 x^k (1-x)^{n-k} dx$$ both satisfy the recurrence $$R(n,k) = \frac{k}{n+1} R(n-1,k-1),$$ with the initial condition $R(n,0) = 1/(n+1)$.


For the binomial expression, use the property $\binom{n-1}{k-1} \frac{n}{k} = \binom{n}{k}$.

For the integral, use integration by parts with $u = \left(\frac{x}{1-x}\right)^k$, $dv = (1-x)^n dx$.

share|improve this answer
2  
Incidentally, the numbers satisfying the $R(n,k)$ recurrence are sometimes called the Leibniz numbers. The link to Comtet's Advanced Combinatorics has more discussion of their properties. –  Mike Spivey Nov 29 '11 at 0:23

The integral can be evaluated as the Beta Function: $$ \begin{align} \int_0^1x^k(1-x)^{n-k}\;\mathrm{d}x &=\mathrm{B}(k+1,n-k+1)\\ &=\frac{\Gamma(k+1)\Gamma(n-k+1)}{\Gamma(n+2)}\\ &=\frac{k!(n-k)!}{(n+1)!}\qquad\text{ for integer }n\text{ and }k\\ &=\frac{1}{n+1}\frac{1}{\binom{n}{k}} \end{align} $$ The given identity follows directly.

Relation between $\mathrm{B}$ and $\Gamma$: $$ \begin{align} \Gamma(a+b)\mathrm{B}(a,b) &=\Gamma(a+b)\int_0^1s^{a-1}(1-s)^{b-1}\;\mathrm{d}s\\ &=\Gamma(a+b)\int_0^\infty\left(\frac{r}{1+r}\right)^{a-1}\left(\frac{1}{1+r}\right)^{b-1}\frac{\mathrm{d}r}{(1+r)^2}\\ &=\Gamma(a+b)\int_0^\infty r^{a-1}(1+r)^{-a-b}\;\mathrm{d}r\\ &=\int_0^\infty\int_0^\infty r^{a-1}(1+r)^{-a-b}t^{a+b-1}e^{-t}\;\mathrm{d}t\;\mathrm{d}r\\ &=\int_0^\infty\int_0^\infty r^{a-1}(1+r)^{-a-b}(u(1+r))^{a+b-1}e^{-u(1+r)}\;(1+r)\mathrm{d}u\;\mathrm{d}r\\ &=\int_0^\infty\int_0^\infty r^{a-1}u^{a+b-1}e^{-u(1+r)}\;\mathrm{d}u\;\mathrm{d}r\\ &=\int_0^\infty\int_0^\infty\left(\frac{v}{u}\right)^{a-1}u^{a+b-1}e^{-u-v}\;\frac{1}{u}\mathrm{d}v\;\mathrm{d}u\\ &=\int_0^\infty\int_0^\infty v^{a-1}u^{b-1}e^{-u-v}\;\mathrm{d}v\;\mathrm{d}u\\ &=\int_0^\infty v^{a-1}e^{-v}\;\mathrm{d}v\;\int_0^\infty u^{b-1}e^{-u}\;\mathrm{d}u\\ &=\Gamma(a)\Gamma(b) \end{align} $$ Therefore, $$ \mathrm{B}(a,b)=\frac{\Gamma(a)\Gamma(b)}{\Gamma(a+b)} $$

share|improve this answer
    
@MichaelHardy: thanks for the edits. I took out the spaces that were added. $(1+r)\mathrm{d}u$ and $\dfrac{1}{u}\mathrm{d}v$ are together because they are $\mathrm{d}$ of the substitution. I left them together to emphasize that :-) The removal of the tag was very good though. –  robjohn Nov 29 '11 at 14:12

The equation is equivalent to

$$\binom{n+m}{n}^{-1}=(n+m+1)\int_{0}^{1}x^{n}(1-x)^{m}dx$$

with $$ m\ge0 , n\ge 0$$

Or $${1\over(n+m+1)!}=\int_{0}^{1}{x^{n}(1-x)^{m}\over n!m!}dx$$

And hence one can multiply the two series and integrate from 0 to 1:

$$e^{tx} = \sum_{n=0}^\infty{t^nx^n\over n!}$$

$$e^{s(1-x)} = \sum_{m=0}^\infty{s^m(1-x)^m\over m!}$$

Giving

$$\int_{0}^{1}{e^{(t-s)x+s}}dx=\sum_{m,n=0}^\infty{t^ns^m\int_{0}^{1}{x^{n}(1-x)^{m}\over n!m!}dx}$$

Finally, the LHS is equal to $$e^t-e^s\over(t-s)$$

And using the exponential series and the fact that

${{t^n-s^n}\over{t-s}} = t^{n-1}+t^{n-2}s+...+ts^{n-2}+s^{n-1}$

gives the result.

share|improve this answer
    
Did you mean $$\frac1{(n+m+1)!}=\int_0^1\frac{x^n(1-x)^m}{n!\,m!}\,\mathrm{d}x$$ –  robjohn Jun 16 at 22:25
    
Yes, I did thanks very much for the heads up, corrected now! –  Ivan Jun 17 at 6:08
    
Nice use of generating functions (+1) –  robjohn Jun 17 at 10:12

Here's another probabilistic answer. A random variable $X$ has a Gamma distribution with scale parameter $1$ if its probability density is $$ x \mapsto \frac{x^{n-1}e^{-x}}{\Gamma(n)}\text{ for }x>0, $$ where $\Gamma(n)$ is just the number needed to make the integral equal to $1$, and as everybody knows, $\Gamma(n) = (n-1)!$ if $n$ is a positive integer. Now suppose a second random variable $Y$ independent of the first has a Gamma distribution with "shape parameter" $m$ instead of $n$, so their joint density function is $$ (x,y)\mapsto \frac{x^{n-1}e^{-x}}{\Gamma(n)}\cdot\frac{y^{m-1}e^{-y}}{\Gamma(m)}\text{ for }x,y>0. $$ We would like to know $\Pr(X+Y<w)$. That is $$ \iint\limits_{\{(x,y)\in\mathbb (R^+)^2\,:\,x+y<w\}} \frac{x^{n-1}e^{-x}}{\Gamma(n)}\cdot\frac{y^{m-1}e^{-y}}{\Gamma(m)} \, dy\,dx. $$ Let $$ \begin{align} u & = x+y, \\ v & = x/(x+y), \\ \text{so that } x & = uv, \\ y & = u(1-v), \\ dx\,dy & = u\,du\,dv. \end{align} $$ Then the integral above becomes $$ \begin{align} & \phantom{={}} \frac{1}{\Gamma(n)\Gamma(m)}\int_0^1 \int_0^w (uv)^{n-1}(u(1-v))^{m-1} e^{-u} u\,du\,dv \\ & = \frac{1}{\Gamma(n)\Gamma(m)}\int_0^1v^{n-1}(1-v)^{m-1}\,dv \cdot \int_0^w u^{n+m-1} e^{-u}\,du. \end{align} $$ The last integral goes to $\Gamma(n+m)$ as $w\to\infty$, but the value of the whole expression must go to $1$ as $w\to\infty$ since the integral of a probability density is $1$. Therefore $$ \int_0^1 v^{n-1}(1-v)^{m-1}\,dv = \frac{\Gamma(n)\Gamma(m)}{\Gamma(n+m)}. $$

share|improve this answer

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.