Convolution of i.i.d. with uniform distribution I am trying to solve another exercise about convolution of continuous variables. Here is what is asked:

Let $X_1,\cdots,X_n$ be i.i.d. such that $X_1 \sim U(0,1)$. Verify that$$
P(X_1+\cdots+X_n\leq x)=\frac{1}{n!}\sum_{k=0}^{n-1}(-1)^k {n\choose k}(x-k)_+^n, \quad \forall 0\leq x \leq n$$
  where$$
(x-k)_+=\begin{cases}
0; & \text{if } x <k \\
x-k; & \text{otherwise}
\end{cases}
$$

My first thought would be to find $P(S\leq s)$, where $S=\sum\limits_{i=1}^{n}X_i$. But I am wondering how I can solve such a huge convolution? My integral would look like:
$$\int_{-\infty}^{+\infty}\cdots\int_{-\infty}^{+\infty}f_{X_1}(x_1)\cdots f_{X_n}(x_n)\,\mathrm{d}x_1\cdots\mathrm{d}x_n.$$
At first I had just $X_1$ and $X_2$ to add and I could find the CDF of $X_1 +X_2$ through convolution like this: $$\int_0^z f_{X_1}(z-v)f_{X_2}(v)\,\mathrm{d}v.$$
My question would be how can I solve it? Just even a hint in order to get started. My teacher say it is a simple generalization but many people suggest me to use conditional expectation, which I did not study yet.
Thank you for your help.
 A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
&\bbox[10px,#ffd]{\ds{\int_{0}^{1}\int_{0}^{1}\cdots\int_{0}^{1}
\bracks{x_{1} + x_{2} + \cdots + x_{n} < x}\dd x_{1}
\,\dd x_{2}\ldots\dd x_{n}}}
\\[5mm] = &\
\int_{0}^{1}\int_{0}^{1}\cdots\int_{0}^{1}\
\underbrace{\int_{c - \infty\ic}^{c + \infty\ic}
{\expo{\pars{x - x_{1} - x_{2} - \cdots - x_{n}}s} \over s}\,{\dd s \over 2\pi\ic}}_{\ds{\bracks{x - x_{1} - x_{2} - \cdots - x_{n} > 0}}}\
\dd x_{1}\,\dd x_{2}\ldots\dd x_{n}
\end{align}

where $\ds{c >0}$.

Then,
\begin{align}
&\bbox[10px,#ffd]{\ds{\int_{0}^{1}\int_{0}^{1}\cdots\int_{0}^{1}
\bracks{x_{1} + x_{2} + \cdots + x_{n} < x}\dd x_{1}
\,\dd x_{2}\ldots\dd x_{n}}}
\\[5mm] = &\
\int_{c - \infty\ic}^{c + \infty\ic}{\expo{xs} \over s}
\pars{\int_{0}^{1}\expo{-s\xi}\dd\xi}^{n}{\dd s \over 2\pi\ic} =
\int_{c - \infty\ic}^{c + \infty\ic}{\expo{xs} \over s}
\pars{\expo{-s} - 1 \over -s}^{n}{\dd s \over 2\pi\ic}
\\[5mm] = &\
\int_{c - \infty\ic}^{c + \infty\ic}
{\expo{xs} \over s^{n + 1}}\pars{1 - \expo{-s}}^{n}{\dd s \over 2\pi\ic} =
\int_{c - \infty\ic}^{c + \infty\ic}
{\expo{xs} \over s^{n + 1}}\sum_{k = 0}^{n}{n \choose k}
\pars{-\expo{-s}}^{k}{\dd s \over 2\pi\ic}\label{1}\tag{1}
\\[5mm] = &\
\sum_{k = 0}^{n}{n \choose k}\pars{-1}^{k}\
\underbrace{\int_{c - \infty\ic}^{c + \infty\ic}
{\expo{\pars{x - k}s} \over s^{n + 1}}{\dd s \over 2\pi\ic}}
_{\ds{\bracks{x - k > 0}\,{\pars{x - k}^{n} \over n!}}}\ =\
\left.{1 \over n!}\sum_{k = 0}^{n}\pars{-1}^{k}{n \choose k}
\pars{x - k}^{n}\,\right\vert_{\ k\ <\ x}
\\[5mm] = &\
\bbx{{1 \over n!}\sum_{k = 0}^{N}\pars{-1}^{k}{n \choose k}
\pars{x - k}^{n}\quad\mbox{where}\quad
N \equiv \min\braces{n,\left\lfloor x\right\rfloor}}
\end{align}
A: $\def\d{\mathrm{d}}\def\peq{\mathrel{\phantom{=}}{}}$The base case of induction is, in fact, $n = 1$.
Denote $S_n = \sum\limits_{k = 1}^n X_k$ for any $n$. For $n = 1$,$$
P(S_1 \leqslant x) = P(X_1 \leqslant x) = x_+. \quad \forall 0 \leqslant x \leqslant 1
$$
Suppose the proposition holds for $n$. For any $0 \leqslant x \leqslant n + 1$, because $S_n$ and $X_{n + 1}$ are independent, then\begin{align*}
&\peq P(S_{n + 1} \leqslant x) = P(S_n + X_{n + 1} \leqslant x)\\
&= \iint\limits_{y + z \leqslant x} f_{X_{n + 1}}(y) f_{S_n}(z) \,\d y\d z = \int_0^1 f_{X_{n + 1}}(y) \,\d y \int_0^{(x - y)_+} f_{S_n}(z) \,\d z\\
&= \int_0^1 P(S_n \leqslant (x - y)_+) f_{X_{n + 1}}(y) \,\d y = \int_0^1 P(S_n \leqslant (x - y)_+) \,\d y\\
&= \int_0^1 \frac{1}{n!} \sum_{k = 0}^{n - 1} \binom{n}{k} (-1)^k ((x - y)_+ - k)_+^n \,\d y. \tag{1}
\end{align*}
If $0 \leqslant x < 1$, then\begin{align*}
(1) &= \frac{1}{n!} \int_0^1 (x - y)_+^n \,\d y = \frac{1}{n!} \int_0^x (x - y)^n \,\d y\\
&= \frac{1}{(n + 1)!} x^{n + 1} = \frac{1}{(n + 1)!} \sum_{k = 0}^n \binom{n + 1}{k} (-1)^k (x - k)_+^{n + 1}.
\end{align*}
Otherwise, suppose $m = [x] \geqslant 1$, then\begin{align*}
(1) &= \frac{1}{n!} \sum_{k = 0}^{n - 1} \binom{n}{k} (-1)^k \int_0^1 ((x - y)_+ - k)_+^n \,\d y\\
&= \frac{1}{n!} \sum_{k = 0}^{m - 1} \binom{n}{k} (-1)^k \int_0^1 (x - y - k)^n \,\d y + \frac{1}{n!} \binom{n}{m} (-1)^m \int_0^1 (x - y - m)_+^n \,\d y.
\end{align*}
Because\begin{align*}
&\peq \frac{1}{n!} \sum_{k = 0}^{m - 1} \binom{n}{k} (-1)^k \int_0^1 (x - y - k)^n \,\d y\\
&= \frac{1}{n!} \sum_{k = 0}^{m - 1} \binom{n}{k} (-1)^k · \frac{1}{n + 1} ((x - k)^{n + 1} - (x - k - 1)^{n + 1})\\
&= \frac{1}{(n + 1)!} \left( \sum_{k = 0}^{m - 1} \binom{n}{k} (-1)^k (x - k)^{n + 1} - \sum_{k = 1}^m \binom{n}{k - 1} (-1)^{k - 1} (x - k)^{n + 1} \right)\\
&= \frac{1}{(n + 1)!} x^{n + 1} + \frac{1}{(n + 1)!} \sum_{k = 1}^{m - 1} \left( \binom{n}{k} + \binom{n}{k - 1} \right) (-1)^k (x - k)^{n + 1}\\
&\peq - \frac{1}{(n + 1)!} \binom{n}{m - 1} (-1)^{m - 1} (x - m)^{n + 1}\\
&= \frac{1}{(n + 1)!} \sum_{k = 0}^{m - 1} \binom{n + 1}{k} (-1)^k (x - k)^{n + 1} + \frac{1}{(n + 1)!} \binom{n}{m - 1} (-1)^m (x - m)^{n + 1},
\end{align*}
and\begin{align*}
&\peq \frac{1}{n!} \binom{n}{m} (-1)^m \int_0^1 (x - y - m)_+^n \,\d y = \frac{1}{n!} \binom{n}{m} (-1)^m \int_0^{x - m} (x - y - m)^n \,\d y\\
&= \frac{1}{n!} \binom{n}{m} (-1)^m · \frac{1}{n + 1} (x - m)^{n + 1} = \frac{1}{(n + 1)!} \binom{n}{m} (-1)^m (x - m)^{n + 1},
\end{align*}
then\begin{align*}
(1) &= \frac{1}{(n + 1)!} \left( \sum_{k = 0}^{m - 1} \binom{n + 1}{k} (-1)^k (x - k)^{n + 1} + \left( \binom{n}{m} + \binom{n}{m - 1} \right) (-1)^m (x - m)^{n + 1} \right)\\
&= \frac{1}{(n + 1)!} \sum_{k = 0}^m \binom{n + 1}{k} (-1)^k (x - k)^{n + 1} = \frac{1}{(n + 1)!} \sum_{k = 0}^{n + 1} \binom{n + 1}{k} (-1)^k (x - k)_+^{n + 1}\\
&= \frac{1}{(n + 1)!} \sum_{k = 0}^n \binom{n + 1}{k} (-1)^k (x - k)_+^{n + 1}.
\end{align*}
End of induction.
