Tony Lezard asked me the following question which seemed like it should not be too hard but which I did not immediately see how to answer. Define $f(n,k)$ recursively by $f(1,k) = 1$ and

$$f(n,k) = \frac{1}{1-(1-1/k)^n} \sum_{r=1}^{n-1} \binom{n}{r} \left(\frac{1}{k}\right)^{n-r} \left(1 - \frac{1}{k}\right)^r f(r,k).$$

What can we say about $\lim_{n\to\infty} f(n,k)$? Even the special case $k=2$ would be interesting:

$$f(n,2) = \frac{1}{2^n-1} \sum_{r=1}^{n-1} \binom{n}{r} f(r,2).$$

Tony Lezard asked me the following question which seemed like it should not be too hard but which I did not immediately see how to answer. Define $f(n,k)$ recursively by $f(1,k) = 1$ and

$$f(n,k) = \frac{1}{1-(1-1/k)^n} \sum_{r=1}^{n-1} \binom{n}{r} \left(\frac{1}{k}\right)^{n-r} \left(1 - \frac{1}{k}\right)^r f(r,k).$$

What can we say about $\lim_{n\to\infty} f(n,k)$? Even the special case $k=2$ would be interesting:

$$f(n,2) = \frac{1}{2^n-1} \sum_{r=1}^{n-1} \binom{n}{r} f(r,2).$$

Addendum. As explained in Tony Lezard’s answer below, $f(n,k)$ arises as the termination probability of a certain recursive elimination process. The process in the case $n=2$ was studied by Helmut Prodinger, “How to select a loser,” Discrete Math. 120 (1993), 149–159, although Prodinger does not seem to have analyzed $f(n,2)$ specifically. For other references, see the MO question on The Dance Marathon Problem.