Donna Flynn

2022-07-17

Discrete math combinatorial proof
Prove that for every positive integer n,
$\sum _{k=0}^{n}{\left(\genfrac{}{}{0}{}{n}{k}\right)}^{2}=\sum _{l=0}^{n}\sum _{r=0}^{\frac{n-l}{2}}\left(\genfrac{}{}{0}{}{n}{l}\right)\left(\genfrac{}{}{0}{}{n-l}{r}\right)\left(\genfrac{}{}{0}{}{n-l-r}{r}\right)$
I know that $\sum _{k=0}^{n}{\left(\genfrac{}{}{0}{}{n}{k}\right)}^{2}=\left(\genfrac{}{}{0}{}{2n}{n}\right)$ but I can't seem to find a way to connect it to the right side.

Tamoni5e

Expert

Step 1
The lefthand side is the number of pairs ⟨A,B⟩ such that A and B are subsets of $\left[n\right]=\left\{1,\dots ,n\right\}$, and $|A|=|B|$.
Step 2
You can classify these pairs according to the number of elements that they have in common. Suppose that $C=A\cap B$; then A∖C and B∖C must be disjoint subsets of [n]. Think of setting $\ell =|C|$ and $r=|A\setminus C|=|A\setminus B|$.

Do you have a similar question?