# Density of the sum of $n$ uniform(0,1) distributed random variables

I am working on the following problem:

Let $X_1, X_2, \ldots, X_n, \ldots$ be iid. random variables, each of Uniform$(0,1)$ distribution. Denote by $f_n(x)$ the density of the random variable $S_n := \sum_{k = 1}^n X_k$. Then \begin{align*} f_n(x) = \frac{1}{(n-1)!} \sum_{k = 0}^{[x]} (-1)^k \binom{n}{k} (x-k)^{n-1}, \end{align*} where $[x]$ denotes the floor function.

I tried this, but I think something went wrong:

Prove by induction. For $n = 1$ \begin{align*} f_1(x) = \frac{1}{(1-1)!} \sum_{k = 0}^{[x]} (-1)^k \binom{1}{k} (x-k)^{1-1} &= \sum_{k = 0}^{[x]} (-1)^k \binom{1}{k} =\begin{cases} 1, & 0 \le x < 1 \\ 0, & \text{otherwise} \end{cases} \end{align*} Furthermore \begin{align*} f_{n+1}(x) &= \mathbb P(S_{n+1} = x) = \mathbb P(S_n + X_{n+1} = x) \\ &= \sum_{m = 0}^{\infty} \mathbb P(S_n + X_{n+1} = x \mid X_{n+1} = m) \mathbb P(X_{n+1} = m) \\ &= \sum_{m = 0}^{\infty} \mathbb P(S_n + m = x) \cdot 1_{[0,1]}(m) = \mathbb P(S_n = x) + \mathbb P(S_n = x-1) \\ &= \frac{1}{(n-1)!} \sum_{k = 0}^{[x]} (-1)^k\binom{n}{k}(x-k)^{n-1} + \frac{1}{(n-1)!} \sum_{k = 0}^{[x-1]} (-1)^k\binom{n}{k}(x-1-k)^{n-1} \\ &= \frac{1}{(n-1)!}\left(\sum_{k = 0}^{[x]} (-1)^k\binom{n}{k}(x-k)^{n-1} + \sum_{k = 0}^{[x]-1} (-1)^k\binom{n}{k}(x-1-k)^{n-1}\right) \\ &= \frac{1}{(n-1)!}\left(x^{n-1}+\sum_{k = 1}^{[x]} (-1)^k\binom{n}{k}(x-k)^{n-1} + \sum_{k = 1}^{[x]} (-1)^{k-1}\binom{n}{k-1}(x-1-(k-1))^{n-1}\right) \\ &= \frac{1}{(n-1)!}\left(x^{n-1}+\sum_{k = 1}^{[x]} (-1)^k\binom{n}{k}(x-k)^{n-1} - (-1)^{k}\binom{n}{k-1}(x-k)^{n-1}\right). \end{align*}

How can I solve this?

Edit: \begin{align*} f_{n+1}(x) &= (f_n * f_{X_{n+1}})(x) = \int_{-\infty}^\infty f_{n}(y) f_{X_{n+1}}(x-y) \, dy \\ &= \int_{-\infty}^\infty \frac{1}{(n-1)!} \sum_{k = 0}^{[y]} (-1)^k \binom{n}{k}(y-k)^{n-1} \cdot 1_{(0,1)}(x-y) \, dy \\ &= \frac{1}{(n-1)!} \int_{-\infty}^{\infty} \sum_{k = 0}^{[y]} (-1)^k \binom{n}{k}(y-k)^{n-1} \cdot 1_{(x-1, x)}(y)\, dy \\ &= \frac{1}{(n-1)!} \int_{x-1}^{x} \sum_{k = 0}^{[y]} (-1)^k \binom{n}{k}(y-k)^{n-1} \, dy \end{align*}

I want to swap the sum and the integral, but the sum depends on $y$.

-
In fact you are saying that $f_{n+1}(x)=0$. This because in your question it equalizes $P(S_{n+1}=x)$. You could use: $f_{n+1}\left(x\right)=\int f_{n}\left(x-u\right)f_{1}\left(u\right)du=\int_{0}^{1}f_{n}\left(x-u\right)du$ –  drhab Dec 27 '13 at 13:11
Ah thanks, I see I had a totally wrong approach. I will try yours. –  numerion Dec 27 '13 at 13:29
I've edited, please check. –  numerion Dec 27 '13 at 15:21
You have $x-1<y<x$. Then$\left\lfloor y\right\rfloor \in\left\{ \left\lfloor x-1\right\rfloor ,\left\lfloor x\right\rfloor \right\}$ and these cases must be discerned. If $x-1<y<\left\lfloor x\right\rfloor$ then $\left\lfloor y\right\rfloor =\left\lfloor x-1\right\rfloor$ and if $\left\lfloor x\right\rfloor \leq y<x$ then $\left\lfloor y\right\rfloor =\left\lfloor x\right\rfloor$. So split up the integral: $\int_{x-1}^{x}...dy=\int_{x-1}^{\left\lfloor x\right\rfloor }...dy+\int_{\left\lfloor x\right\rfloor }^{x}...dy$. –  drhab Dec 27 '13 at 16:02

$\int f_{n}\left(y\right)f_{1}\left(x-y\right)dy=\int\frac{1}{\left(n-1\right)!}\sum_{k=0}^{\left\lfloor y\right\rfloor }\left(-1\right)^{k}\binom{n}{k}\left(y-k\right)^{n-1}1_{\left(0,1\right)}\left(x-y\right)dy$

$=\frac{1}{\left(n-1\right)!}\sum_{k=0}^{\left\lfloor x-1\right\rfloor }\left(-1\right)^{k}\binom{n}{k}\int_{x-1}^{\left\lfloor x\right\rfloor }\left(y-k\right)^{n-1}dy+\frac{1}{\left(n-1\right)!}\sum_{k=0}^{\left\lfloor x\right\rfloor }\left(-1\right)^{k}\binom{n}{k}\int_{\left\lfloor x\right\rfloor }^{x}\left(y-k\right)^{n-1}dy$

$=\frac{1}{n!}\sum_{k=0}^{\left\lfloor x-1\right\rfloor }\left(-1\right)^{k}\binom{n}{k}\left[\left(\left\lfloor x\right\rfloor -k\right)^{n}-\left(x-1-k\right)^{n}\right]+\frac{1}{n!}\sum_{k=0}^{\left\lfloor x\right\rfloor }\left(-1\right)^{k}\binom{n}{k}\left[\left(x-k\right)^{n}-\left(\left\lfloor x\right\rfloor -k\right)^{n}\right]$

$=\frac{1}{n!}\sum_{k=0}^{\left\lfloor x-1\right\rfloor }\left(-1\right)^{k}\binom{n}{k}\left[\left(x-k\right)^{n}-\left(x-1-k\right)^{n}\right]+\left(-1\right)^{\left\lfloor x\right\rfloor }\binom{n}{\left\lfloor x\right\rfloor }\left(x-\left\lfloor x\right\rfloor \right)^{n}$

$=\frac{1}{n!}\sum_{k=0}^{\left\lfloor x\right\rfloor }\left(-1\right)^{k}\binom{n}{k}\left(x-k\right)^{n}+\frac{1}{n!}\sum_{k=0}^{\left\lfloor x\right\rfloor }\left(-1\right)^{k}\binom{n}{k-1}\left(x-k\right)^{n}$ (here $\binom{n}{-1}:=0$)

$=\frac{1}{n!}\sum_{k=0}^{\left\lfloor x\right\rfloor }\left(-1\right)^{k}\left[\binom{n}{k}+\binom{n}{k-1}\right]\left(x-k\right)^{n}$

$=\frac{1}{n!}\sum_{k=0}^{\left\lfloor x\right\rfloor }\left(-1\right)^{k}\binom{n+1}{k}\left(x-k\right)^{n}$

pfffffff.....In my language: een echte 'rotsom'.

-

Here is a totally different method. So you want to compute $I*I*\cdots*I = I^{*n}$, where $I$ is the indicator function of $[0,1]$, and the $*$ denotes convolution, and the superscript $I^{*n}$ denotes the $n$th convolution with itself.

Differentiate $n$ times. You will get $(\delta_1 - \delta_0)^{*n}$, where $\delta_x$ denotes the Dirac delta function centered at $x$. This is easily expanded using the Binomial Theorem, remembering that $\delta_x * \delta_y = \delta_{x+y}$.

Now take the indefinite integral $n$ times. The tricky bit is how to consider the constants of integration. But the easiest boundary condition is to suppose that all the derivatives disappear at $-\infty$. In this way $\int^n \delta_y (dx)^n = \frac1{(n-1)!} (x-y)_+^{n-1}$, where $x_+$ denotes $\max\{x,0\}$. (Please excuse the notation for $n$th indefinite integral.)

I got this method from an exercise in the book by Nakhle Asmar on Partial Differential Equations.

-