Bob starts with \$20. Bob flips a coin. Heads = Win +\$1 Tails = Lose -\$1. Stops if he has \$0 or \$100. Probability he ends up with \$0? I'm working on the extra credit for my Discrete Structures homework, but so far I have been unable to get a handle on the problem, even with help from 3rd parties, so I've decided to turn to you guys. The title explains the essentials, but I've included the full wording below, along with some notes.
Extra Credit Problem: Consider a game of gambling, where Bob started with 20 dollars in his pocket. Each time Bob wins, he will earn 1 dollar and each time he loses he will lose 1 dollar. A fair coin is flipped to decide win or loss, head = win & tails = loss. Bob will stop playing if his balance reaches 100 dollars or 0 dollars. What is the probability that Bob is ruined? (He loses all his money, as opposed to returning home with $100 in his pocket.)
The question is as such:
Let $P_k$ be the probability that Bob is ruined when he has k dollars in his pocket.
a. Write a recurrence relation for $P_k$
b. Solve the recurrence relation to find the answer. 
Note that $P_0 = 100\%$ (with no money Bob is ruined) and $P_{100} = 0\%$ (Because Bob returns with 100 dollars in his pocket and the game is over for Bob, so he is not ruined.)
Basically, I'm at a loss for how to create this recurrence relation. I started by investigating what information I might be able to derive from the given values of P, but honestly I'm not sure if this is really helpful. Solving the relations does not seem to be as difficult, but creating them has proved extremely challenging for me, if anyone has advice on a good way to think about this or some sort of methodology that helps you personally it would be well received.
Any help you could provide is much appreciated, I'd really like to get this extra credit or at least be able to understand how it works, because the professor generally doesn't go over the HW unless explicitly asked about a problem and even then it's very quickly, so that we have time in lecture to cover the new/current material. Also, the next time we have lecture will be the same day the HW is due, which limits the time I'll be able to spend with any hints given. 
 A: If he has $k$ dollars, there is a $50\%$ chance he loses a dollar and a $50\%$  chance he gains a dollar. Then the probabilities for those amounts determine how likely he will be ruined. The relation is
$$P_k=\frac12P_{k-1}+\frac12P_{k+1}$$
Which when combined with the initial conditions is
$$P_{k+1}=2P_k-P_{k-1}; \,P_0=1, P_{100}=0$$
From here you can solve the recurrence relation to get
$$P_k=1-\frac k {100}$$
A: For general problems of this kind I would recommend using a method based on deriving the recurrence relation (see e.g. the post by Pauly B). 
However in this particular case, where the probabilities of winning or losing a coin toss are exactly $50$% , there is a much simpler approach possible. Let us assume that we play this entire game many more times. Sometimes we win $80$ dollars, sometimes we lose $20$. Since the game is fair, we can immediately conclude that the probability of losing must be a factor $4$ larger. It follows that the probability of losing is $80$ %. 
A: Say he has $k$ dollars. Next round he is going to have either $k-1$ or $k+1$ dollars. Use the probabilities of these things happening together with $P_{k+1}$ and $P_{k-1}$ to create the recurrence.
A: Lets see : how can Bob be ruined with k dollars? What if his name is not Bob??? :) . Hope this will give you enough to do it yourself.
Let's see the scenarios:
For k=1, a single string $T$ will ruin him on the first trial , a string $HTT$ will ruin him on three trials. For 5 trials, we can have $HTHTT, HHTTT$, all starting with $H$ , notice we always have one more tail than heads in each ruin. Can you show that for $k$ dollars, there will be $k$ more heads than tails? 
