Drug addict

[radosr]

A drug addict has a bottle of n pills and initially wishes to take one pill per day. However, he is a bit short on money lately, so he plans to take only half a pill per day. Every day he picks a pill from the bottle at random. If it is a whole pill, he cuts it in half, takes half a pill, and puts the other half back in the bottle. If it is half a pill that he picked, he just takes it. He does this until the bottle is empty. What is the expected maximum number of half pills in the bottle?

 

[Brad Warren]

Let E(n, m) be the expected maximum number of half pills after starting with n whole pills and m half pills. The answer we're looking for is E(n, 0). I tried to solve for it in terms of E(n-1, 0).

This is as far as I got:
E(n, 0) = 2/(n^2 (n-2)!) + (1 - (n-1)(n-2)/n^2)E(n-1, 0) + (n-1)(n-2)/n^2 E(n-3, 3)

I couldn't find a simple expression for E(n-3, 3), but
E(0, 3) = 3 for n = 3
E(1, 3) = 13/4 for n = 4
E(2, 3) = 711/200 for n = 5

Using this formula, and starting with the trivial E(1, 0) = 1,
E(2, 0) = 1/2 + E(1, 0) = 3/2
E(3, 0) = 2/9 + 7/9 E(2, 0) + 2/9 E(0, 3) = 37/18
E(4, 0) = 1/16 + 5/8 E(3, 0) + 3/8 E(1, 3) = 739/288
E(5, 0) = 1/75 + 13/25 E(4, 0) + 12/25 E(2, 3) = 3.0540

It wouldn't be difficult to compute the expected maximum recursively, but I'm not sure how to find a closed-from solution.