The first n terms of the exansion of (2 - 1)-n are 2-n ( 1 + n/1! (1/2) + n(n + 1)/2! (1/2)2 + ... + n(n + 1) ... (2n -2)/(n - 1)! (1/2)n-1 ). Show that they sum to 1/2.
Solution
Consider a random walk on a two dimensional lattice. The particle starts at (0, 0). At each step it moves up 1 step with probability 1/2 and right one step with probability 1/2. Suppose that we stop when the particle reaches x = n or y = n.
Suppose the particle first reaches x = n at y = m (0 ≤ m < n). Then its final move must be from (n-1, m) to (n, m). In order to reach (n-1, m) it must make n+m-1 moves, m of which must be upwards. So the probability is (n+m-1Cm)(1/2)n+m. Thus the probability that it reaches x = n is (n-1)C0 (1/2)n + nC1 (1/2)n+1 + ... + (2n-2)C(n-1) (1/2)2n-1. The probability that it reaches y = n is the same. Note that it cannot reach the point (n, n) (because it reaches (n, n-1) or (n-1, n) first and stops). So each series must total 1/2.
Alternatively, a messy induction.
© John Scholes
jscholes@kalva.demon.co.uk
14 Jan 2002