Misanthropic Neighbors This week's 538 riddler is:


  The misanthropes are coming. Suppose there is a row of some number, N, of houses in a new, initially empty development. Misanthropes are moving into the development one at a time and selecting a house at random from those that have nobody in them and nobody living next door. They keep on coming until no acceptable houses remain. At most, one out of two houses will be occupied; at least one out of three houses will be. But what’s the expected fraction of occupied houses as the development gets larger, that is, as N goes to infinity?


If we define $E_N$ to be the expected number of occupied houses given $N$ houses in a row, then I could work out the recurrence as: $$E_N = 1 + \frac2N\sum_{i=1}^{N-2}E_i$$ just based on the open spaces left after we fix the first misanthrope moving in. However, I have no idea where to go from here - either in finding a closed form for $E_N$ that I can take the limit of or coming up with a different way of thinking about this problem. What's the next step?
Michael pointed out that an equivalent recurrence relation is 
$$ (n+1)E_{n+1} = n E_n + 2E_{n-1} + 1.$$
We can solve this with generating functions. Let 
$$f(x) = \sum_{n=0}^\infty E_n x^n.$$ 
Then we can construct a few useful quantities from this. First, note that
$$\frac{df}{dx} = \sum_{n=1}^\infty n E_n x^{n-1}.$$ 
Multiplying this by $x$ gives the useful relation
$$ x \frac{df}{dx} = \sum_{n=1}^\infty n E_n x^n.$$
Additionally, note that
$$ \frac{df}{dx} = E_1 + 2 E_2 x + 3E_3 x^2 + \cdots = E_1 + \sum_{n=1}^\infty (n+1) E_{n+1} x^n.$$
Multiplying $f(x)$ by $x$ gives us
$$x f(x) = \sum_{n=0}^\infty E_n x^{n+1} = \sum_{n=1}^\infty E_{n-1} x^n,$$
where we shifted the index in the last step.
Finally, from Taylor expanding about $x=0$, we have that
$$ \frac{x}{1-x} = \sum_{n=1}^\infty x^n.$$
Using this, we can write
$$ \frac{df}{dx} - E_1 = \sum_{n=1}^\infty (n+1)E_{n+1} x^n = \sum_{n=1}^\infty \left( nE_n + 2E_{n-1} + 1\right) = x \frac{df}{dx} + 2x f + \frac{x}{1-x}.$$
This gives us a first order differential equation for $f$. If there's only one house, then it clearly gets occupied, so $E_1 = 1$. Rearranging yields
$$ \frac{df}{dx} = \frac{2x}{1-x} f + \frac{1}{(1-x)^2}.$$
This differential equation can be solved exactly to give
$$f(x) = \frac{e^{-x} \sinh(x)}{(1-x)^2},$$
where we use the fact that $f(0) = E_0 = 0$ as our initial condition (since no houses can be occupied if there are no houses in the first place). Expanding this function in a Taylor series about $x=0$ gives the coefficients $E_n$ since
$$ E_n = \frac{1}{n!} \left.\frac{d^n f}{dx^n}\right|_{x=0}.$$
After playing with the series expansion a bit, you can show that
$$ E_n = \frac{n+1}{2} - \frac{1}{2}\sum_{k=0}^n (-2)^k \frac{(n-k+1)}{k!},$$
which is a nice closed form solution for $E_n$. From here, you can work out $\lim_{n\to \infty} E_n/n$ which should give you the expected fraction of occupied houses.
If there are n houses. Then 1 accepted event is 1 house out of n or 2 out of n all the way to n/2 out of n

So fraction of occupied houses is sum of 1,2,...n/2   Divided by nsqaured

Take a limit if n is infinity will be 25%