# Prove: $\binom{n}{k}^{-1}=(n+1)\int_{0}^{1}x^{k}(1-x)^{n-k}dx$ for $0 \leq k \leq n$

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!

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

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.

-

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

-
I love it when such different methods come together in answer. (+1) – robjohn Nov 28 '11 at 23:55
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
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}.$$

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

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

-
 @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