An upper bound on the probability of that the sum of k i.i.d uniform random variable is at most x? 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.
 A: 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.
A: The claim actually holds for all $x \geq 0$, with equality for $x \in [0,1]$.
To see this, as in the post by AnCar, we proceed by induction.
For $k = 1$, the claim is trivial.
For the induction step, note that $A = X_1+\dots+X_k$ and $B = X_{k+1}$ are independent.
Thus,
\begin{align*}
  \mathbb{P}(A + B \leq x)
  & = \mathbb{E} [1_{A+B \leq x}] \\
  & = \mathbb{E}_B
      \big[
        \mathbb{E}_A
          [1_{A+B \leq x} \,|\, B]
      \big]\\
  & = \int_0^1
        \mathbb{E}_A [1_{A+t \leq x}]
      \, d t \\
  & = \int_0^1
        \mathbb{P}(A \leq x - t)
      \, d t \\
  & \overset{(\ast)}{\leq} \int_0^x \mathbb{P}(A \leq x - t) \, d t \\
  & \overset{(\ast)}{\leq} \int_0^x \mathbb{P}(A \leq s) \, d s \\
  & \overset{\text{induction}}{\leq} \int_0^x \frac{s^k}{k!} \, d s \\
  & = \frac{x^{k+1}}{(k+1)!}
  .
\end{align*}
where we used at $(\ast)$ that $\mathbb{P}(A \leq x - t) = 0$ if $t \geq x$.
This step is an equality if $x \in [0,1]$, since then $[0,x] \subset [0,1]$.
Side-note: The distribution of $X_1+\dots+X_k$ is explicitly (more or less) known.
One can also obtain the claim (for $0 \leq x \leq 1$) from that.
See here: https://en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution
A: Here is a slightly different approach to prove the equality $\mathbb P[X_1+\dots+X_k\leq x]=\frac{x^k}{k!}$ for any $k$ and any $x\in [0,1]$, we also proceed by indution on $k$. Denote $U=U_1+\dots+U_k$, suppose that $\mathbb P[U\leq y]=\frac{y^k}{k!}$ for all $y\in [0,1]$, then
\begin{align*}
\mathbb P[U+U_{k+1} \leq x] &=\int_0^x \mathbb P[y+U_{k+1}\leq x|U=y] f_U(y)dy\\
&=\int_0^x (x-y) f_U(y) dy\\
&=\int_0^x\int_y^x f_U(y) dudy\\
&=\int_0^x\int_0^u f_U(y) dydu\\
&=\int_0^x\mathbb P[U\leq u] du\\
&=\int_0^x \frac{u^k}{k!} du\\
&=\frac{x^{k+1}}{(k+1)!}
\end{align*}
The base case is simple since $\mathbb P[U_1\leq x]=x$ and so by induction your inequality holds with equality for all $x\in[0,1]$ and all $k\in \mathbb N$.
