随笔题解 Ex. 1

校内 ACM 群里看到的申必数学题。

令 $p_{n, k}$ 表示给定 $n$ 的初值，那一坨东西等于 $k$ 的概率。有

$$p_{n, k} = \sum_{i = k - 1}^{n - 1} \frac{p_{n - 1, i}}{i + 1}$$

边界条件

$$p_{1, 1} = 1$$

假设

$$\lim_{n \rightarrow \infty} p_{n, k} = p_k$$

那么

$$p_k = \sum_{i = k - 1}^n \frac{p_i}{i + 1}$$

把右边那个求和为记作 $s_{k - 1}$。不难通过归纳法得出

$$p_k = k (k + 1) s_{k + 1}$$

再用这个柿子来回捣鼓一下可以得到

$$p_k = \frac{p_{k - 1}}{k - 1} = \frac{p_1}{(k - 1)!}$$

于是

$$\sum_{k \geqslant 1} p_k = \sum_{k \geqslant 1} \frac{1}{(k - 1)!} p_1 = e p_1 = 1$$

可以解得

$$p_1 = \frac{1}{e} \qquad p_k = \frac{1}{(k - 1)! e}$$