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