How to prove that $\mathbb{P} (U_1 + U_2 + \dots U_k \le x) \le \dfrac{x^k}{k!}$, where $x \le 1$ and $U_1, U_2. \dots, U_k$ is $k$ i.i.d random variables $\sim Uniform[0,1]$?
I have no idea except using Central limit theorem but it seem doesn't work.
Best Answer
I think this can be done by induction on $k$.
The base case is trivial, namely $\mathbb{P}(X_1\leq x)=x\leq\frac{x^1}{1!}$ since $X_1$ is uniform.
So assume the statement is true for all $0\leq x\leq 1$ and for a fixed $k$. We want to show it for $k+1$.
I think there is a more elegant way of doing this induction step using some integral tricks more directly, but I am struggling with making sure that is formally correct, so I will write down a more elementary version.
Pick an arbitrary natural $N$. Note that if the event $X_1+\dots+X_{k+1}\leq x$ occurs, this means that there exists some $1\leq n\leq N$ such that $X_{k+1}\in [\frac{(n-1)x}{N},\frac{nx}{N}]$ and $X_1+\dots+X_k\leq x-\frac{(n-1)x}{N}$. Therefore, setting $P:=\mathbb{P}(X_1+\dots+X_k+X_{k+1}\leq x)$, we have
$P\leq \sum_{n=1}^N \mathbb{P}(X_{k+1}\in [\frac{(n-1)x}{N},\frac{nx}{N}])\cdot\mathbb{P}(X_1+\dots+X_k\leq x-\frac{(n-1)x}{N})$.
Applying the induction hypothesis and the fact that $X_{k+1}$ is uniformly distributed, this means
\begin{equation*} \begin{split} P & \leq \sum_{n=1}^N \frac{x}{N} \mathbb{P}(X_1+\dots+X_k\leq x-\frac{(n-1)x}{N}) = \\ & = \frac{x}{N} \sum_{n=1}^{N} \mathbb{P}(X_1+\dots+X_k\leq \frac{nx}{N}) \leq \\ & \leq \frac{x}{N}\sum_{n=1}^{N} \big(\frac{n}{N}\big)^k\frac{x^k}{k!} =\\ & = \frac{x^{k+1}}{k!} \cdot \frac{1}{N} \sum_{n=1}^{N} \big(\frac{n}{N}\big)^k. \end{split} \end{equation*}
Note however that $\frac{1}{N} \sum_{n=1}^{N} \big(\frac{n}{N}\big)^k $ tends to $\int_0^1 x^k dx =\frac{1}{k+1}$ as $N\to\infty$ since clearly $x\mapsto x^k$ is Riemann integrable and the expression is just the (upper) Riemann sum corresponding to the equidistant partition of the unit interval with stepsize $\frac{1}{N}$ for $x\mapsto x^k$.
Since we chose $N$ arbitrarily, we can pass to the limit and obtain that $P\leq\frac{x^{k+1}}{k!}\frac{1}{k+1}=\frac{x^{k+1}}{(k+1)!}$, which completes the induction.