邮票收集问题正推递推式证明
考虑这样一个问题：有一个 \(n\) 面的骰子，扔到各面的概率相等。求期望扔几次可以使每一面都被扔到。对于这个问题，我们有递推式 \(f_i=f_{i-1}+\frac{n}{n-i+1}\)，其中 \(f_i\) 表示骰子有 \(i\) 面时的答案。然而可能是我太菜了，我已经找到的网上的证明都不太能看懂，于是自己整理了一下。
下面是证明。
设 \(f_i\) 表示已经扔到过 \(i\) 个不同的面时，期望的扔的次数。
称事件 \(A\) 为扔到了已经扔过的面，事件 \(B\) 为扔到了新的面。
考虑如何求出 \(f_i\)。此前已经扔到过 \(i-1\) 个面，那么有 \(P(A)=\frac{i-1}{n}\)；容斥一下，\(P(B)=1-P(A)=\frac{n-i+1}{n}\)。
于是我们有：
[*]扔 \(1\) 次后触发事件 \(B\) 的概率为 \(P(B)=\frac{n-i+1}{n}\)；
[*]扔 \(2\) 次后触发事件 \(B\) 的概率（即先发生 \(1\) 次事件 \(A\)，再发生一次事件 \(B\)）为 \(2\cdot P(A)\cdot P(B)=2\cdot\frac{i-1}{n}\cdot\frac{n-i+1}{n}\)；
[*]扔 \(3\) 次后触发事件 \(B\) 的概率（即先发生 \(2\) 次事件 \(A\)，再发生一次事件 \(B\)）为 \(3\cdot ^2\cdot P(B)=3\cdot(\frac{i-1}{n})^2\cdot\frac{n-i+1}{n}\)；
[*]……
观察得到，扔 \(k\) 次后触发事件 \(B\) 的概率为 \(k\cdot ^{k-1}\cdot P(B)=k\cdot (\frac{i-1}{n})^{k-1}\cdot \frac{n-i+1}{n}\)。
总的期望即为所有情况的加权和，即：
\^{k-1}\cdot P(B)\]
简要起见，设 \(q=P(A),p=P(B)\)。易得 \(p+q=1\)。
设 \(S=\sum\limits_{k=1}^{\infty}k\cdot q^{k-1}\)，易得 \(Ex=S\cdot p\)。
考虑将 \(S\) 变形。左右同乘 \(q\)：
\
两式相减：
\
即：
\[(1-q)S=\sum\limits_{k=0}^{\infty}q^{k}\]
右式是几何级数，那么由 \(|q|
页:
[1]