Each member of a population dies with probability $\frac12$ each day, what is the probability that there will be exactly $1$ person alive? Suppose that there are $n$ people alive in a population. Due to a deadly disease, each person dies with probability $\frac12$ each day (and there are no births). What is the probability that there will be exactly one person alive at some time?
Thoughts:
Let $p_k$ be the probability that the population reaches exactly $1$ person given that there are currently $k$ people alive. Then $p_0 = 0$ and $p_1 = 1$.
The probability of going from $k$ people alive to $k - j$ being alive (where $0 \leq j \leq k$) is the probability that $j$ die:
$$
\binom{k}{j} \left(\frac{1}{2}\right)^j \left(\frac{1}{2}\right)^{k - j} = \binom{k}{j} \left(\frac{1}{2}\right)^k
$$
And using conditional probability we have the recursion:
$$
p_k = \frac{1}{2^k} \binom{k}{0} p_k + \frac{1}{2^k} \binom{k}{1} p_{k - 1} + \cdots + \frac{1}{2^k} \binom{k}{k - 1} p_1 + \frac{1}{2^k} \binom{k}{k} p_0,
$$
or
$$
(2^k - 1)p_k = \binom{k}{1} p_{k - 1} + \cdots + \binom{k}{k - 1} p_1.
$$
Is it possible to solve a recursion like this? Is there a better way to solve the puzzle?

Here's a look at the problem using a generating function. As you point out, we have for $k > 1$:
$$
p_k = \frac{1}{2^k}\sum_{j=0}^k \binom{k}{j} p_j
$$
Note that this is off by $\frac12$ when $k=1$.
We define $f(z)$ to be the exponential generating function for $p_k$:
$$
f(z) = \sum_{k=0}^\infty \frac{p_k}{k!} z^k
$$
Then we observe:
$$
f(\frac z2)e^{\frac z2} + \frac{z}{2} = \sum_{k=0}^\infty \left(\sum_{j=0}^k \frac{p_j}{j!(k-j)!}\right)\left(\frac{z}{2}\right)^k + \frac{z}{2} = f(z)
$$
This gives us a recursion formula for $f(z)$. Inductively, we can see 
$$
f(z) = \frac{z}{2} + f(\frac z2)e^{\frac z2} = \frac{z}{2} + \frac{z}{4}e^{\frac{z}{2}} + f(\frac z4)e^{\frac {3z}4} = ... = \sum_{n=0}^{N-1} \frac{z}{2^{n+1}} e^{\frac{2^n - 1}{2^n} z} + f(\frac{z}{2^N}) e^{\frac{2^N - 1}{2^N} z} 
$$
Taking the limit as $N$ goes to infinity and recalling that $f(0) = p_0 = 0$, we determine:
$$
f(z) = \sum_{n=0}^{\infty} \frac{z}{2^{n+1}} e^{\frac{2^n - 1}{2^n} z} =\frac{z e^z}2 \sum_{n=0}^\infty \frac{e^{-2^{-n} z}}{2^n} 
$$
Thus we have $p_n = f^{(n)} (0)$ which works out to agree with the other answers:
$$
p_n = f^{(n)}(0) = \frac{n}{2}\sum_{k=1}^\infty  2^{-k}\left(1 - 2^{-k}\right)^{n-1}
$$
Note that this is increasing in $n$, and bounded above by $1$, hence it converges.
Now we show that $\lim p_k = \frac1{2\log 2}$. Notice that the sum $\sum_{n=0}^\infty \frac{e^{-2^{-n} z}}{2^n}$ is a left Riemann sum with interval divisions of length $1$ of the integral $\int_0^\infty 2^{-x} e^{-2^{-x} z} dx$, which evaluates to $\frac{1 - e^{-z}}{z\log 2}$. Call the integrand $g(x)$. Notice that $g(x)$ is increasing for $x < \log_2{z}$ and decreasing for $x > \log_2{z}$. Thus, for the smaller $x$, the integral underestimates the sum, and for the larger $x$, it overestimates. Changing to a right Riemann sum switches the over/underestimation but since all terms in the series go to $0$ exponentially as $z$ goes to infinity this doesn't change the asymptotics of the overall sum in $z$. Hence the sum and the integral are asymptotically equivalent. We therefore can conclude $$
f(z) \sim \frac{e^z}{2\log 2}
$$
which implies that if $p_n$ converges to a limit, it must converge to $\frac1{2\log 2}$. Since we have already established that $p_n$ is convergent, this shows that indeed $\lim\limits_{n\rightarrow\infty} p_n = \frac1{2\log2}$.
