Introduction to Probability · Problem 12.1.12

Random Walks — Grinstead & Snell

Mathematics — Probability · random-walks-combinatorial-identity

Problem

Prove that if

n \geq 0

, then

\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}.

Hint: Write the sum as

\sum_{k=0}^{n} \binom{n}{k} \binom{n}{n-k}

and explain why this is a coefficient in the product

(1+x)^n(1+x)^n

. Use this, together with Exercise 11, to show that

u_{2n}^{(2)} = \frac{1}{4^{2n}} \binom{2n}{n} \sum_{k=0}^{n} \binom{n}{k}^2 = \frac{1}{4^{2n}} \binom{2n}{n}^2.