A double counting proof of a sum identity

Question

I am trying to prove the following identity combinatorialy $$\sum_{k=0}^{n} \frac{(2n)!}{(k!)^2((n-k)!)^2}={2n \choose n}^2$$ The interpretation I have of the right side is that it was a $n \times n$ lattice walk from (0,0) to (n,n) and then from (n,n) back to (0,0) but I am unable to make sense of the LHS like this

I would appreciate any help and suggestions regarding my problem

Answer 1

Both sides answer the question

How many ways are there to make a walk of length $2n$ in the plane which starts where it ends, and where each step is one unit either up, down, left or right?

On the one hand, suppose that $k$ of the steps of the walk are up steps. This means there must also be $k$ down steps to restore the $y$ displacement to zero. Since the left and right steps must balance as well, there are then $n-k$ left steps and $n-k$ right steps. The number of ways to choose an ordering for these steps is $(2n)!/(k!\cdot k! \cdot (n-k)!\cdot (n-k)!)$, which is then summed over $k$.

On the other hand, define the vectors $$ v=(\tfrac12,\tfrac12),\qquad w=(\tfrac12,-\tfrac12) $$ Note that the four vectors of the form $$ \pm v\pm w $$ are exactly the four unit vectors pointing up, down, left and right. Therefore, you can uniquely determine a walk of length $2n$ in the plane as follows:

• Choose a sequence $s$ of length $2n$, where $n$ of the entries are $+v$ and $n$ are $-v$. This can be done in $\binom{2n}n$ ways.

• Choose a sequence $t$ of length $2n$, where $n$ of the entries are $+w$ and $n$ are $-w$. This can be done in $\binom{2n}n$ ways.

• Finally, form a walk of length $2n$, where the $i^\text{th}$ step of the walk is the vector sum of the $i^\text{th}$ elements of the $s$ and $t$ sequences.

Answer 2

LHS is $$\sum_{k = 0}^{n}\frac{(2n)!}{n!n!} \cdot \frac{n!}{k! (n-k)!} \cdot \frac{n!}{k! (n - k)!} = \sum_{k = 0}^{n} \binom{2n}{n} \binom{n}{k}^2 = \binom{2n}{n} \sum_{k = 0}^{n}\binom{n}{k}^2$$

RHS is $$\binom{2n}{n}^2$$

So, we only need to prove $$\sum_{k = 0}^{n}\binom{n}{k}^2 = \binom{2n}{n}$$

Here is a combinatorial proof for Vandermonde's Identity

There is no need of multiplication either. We can just prove $$\sum_{k = 0}^{n}\binom{2n}{n} \binom{n}{k}^2 = \binom{2n}{n}^2$$

The RHS counts the ordered pair of paths from $(0, 0)$ to $(n, n)$. The paths may be identical.

Let's look at LHS.

First, we select the first path. $\binom{2n}{n}$ ways.

Now by iterating on $k$, we are counting the ordered pair of paths with $k$ right (or, analogous up) moves in the first $n$ moves. The other part then find the number of ways to pick $n - k$ positions for the right (or up) moves in the second half. The rest are up (or right) moves.

$$LHS = \sum_{k = 0}^{n} \binom{2n}{n} \binom{n}{k} \binom{n}{n - k} = \sum_{k = 0}^{n} \binom{2n}{n} \binom{n}{k}^2$$