I am working on Grimmet's Probability and Random Processes and encounter a problem of this style.
In a betting game, we start with a balance of \$k. For each turn, we bet \$1, and the winning probability is p. What is the probability that the ending balance will be \$n after d turns and that we never lose all money during the play?
My attempt was writing the winning probability as a recurrence relation $p_{n, d} = p\cdot p_{n-1, d-1} + q\cdot p_{n+1, d-1}$, but it does not seem solvable.
What might be the best way to approach this kind of problem? Thank you!