# Proof by induction using Fubini's Theorem

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?

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

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

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

-

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

-