Coin Flip Problem So my friend gave me this question this other day, and I've tried to start it (I'll show my logic below), but I couldn't find any efficient way to do the problem.

You start out with 1 coin. At the end of each minute, all coins are flipped simultaneously. For each heads that is flipped, you get another coin. But for every tails that is flipped, a coin is lost. (Note any new coins are not flipped until the next moment). Once there are no more coins remaining, the process stops. What is the probability that exactly after 5 minutes (that's 5 sets of flips), that the process will have stopped (so no earlier or no later)?

I've taken a few approaches to this problem. What I've tried to do is to find the total amount of possibilities for each amount of coins by the 5th moment, and then multiply that by the probability that all coins will be vanished on the 5th moment. But I'm just not able to calculate how many possible ways exist to get to each amount of total coins by the end. Does anyone have any other ideas, or perhaps a formula to solve this problem?
 A: Let $q(k)$ be the probability that the process initiated by a single coin will stop
on or before $k$ minutes. We write $q(k+1)$ in terms of $q(k)$:
\begin{align}
q(1) &= 1/2\\
q(2) &= (1/2) + (1/2)q(1)^2 = 5/8\\
q(3) &= (1/2) + (1/2)q(2)^2 = 89/128\\
q(4) &= (1/2) + (1/2)q(3)^2 = 24305/32768\\
q(5) &= (1/2) + (1/2)q(4)^2 = 16644\hspace{0pt}74849/2147483648
\end{align}
and the probability we stop at 5 minutes exactly is:
$$q(5)-q(4)  = \frac{71622369}{2^{31}} \approx 0.0333517645...$$
A: This is too long for a reply to my earlier comment, and since it provides an alternate answer, I'm posting it that way.
I confirmed Michael's answer by the brute-force approach suggested by Calvin and Wim in their answers.
I set this up as a Markov process where the state is the number of coins. (There can be from $0$ through $16$ coins after $4$ steps, which is all I needed.) The probability of transition from $i$ coins to $j$ coins is $0$ if $j$ is odd and ${i\choose {j\over2}}\cdot{1\over2^i}$ if $j$ is even. (This is left as an exercise to the reader!)
Then (thanks, Mathematica!) I computed $M^4$ for the transition matrix $M$ of the above probabilities. Then $(M^4)_{1j}$ is the probability of there being $j$ coins after $4$ steps, and thus the probability of ending after exactly $5$ steps is $\sum_{j=1}^{16}(M^4)_{1j}\cdot{1\over2^j}$. (Note that the sum doesn't start at $j=0$ because that would correspond to the game ending before the fifth step.) The nonzero terms $\left(M^4\right)_{1j}$ in the calculation ($j=2,4,6,\dots,16$), for anyone interested, are $\left(\frac{445}{4096},\frac{723}{8192},\frac{159}{4096},\frac{267}{16384},\frac{19}{4096},\frac{11}{8192},\frac{1}{4096},\frac{1}{32768}\right)$.
A: (This is not a complete solution).
There's always the brute force approach.
At time $t$, if there are $n$ coins, then the probability that there are $2k$ coins at time $t+1$ is ${n \choose k } \times \frac{1}{2^n}$.
We can come up with the following table for probability at time $t$, we have $n$ number of coins:
$\begin{array} { l | l l l l l}
 & 1 & 2 & 3 & 4 & 5  \\   
\hline   
0 & \frac{1}{2} & \frac{1}{2} \times 1 + \frac{1}{2} \times \frac{1}{4} = \frac{5}{8} & \frac{5}{8} \times 1 + \frac{1}{4} \times \frac{1}{4} + \frac{1}{8} \times \frac{1}{16}  = \frac{89}{128}       \\
2 & \frac{1}{2} &  \frac{1}{2} \times \frac{2}{4} = \frac{1}{4}         \\
4 &            & \frac{1}{2} \times \frac{1}{4} = \frac{1}{8} \\
6 &           \\
8 &           \\
10 &            
\end{array}$
Yes, it gets long and ugly, which is why I didn't complete it for 5. But, at least it could be done.
A: Try to use a Markov Matrix M. States are 0, 1, 2, 3, 4, ... and 32 coins. Calculate the probabilities for all transitions. The column represent the state before flipping the coins. The rows represent the state after flipping the coins. You will have a $33 \times 33$ matrix.
\begin{bmatrix}
1 & 0.5 & 0.25 & . & ... & .\\
0 & 0 & . & . & ... & .\\
0 & 0.5 & . & . & ... & .\\
0 & 0 & . & . &... & .\\
0 & 0 & . & . &... & .\\
...\\
0 & 0 & . &  . &... & .\\
\end{bmatrix}
The initial state is 1 coin and can be represented as a matrix A
\begin{bmatrix}
0 \\
1 \\
0 \\
0 \\
... \\
0 \\
\end{bmatrix}
The distribution after 5 rounds can be calcalated by $M^5 \times A$.
This way you can calculate the probabilities of having zero coins after 5 flips. You will still have to subtract the probabilities for having 0 coins after 1, 2, 3 or 4 flips.
