Suppose a gambler starts with one dollar and plays a game in which he or she wins one dollar with probability $p$ and loses one dollar with probability $1-p$. Let $f_n$ be the probability that he or she first becomes broke at time $n$ for $n = 0, 1, 2, \ldots$ Find a generating function for these probabilities?
Thanks :)
OK, the way this will work is to consider the ways how the gambler goes broke for an arbitrary $n$. This gambler must lose one more than he wins, and the last play results in a loss. Thus, $n$ must be odd for the probability to be nonzero, e.g., $n=2 k+1$. Further, the other $2 k$ plays are evenly distributed in wins and losses, so it is just a matter of figuring out how many combinations of wins and losses there are for a given $k$. This number is $(2 k)!/(k!)^2$, and the probability $f_{2 k+1}$ is
$$f_{2 k+1} = \frac{(2 k)!}{(k!)^2} p^k (1-p)^{k+1} = \binom{2 k}{k} p^k (1-p)^{k+1}$$
The generating function you want is
$$f(x) = \sum_{k=0}^{\infty} f_{2 k+1} \, x^{2 k+1} = (1-p) x\sum_{k=0}^{\infty}\binom{2 k}{k} [p(1-p) x^2]^k$$
It turns out that the series on the right is the Taylor series of a well-known function. This is your generating function:
$$f(x) = \frac{(1-p) x}{\sqrt{1-4 p (1-p) x^2}}$$