Introduction to Probability · Problem 12.1.11

Random Walks — Grinstead & Snell

Mathematics — Probability · random-walks-higher-dimensions

Problem

Prove that

u_{2n}^{(2)} = \frac{1}{4^{2n}} \sum_{k=0}^{n} \frac{(2n)!}{k!k!(n-k)!(n-k)!},

and

u_{2n}^{(3)} = \frac{1}{6^{2n}} \sum_{j,k} \frac{(2n)!}{j!j!k!k!(n-j-k)!(n-j-k)!},

where the last sum extends over all non-negative

j

and

k

with

j+k \leq n

. Also show that this last expression may be rewritten as

\frac{1}{2^{2n}} \binom{2n}{n} \sum_{j,k} \left(\frac{1}{3^n} \frac{n!}{j!k!(n-j-k)!}\right)^2.