For the one-dimensional random walk model (7.1), a return to the origin S0 at time n occurs if Sn = 0. Note that a return to the origin can only happen if n is an even number.

(a) Show that the probability of a return to the origin at time 2m for any non-negative integer m is given by p2m = 1 22m

2m m



.

Note that p0 = 1.

(b) First return to the origin is said to have occurred at time 2m if m > 0, and S2k = 0 for all k < m. Denote the probability of the first return to the origin by f2m. For n ≥ 1, show that the probabilities p2k and f2k are related as follows:

p2k = f0 p2n + f2 p2(n−1) + ··· + f2n p0, where f0 = 0.