Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.