recurrence relation arising from Magic the Gathering scenario [duplicate]

The solution is not the right one; in fact, you have a vanishingly small probability of ever catching your friend as $L$ becomes large.

Let $X_{i}$ for $i=1,2,3,\ldots$ be i.i.d. discrete random variables representing the lengths of your non-zero runs of heads. (Note that there are a.s. infinitely many such runs.) The probability distribution for each variable is $P[X=k]=2^{-k}$ for $k\ge 1$. So $P[X \ge k]=2^{1-k},$ and $P[X<k]=1-2^{1-k}$. After your $n$-th non-zero run of heads, you have $2X_n$ and your friend has $L+\sum_{i=1}^{n}X_{i}$; you have as much money as your friend if $$ X_{n}\ge L + \sum_{i=1}^{n-1}X_{i}, $$ which implies that $X_{n} \ge L + (n-1)$. That is, each time you flip at least one head and fail to catch your friend, your friend has at least one more dollar for you to match next time. Therefore, the probability of success is at most $$ P[X \ge L] + P[X < L]P[X \ge L+1]+P[X<L]^2P[X\ge L+2] + ...,$$ which is $$ P[X\ge L]\left(1 + \frac{1}{2}P[X<L]+\frac{1}{4}P[X<L]^2+...\right)=\frac{P[X\ge L]}{1-\frac{1}{2}P[X<L]}=\frac{2^{1-L}}{\frac{1}{2}+\frac{1}{2}2^{1-L}}=\frac{2^{2-L}}{1+2^{1-L}}. $$ For $L=0$ or $L=1$, the probability of success is obviously $1$. The above bound shows that the probability of success for $L=2$ is at most $2/3$, and that it decreases exponentially with $L$.

Edit: This is my (incorrect) attempt at a solution. The induction step is not valid at $L=2$.

Clearly $p(0) = 1$.

Use induction on $L$ and assume that $p(0),...,p(L-1) = 1$.

Case 1: $L$ is odd, $L = 2m-1.$ Then $$1 = p(m) = \frac{1}{2^{m-1}} + \sum_{i=1}^{m-1} \frac{p(m+i)}{2^i} = \frac{p(L)}{2^{m-1}} + \frac{1}{2^{m-1}} + \underbrace{\sum_{i=1}^{m-2} \frac{1}{2^i}}_{1 - 2^{2-m}}$$ and $p(L) = 1$ follows after multiplying through.

Case 2: $L = 2m-2$ is even. Then $$1 = p(m) = \frac{1}{2^{m-1}} + \sum_{i=1}^{m-1} \frac{p(m+i)}{2^i} = \frac{p(L)}{2^{m-2}} + \frac{p(L+1)}{2^{m-1}} + \frac{1}{2^{m-1}} + (1 - 2^{3-m})$$ and so $$2p(L) + p(L+1) = 3.$$ On the other hand, the inequalities $0 \le p(L), p(L+1) \le 1$ imply immediately $p(L) = 1$.

Define $Q(L) = P(L)/2^{L+1}$, so that your recurrence relation becomes : $Q(L) = 4^{-L} + \sum_{i=1}^{L-1} Q(L+i)$.

Then you get $Q(L+1) - Q(L) = (1-4).4^{-L-1} + Q(2L) + Q(2L+1) - Q(L+1)$, thus $2Q(L+1) - Q(L) = -3.4^{-L-1} + Q(2L) + Q(2L+1)$. Together with $Q(2) = 4^{-2} + Q(3)$, we have an equivalent system.

The space of solutions to this system of equations is a real affine space of infinite dimension : you can simply choose arbitrarily the values of every $Q(2L)$, then deduce the values of the $Q(2L+1)$. However there might not be many solutions with $Q(L) \in [0 ; 2^{-L-1}]$, and you are looking for the smallest one :

supposing you have a positive solution, $Q(2) = 4^{-2} + Q(3) \\ = 4^{-2} + 4^{-3} + Q(4) + Q(5) \\ = 4^{-2} + 4^{-3} + 4^{-4} + 2Q(5) + Q(6) + Q(7) \\ \ldots \\ \ge 4^{-2} + 4^{-3} + 4^{-4} + 2.4^{-5} + 3.4^{-6} + 6.4^{-7} + 11.4^{-8} + 22.4^{-9} + 42.4^{-10} + \ldots \\ = \sum a_2(n)4^{-n} = Q_0(2)$

We can do the same for higher $L$ and define a series $Q_0(L) = \sum a_L(n)4^{-n}$. Since we have a positive solution $Q_1(L) = 2^{-1-L}$, those series converge and $0 < Q_0(L) \le Q_1(L)$. The sequence $Q_0(L)$ is a solution of the system of equations, and it is in fact strictly smaller than the trivial solution $Q_1(L)$

After observing that the coefficients don't grow too fast, we can give a better bound for $Q_0(L)$ : for every $L$ we have for $n$ large enough $a_L(2n+1) = 2a_L(2n)$ and $a_L(2n) = 2a_L(2n-1)-a_L(n) < 2a_L(2n-1)$. For example with $L=2$, $Q_0(2) < 4^{-2} + 4^{-3} + 4^{-4} + 2.4^{-5} + 4.4^{-6} + 8.4^{-7} \ldots = 11.2^{-7} < 2^{-3} = Q_1(2)$, and thus $P_0(2) < 11/16$

To see that you're indeed looking for $P_0$, you just need to check that the probability to get as much money as your friend is the limit as $n \mapsto \infty$ of the probability of doing so in less than $n$ throws, which gives rises to essentially the same series.

The problem of giving a closed form expression for $P_0(2)$ and the others $P_0(L)$ is still unresolved.