George Polya's theorem on the number of shortest routes on Pascal's Triangle

Question

How does one prove George Polya's theorem in Pascal's Triangle that the number of shortest routes from the point representing $_0C_0$ to the point representing $_nC_r$ is $_nC_r$?

Here, $_nC_r = \frac{n!}{(n-r)!r!}$.

Answer 1

We can do this by induction!

Base case. Let $n=1$. To get from ${0\choose0}$ to ${1\choose0}$ and from ${0\choose0}$ to ${1\choose 1}$ there is only one path in each case, since ${1\choose0}$ and ${1\choose1}$ are both adjacent to ${0\choose0}.$

Inductive hypothesis. Now, assume that the number of paths from ${0\choose0}$ to ${k\choose r}$ is ${k\choose r}$ for some $k\in\mathbb{Z}^+$.

Now, how many ways are there to get to ${k+1\choose r}$? First, we note that in order to get to ${k+1\choose r}$, we must come from either ${k\choose r}$ or ${k\choose r-1}$, since they are directly to the upper-right and upper-left, respectively. Therefore, there are ${k\choose r} + {k\choose r-1} = {k+1\choose r}$ ways to get to ${k+1\choose r}$.

Note that in the above argument, $r\ne k+1$. To get this case, we see that the only choice is to run along the right edge, giving us a single path.

To really flesh out this proof, you should prove two things I glossed over:

• Any path to ${n\choose k}$ must come from ${n-1\choose k}$ of ${n-1\choose k-1}$.

• ${n\choose k} = {n-1\choose k}+{n-1\choose k-1}$.