Convolution of i.i.d. with uniform distribution

Question

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.

Answer 1

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

Answer 2

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