(a) Show that the probability that a random walk of length 2m has a last return to the origin at time 2k, where 0≤k≤m, equals
22m(k2k)(m−k2m−2k)=u2ku2m−2k.
(The case k=0 consists of all paths that do not return to the origin at any positive time.) Hint: A path whose last return to the origin occurs at time 2k consists of two paths glued together, one path of which is of length 2k and which begins and ends at the origin, and the other path of which is of length 2m−2k and which begins at the origin but never returns to the origin. Both types of paths can be counted using quantities which appear in this section.
(b) Using part (a), show that if m is odd, the probability that a walk of length 2m has no equalization in the last m outcomes is equal to 1/2, regardless of the value of m. Hint: The answer to part (a) is symmetric in k and m−k.