Friday, September 6, 2019

summation - Show that sumnk=0binomnk2=fracn+1nsumnk=1binomnkbinomnk1



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

analysis - Injection, making bijection

I have injection f \colon A \rightarrow B and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...