Consider the following game between two people. You start with a large stack of $n$ fair coins and flip all of them. For all coins that come up heads, toss those coins out the window and pass the remaining coins to the other player. Repeat this process until some player flips no heads. If a player fails to flip any heads, that player loses.
Question: Given a (large) value of $n$, determine which player is more likely to win this game.
Let $P_n$ be the probability of losing this game when you go first and start with $n$ coins. Then $P_0=1$ (you can’t flip heads if there aren’t any coins) and $P_n$ satisfies the following recurrence: $$P_n=1-\frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}P_{n-k}$$ While analyzing this, I found out pretty quickly that $P_n$ converges to $1/2$, so I let $P_n=1/2+Q_n$ and found the following recurrence for $Q_n$: $$Q_n=-\frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}Q_{n-k}$$ Some initial values of $Q_n$, starting with $Q_0=1/2$, are $$\frac{1}{2},\space 0,\space -\frac{1}{4},\space \frac{1}{64},\space \frac{5}{256},\space ....$$ Of course, the sign of $Q_n$ determines which player the game favors. Running a Python script, I determined that $Q_n$ changes signs after $n=8,17,35,72,145,291,583$ (at which point the numbers got too big for my program to handle, since it was dealing with binomial coefficients). I know that these values at which sign changes occur are $\sim c\cdot 2^k$ for some constant $c$.
What I need help with: Can anyone calculate the value of $c$, or come up with a clever way to calculate the sign of $Q_n$ for arbitrary large $n$?
What I know already: If it helps, I’ve found out that the EGF (exponential generating function) of $Q_n$, denoted $f$, satisfies the following functional equation: $$f(2x)=(1-e^x)f(x)$$ However, I’m not sure how to use this fact. Also, I know that the expected duration of the game (that is, the number of turns before someone loses) is asymptotically $\log_2(n)$ for large $n$. However, this fact is almost trivial because we expect half of the coins to come up heads (and be thrown out) after each turn.