What's the probability of winning a raffle with extra lives? My local ACM club has prizes at every meeting. You get 1 life for showing up at the meeting, and 1 extra for solving the programming challenge. The script chooses one of the remaining people, decrements the number of lives remaining (removing if that number is 0), and repeats until there is 1 person left.
This question was asked after today's meeting: "What is the probability that I will win having 2 lives verses just 1?" Curious, I thought I'd compute the probability of me winning assuming I always have 2 lives.

Let's define $P(n, k)$ to be the probability of me winning given that there are $n$ people in the drawing (including me) and $k$ people (of those $n$, not including me) who have 2 lives. Let's work on $P(n, 0)$ first:
$$
\def\x{\times}
\begin{align}
P(1, 0) &= 1\\
P(2, 0) &= 1/2 \x 1/2 + 1/2 \x 1 = \frac34\\
P(3, 0) &= 1/3 \x 1/3 + 2/3 \x P(2, 0) = \frac{11}{18}\\
P(n, 0) &= \frac{1}{n^2} + \frac{n - 1}{n} P(n - 1, 0)
\end{align}
$$
Mathematica helpfully allows me to remove the recursion to get:
$$
P(n, 0) = \frac{\gamma + \psi(1 + n)}{n}
$$
Where $\gamma$ is the Euler-Mascheroni constant and $\psi$ is the digamma function.
Naturally, I want to generalize this to all $k$. So let's move on to $k = 1$:
$$
\begin{align}
P(2, 1) &= 1/2\\
P(n, 1) &= \frac{1}{n (n - 1)} (1 - P(n, 0)) + \frac{n - 2}{n} P(n - 1, 1) + \frac{1}{n} P(n, 0)
\end{align}
$$
Next, I made the leap to general $k$:
$$
\begin{align}
P(k+1, k) &= \frac{1}{k+1}\\
P(n, k) &= \frac{1}{n (n-k)} (1 - k\, P(n, k-1)) + \frac{n-k-1}{n} P(n-1, k) + \frac{k}{n} P(n, k-1)
\end{align}
$$
Now I have never received education on probability other than high school Algebra, so I don't know if I worked this out correctly. Did I correctly derive the formula?
Now all that remains is to remove the recursion on this...
 A: The result looks correct to me.
$$P(k+1, k) = \frac{1}{k+1}$$
because if all $k+1$ people have the same number of lives, by symmetry they have the same probability of winning.
$P(n, k)$ for $n > k$ is a weighted sum of three cases:


*

*The case where I'm the next person to lose a life. This case has probability $\frac{1}{n}$ and would lead to a situation where I'm one of $n-k$ people on 1 life, and there are $k$ people on two lives. Each of those $k$ people will then have probability $P(n,k-1)$ of winning, and the remaining $\left(1 - kP(n,k-1)\right)$ is divided equally among the $(n-k)$ people on 1 life.

*The case where someone on 1 life loses it. This case has probability $\frac{n-k-1}{n}$ and would lead to a situation with $n-1$ people in total, of whom I and $k$ others have two lives, whence my probability of winning would become $P(n-1,k)$.

*The case where someone else on 2 lives loses one. This case has probability $\frac{k}{n}$ and leads to a situation where there are still $n$ players in total, but one fewer opponent on 2 lives, whence my probability of winning would become $P(n,k-1)$.


These correspond exactly to the sum you give for the recurrence.

Note: $P(n, 0)$ can equivalently be stated in terms of the $n$th harmonic number, $$H_n = 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n} =\sum_{k=1}^n \frac{1}{k}$$
To see this, note that $$P(n, 0) = \frac{1}{n^2} + \frac{n - 1}{n} P(n - 1, 0)$$ can be rewritten as $$\begin{eqnarray}
nP(n, 0) & = & \frac{1}{n} + (n - 1) P(n - 1, 0) \\
& = & \frac{1}{n} + \frac{1}{n-1} + (n - 2) P(n - 2, 0) \\
& = & \frac{1}{n} + \frac{1}{n-1} + \ldots + P(1, 0) \\
& = & H_n \\
\end{eqnarray}$$
