The problem asks for: Let $N > i$. Starting with $i$ dollars, each time a fair coin is tossed if heads, then the gambler wins $2$ dollars and loses $1$ otherwise. What is the probability $P_i$ that the gamblers starting from $i$ goes broke before reaching $N$ dollars.
The question can be turned into a third order linear recurrence equation:
$$
0 = \frac12 P_{n+2} - P_n + \frac12 P_{n-1}
$$
with conditions $P_0 = 1$, $P_N = 0$.
The characteristic equation is
$$
0 = r^3 - 2r + 1
$$
which has three roots
$$
1, \frac{- 1 + \sqrt{5}}{2}, \frac{- 1 - \sqrt{5}}{2}.
$$
Thus the general solution is
$$
P_i = A + B (\frac{- 1 + \sqrt{5}}{2})^i + C (\frac{- 1 - \sqrt{5}}{2})^i
$$
for some $A, B, C$. The first boundary condition forces $A + B + C =1$. I am not sure how to deduce the coefficients when I have only one boundary condition left... any explanation is appreciated. thank you
The process can end at three values: $0,N$ and $N+1$. Thus there are three relevant boundary values: $P_0=1$ and $P_N=P_{N+1}=0$.
One can avoid solving equations as follows.
Write $x_n:=P_n-P_{n+1}$ for $n=0,1,\dots,N$. Then for $1 \le n \le N-1$, we have $$P_n=(P_{n-1}+P_{n+2})/2 =(P_n+x_{n-1}+P_n-x_n-x_{n+1})/2 \,,$$ so $x_{n-1}=x_n+x_{n+1}$. Thus $y_k=x_{N-k}$ satisfy the Fibonacci recurrence $$y_{k+1}=y_k+y_{k-1} \quad \text{for} \quad k=1,\dots, N-1 \,.$$ Since $y_0=0$, we infer that $y_k=y_1 F_k$ for $k=0,\dots, N$, where $F_0=0, F_1=1, F_2=1,\dots$ is the Fibonacci sequence. Recall that $$ F_1+\dots +F_k=F_{k+2}-1 \,,$$ which can be easily verified inductively. Therefore, for $m \in [0,N]$ we have $$P_m=P_N+ y_1+\dots +y_{N-m} = y_1 (F_{N-m+2}-1) \,.$$ Taking $m=0$ yields $1=y_1(F_{N+2}-1)$, so we conclude that $$\forall m \in [0,N], \quad P_m=\frac{F_{N-m+2}-1}{F_{N+2}-1} \,.$$