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? 
 A: 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.
A: Ak = Permutations in which house K is occupied
 = Bk Permutations in which house K - 1 is empty (but not K-2) 
   + Ck Permutations in which house K - 1 and K -2 are empty 
So eK = Expected occupancy for House K = Ak / ( Ak+ Bk + Ck)
So eN = Sum of eK over N  / N
Model needs adjustment for corner cases for K = 1, 2 and N (Ck is 0)
But even without the adjustment, as N-> Infinity, Expected fraction -> 43% 
- as shown in the image
Misanthrope solution
A: This may be a bit naive, but here's my approach:
Each time a new misanthrope moves in, there are either 2 or 3 fewer houses available for the next misanthrope.
Case #1 - 3 fewer houses: If a misanthrope moves into a house, the next misanthrope can't move into that house or either neighboring house.
Case #2 - 2 fewer houses: If a misanthrope moves into a house that is 2 doors down from an occupied house, the common neighbor between them was already removed from the potential selection pool, so there are now 2 fewer houses to choose from.
Because housing selection is random, both cases occur with equal probability.  So, on average when a new misanthrope moves in, there are 2.5 fewer houses to choose for the next misanthrope.
If there are N houses, where N is large (so that we can ignore the houses on the ends), then we expect x number of misanthropes to be able to move in, where 2.5x = N.  You can think of this as the effective number of houses each misanthrope occupies.  The expectation value then is just x/N which is (1/2.5) or 2/5 or 0.4.
Thus, the expected fraction of occupied houses is 0.4 as N goes to infinity.
A: 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%
