- Thread starter
- Admin
- #1

- Feb 14, 2012

- 3,809

- Thread starter anemone
- Start date

- Thread starter
- Admin
- #1

- Feb 14, 2012

- 3,809

- Moderator
- #2

- Feb 7, 2012

- 2,740

- Thread starter
- Admin
- #3

- Feb 14, 2012

- 3,809

A method that is different than you and is also the proof by other:

$\displaystyle \sum_{k=0}^{n} \dfrac{(2n)!}{(k!(n-k)!)^2}={2n \choose n}^2$---(1)

Note that we have

$\displaystyle\dfrac{(2n)!}{(k!(n-k)!)^2}=\dfrac{(n)!}{(k!(n-k)!)^2}\cdot \dfrac{(2n)!}{(n!)^2}={n \choose k}^2\cdot{2n \choose n}$

Hence it suffices t show that

$\displaystyle \sum_{k=0}^{n} {n \choose k}^2={2n \choose n}$

We will do this combinatorially. Consider $2n$ balls, numbered from 1 up to $2n$. Balls 1 up to $n$ are colored green, and balls $n+1$ up to $2n$ are colored yellow. We can choose $n$ balls from these $2n$ balls in $\displaystyle {2n \choose n}$ ways.

On the other hand, we can also first choose $k$ green balls, with $0 \le k \le n$, and then choose $n-k$ yellow balls. Equivalently, we can chose $k$ green balls to include and $k$ yellow balls to not include. Hence the number of ways in which one can choose $n$ balls is also equal to $\displaystyle \sum_{k=0}^n {n \choose k}^2$.

Hence this sum is equal to ${2n \choose k}$. This proves (1) and we are done.