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 am asked for the volume of the region $x_1+\cdots+x_n\leq 1$ where $x_1,...,x_n\geq 0$. I am proposing that the volume $V(n)$, is given by

$$ V(n) = \int\limits_0^1\int\limits_0^{(1-x_1)}\cdots\int\limits_0^{(1-\cdots-x_{n-1})} \,dx_n\cdots\,dx_2\,dx_1 = \frac{1}{n!} \ . $$

I am trying to prove the formula by induction. The base case is easy, but I am having a problem showing that if $n=k$ holds, then $n=k+1$ holds. I cannot figure out how to apply the inductive hypothesis. Am I missing something obvious or is there an easier method?

share|improve this question
    
Here is a proof using a measure theoretic approach. If this is out of the scope, then just disregard my comment. –  Stefan Hansen Apr 12 '13 at 6:59
1  
@StefanHansen: Your "measure theoretic" approach proof is just a rewording of the proof below. But it is enjoyable to read your proof! Thank you! –  Bombyx mori Apr 12 '13 at 7:08
    
@StefanHansen: I saw that approach when I was searching prior to posting my question. It is out of scope for my purposes, but I do appreciate the comment. I always like seeing different ways of approaching the same problem. –  5space Apr 12 '13 at 18:02

3 Answers 3

up vote 4 down vote accepted

This is example of inventor's paradox, when it is easier to prove more general fact than more specific. Let's prove by induction on $n$ that $$ V(a,n) = \int\limits_0^a\int\limits_0^{(a-x_1)}\cdots\int\limits_0^{(a-\cdots-x_{n-1})} dx_n \cdots dx_2 dx_1 = \frac{a^n}{n!}. $$ Basis of induction is obvious $$ V(a,1)=\int_0^a dx_1=a $$ Step of induction $$ \begin{align} V(a,n+1)&=\int\limits_0^a\int\limits_0^{(a-x_1)}\cdots\int\limits_0^{(a-\cdots-x_n)} dx_{n+1} \cdots dx_2 dx_1\\ &=\int_0^a V(a-x_1,n)dx_1\\ &=\int_0^a \frac{(a-x_1)^n}{n!}dx_1\\ &=\frac{a^{n+1}}{(n+1)!} \end{align} $$ In particular $$ V(n)=V(1,n)=\frac{1}{n!} $$

share|improve this answer
    
That is clean! I appreciate the help and especially the info on inventor's paradox. –  5space Apr 12 '13 at 18:03
    
Не стоит благодарности :) –  Norbert Apr 12 '13 at 18:06
    
Я полагаю, "спасибо" является более целесообразным. :-D –  5space Apr 12 '13 at 18:11

In the spirit of the above proof, assume $A$ is a connected region in $\mathbb{R}^{n-1}$ of area $m(A)$, and $x$ has distance $1$ from $A$. We claim that the simplex $K$ formed by joining $x$ to $A$ in $\mathbb{R}^{n}$ has volume $m(A)/n$.

We show this via a classical scaling argument:

$$\int_{K}\prod dx_{i}=\int_{((1-x)A,x)}m((1-x)A)dx=\int (1-x)^{n-1}m(A)dx=m(A)\int^{1}_{0}y^{n-1}dy=\frac{m(A)}{n}$$where $y=(1-x),dy=-dx$.

share|improve this answer

Try the following (you need to make this rigorous). Fix $x_{1}$. If you integrate only the $n-1$ interior integrals, you get the volume for the region when $x_{2} + \cdots x_{n} \leq 1 - x_{1}$. Heuristically, this should be

$$\frac{1}{(n-1)!}(1-x_{1})^{n-1}$$

Where the $\frac{1}{(n-1)!}$ comes from the inductive step, and the $(1-x_{1})^{n-1}$ from the fact that you are scaling each inner integral by $(1-x_{1})$. Then finish evaluating the integral,

$$\frac{1}{(n-1)!}\int_{0}^{1} (1-x_1)^{n-1} dx_{1} = \frac{1}{(n-1)!} \cdot \frac{1}{n} = \frac{1}{n!}$$

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.