# Prove by induction that the CDF of the sum of $n$ i.i.d. uniform random variables is $F(x)=x^n/n!$ on $(0,1)$

Let $X_i$ be a family of independent random variables, with $X\sim U(0,1)$. Then we have that the PDF of all the $X_i$ is $1$ for all $x \in [0,1]$. Now let $$Z_n= X_1 + X_2 +\dots + X_n$$ The question asks to prove by induction that the cdf of $Z_n$ is equal to: $$F_n(x) = x^n/n!, \qquad \text{ for all } x \in [0,1]$$

Now I think I am currently on the right track, as I proved that $Z_1 = x^1/1!$. Also, I think that I should change $Z_m = Z_k + X_m$, where $m=k+1$.

ButI don't know how to conclude this in the Induction Step. If someone could help it would be appreciated.

First, determine the df of $X$, because you will need it

$$F_X(x)=\int_{0}^x1dt=x$$ for $x\in[0,1]$. Now, the proof by induction:

• Base case: $F_1(x)=x^1/1!$, you have shown this.
• Induction step: Assume that $F_n(x)=x^n/n!$ for $x\in [0,1]$. Then you can find the pdf $f_n(z)$ of $Z_n$ by differentiating $F_n$ $$f_n(x)=\frac{d}{dx}F_n(x)=\frac{x^{n-1}}{(n-1)!}$$ for $x\in [0,1]$. Then for the distribution function of $Z_{n+1}$ we have that \begin{align}F_{n+1}(x)&=P(Z_{n+1}\le x)=P(Z_n+X_{n+1}\le x)=P(X_{n+1}\le x-Z_n)\\[0.2cm]&=\int_{0}^1P(X_{n+1}\le x-Z_n\mid Z_n=z)f_n(z)dz\\[0.2cm]&=\int_0^1F_X(x-z)\frac{z^{n-1}}{(n-1)!}dz=\int_0^x(x-z)\frac{z^{n-1}}{(n-1)!}dz\\[0.2cm]&=x\int_0^x\frac{z^{n-1}}{(n-1)!}dz-\int_0^x\frac{z^n}{(n-1)!}dz\\[0.2cm]&=x\left[\frac{z^n}{n!}\right]_0^x-\left[\frac{z^{n+1}}{(n-1)!(n+1)}\right]_0^x\\[0.2cm]&=\frac{x^{n+1}}{n!}-\frac{x^{n+1}}{(n-1)!(n+1)}=\frac{x^{n+1}(n+1-n)}{n+1!}=\frac{x^{n+1}}{(n+1)!}\end{align} for $x\in[0,1]$. Note the change in the integral limits in the end of the third line. This is because $F_X(x)=(x-z)$ only if $x-z\in [0,1]$. Otherwise, if $x-z<0$, then $F_X(x-z)=0$.

The base case: $\mathbb{P} \{Z_1\le x\}=x^1/1!$. Assume that the result holds for $n-1$. Then noticing that $\mathbb{P}\{Z_{n-1}<0\}=0$ and $X$'s are independent, for $x\in [0,1]$ we have

$$\mathbb{P}\{Z_n\le x\}=\mathbb{E}[\mathbb{P}\{Z_{n-1}\le x-X_n\mid X_n\}]=\int_{0}^x \frac{(x-z)^{n-1}}{(n-1)!}dz=\frac{x^n}{n!},$$

and the result holds by induction.

• Could I just ask how you got the first result for the Expectation in your equation? Nov 2 '16 at 4:09
• @FelicioGrande $$\mathbb{P}\{Z_n\le x\}=\mathbb{P}\{Z_{n-1}+X_n\le x\}\\ =\mathbb{E}[1\{Z_{n-1}\le x-X_n\}]\\ =\mathbb{E}[\mathbb{E}[1\{Z_{n-1}\le x-X_n\}\mid X_n]]$$ Nov 2 '16 at 4:16
• is the part in between the two equals a multiplication? Nov 2 '16 at 4:20
• @FelicioGrande There must be an equality. Fixed... Nov 2 '16 at 4:21
• Ah I see, so 1{...} means the indicator function based on the conditions within the brackets? In the answer part Nov 2 '16 at 4:26

Instead of the general case, it's easier to think of the n=2 case. If you can figure out n=2 from n=1, the general case would be similar.

Hint: you can try convolution of p.d.f. or from conditional probability point of view.