Show that \sum_{k=0}^{n}\binom{n}{k}^2=\frac{n+1}{n}\sum_{k=1}^{n}\binom{n}{k}\binom{n}{k-1}
I came across this result
while trying to solve this:
inductive proof for \binom{2n}{n}
My proof is cumbersome,
so I hope that
someone can come up
with a more elegant proof.
Note:
I know that
\sum_{k=0}^{n}\binom{n}{k}^2 =\binom{2n}{n} .
Answer
The fact that \sum_{k=0}^\infty {n \choose k}^2 = {2n \choose n}
has a combinatorial interpretation: to select n items from 2n, first take an arbitrary subset of the first n items, and if this had cardinality k select n-k of the second n items.
Similarly,
{2n \choose n} = \sum_{k=1}^{n} {n+1 \choose k} {n-1 \choose n-k}
and
{n+1 \choose k} {n-1 \choose n-k} = \frac{n+1}{n} {n \choose k}{n \choose k-1}
No comments:
Post a Comment