Evaluate the sum $\sum_{0\leq j < k\leq n}\binom{n}{j}\binom{n}{k}$

Question

Could someone give me a hint on how to do this? I believe I know what the answer to be (I computed some low values and checked on OEIS). However, I was hoping someone would be able to explain to me how to approach a question like this.

Answer 1

Your sum looks like the cross product terms of $$\left[\binom n0+\binom n1+\cdots+\binom nn\right]^2.$$ Since $$2^n=\binom n0+\binom n1+\cdots+\binom nn,$$ squaring both sides gives us $$2^{2n}=\binom n0^2+\binom n1^2+\cdots+\binom nn^2+2\sum_{j\lt k}\binom nj\binom nk.$$ Since $$\binom n0^2+\binom n1^2+\cdots+\binom nn^2=\binom n0\binom nn+\binom n1\binom n{n-1}+\cdots+\binom nn\binom n0=\binom{2n}n$$ (Vandermonde's identity), the previous equation simplifies to $$2^{2n}=\binom{2n}n+2\sum_{j\lt k}\binom nj\binom nk$$ which we can solve to get your answer: $$\sum_{j\lt k}\binom nj\binom nk=\frac{2^{2n}-\binom{2n}n}2.$$

Answer 2

I suppose you meant : $\sum\sum_{0\le j<k\le n}\binom{n}{j}\binom{n}{k}$

$A=\sum_{j\le n}\sum_{k\le n}\binom{n}{j}\binom{n}{k} $

$B=\sum\binom{n}{i}^2$

You want $\dfrac{A-B}{2}$

$B=\binom{2n}{n}$ as it is coefficient of $x^n$ in $(1+x)^{n}\times(1+x)^n$

$A=\sum2^n\binom{n}{k}=2^{2n}$