Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

In Blom, Holst, Sandell, "Problems and snapshots from the world of probability", section 9.4, a model of records is discussed:

Elements are ordered in a sequence of increasing length according to some rule that leads to exchangeability. At each step, the element is inserted at its proper place among those already ordered. If an element comes first, it is called a record. The position of $r$-th record is denoted $N_r$. Naturally $N_1 = 1$.

The following probability is then derived: $$ \mathbb{P}(N_r = n) = \frac{1}{n!} \left[ n-1 \atop r-1 \right] I\left( n \geqslant r\right) $$ where $\left[ n \atop r \right]$ denotes the unsigned Stirling number of the first kind.

Question: How does one analytically prove that this probability mass function is normalized for all integer $r \geqslant 2$, i.e. $$ \sum_{n=r}^\infty \frac{1}{n!} \left[ n-1 \atop r-1 \right] = 1 $$

Using $\left[ n-1 \atop 1 \right] = (n-2)!$, and $\left[ n-1 \atop 2 \right] = H_{n-2} \cdot (n-2)!$, the normalization follows for special cases of $r=2$ and $r=3$.

share|cite|improve this question
up vote 6 down vote accepted

On the one hand,

$$\binom{u}{n}=\frac{1}{n!}\sum_{l=0}^ns(n,l)u^l=\frac{1}{n!}\sum_{l=0}^n \left[n\atop l\right](-1)^{n-l}u^l. \tag{1}$$

So on the other hand,

$$-\frac{1}{z}\int_0^z (1-\tau)^{-u}d\tau=\sum_{n=0}^\infty \frac{(-z)^n}{n+1}\binom{-u}{n}=\sum_{n=0}^\infty\sum_{l=0}^n\frac{1}{(n+1)!}\left[n\atop l\right]z^nu^l. \tag{2}$$

And on your third hand,

$$\frac{1}{z}\int_0^z (1-\tau)^{-u}d\tau=\frac{1}{z}\frac{(1-z)^{1-u}-1}{1-u}. \tag{3}$$

Plugging in $z=1$,

$$\sum_{k=0}^\infty u^k=\sum_{l=0}^\infty \left(\sum_{n=l}^\infty \frac{1}{(n+1)!}\left[n\atop l\right]\right)u^l. \tag{4}$$

Equating coefficients gives the result. (I'll have time to clarify/elaborate/salvage later. My hand ... or hands were forced by the answer of Mr. Andrews!)

share|cite|improve this answer
+1 Thank you! The derivation is clean and crystal clear. I do not think you would need to salvage it:) – Sasha May 31 '12 at 18:10
And special thanks for leading me to discovery of \atop – Sasha May 31 '12 at 18:11

Define $$g_r(y) = \sum_{n=r}^\infty \frac{1}{n!}\begin{bmatrix} n-1 \cr r-1\end{bmatrix}y^n$$

Define $$G(y,z) = \sum_{r=1}^\infty (-1)^r g_r(y)z^{r-1}$$

Swapping terms we get:

$$G(y,z) = \sum_{n=1}^\infty \frac{(-1)^n y^n}{n!}\sum_{r=1}^{n} (-1)^{n-r} \begin{bmatrix} n-1 \cr r-1\end{bmatrix}z^{r-1}$$

The inner sum is just $(z)_{n-1}=\frac{(1+z)_n}{1+z}$, so we get:

$$G(y,z) = \frac{1}{1+z} \sum_{n=1}^\infty (-1)^ny^n \frac{(1+z)_n}{n!}$$

Which is just:

$$G(y,z) = \frac{1}{1+z} ((1-y)^{1+z}-1)$$,

where $|y|<1$ and $|z|<1$

Now, for any real $z\in(-1,1)$, $\lim_{y\to 1} G(y,z) = \frac{-1}{1+z} = \sum_{r=1}^\infty (-1)^{r}z^{r-1}$ so it seems that $g_r(y)\to 1$ as $y\to 1$, but that last step might be hard to formalize.

share|cite|improve this answer
+1 Thanks for the answer. I should have known to look for the bivariate generating function. @anon drove the argument home. – Sasha May 31 '12 at 18:13

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.