# Seeking analytic proof for $\sum_{n=r}^\infty \frac{1}{n!}\left[ n-1 \atop r-1 \right] = 1$

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

-

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

$$\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!)

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

-
+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