Rewriting $\sum_{{i,j=0}\:\:i\ne j}^n \binom{n}{i}\:\:\binom{n}{j}$ [duplicate]

Question

Solve $$\sum_{{i,j=0}\:\:i\ne j}^n \binom{n}{i}\:\:\binom{n}{j}$$ This was a contest math problem which I was not able to solve.

My work: I was very unsure about how to approach this question. In my opinion, there will be many combinations and I tried listing them but wasn't able to find a general pattetn.

The options given were:

$2^{2n}-\binom{2n}{n}$

$2^{2n-1}-\binom{2n-1}{n-1}$

$2^{2n}-\frac12\binom{2n}{n}$

$2^{n-1}-\binom{2n-1}{n}$

The answer given by me was $2^{2n}-\binom{2n}{n}$ Any help will be appreciated.

Answer 1

$$ \sum_{{i,j=0};\:i\ne j}^n \binom{n}{i}\:\:\binom{n}{j}= $$ $$ \sum_{{i,j=0}}^n \binom{n}{i}\binom{n}{j}- \sum_{{i,j=0};\:i=j}^n \binom{n}{i}\binom{n}{j}\stackrel{\ast}{=} $$ $$ \sum_{i=0}^n \binom{n}{i}\cdot \sum_{j=0}^n \binom{n}{j}- \sum_{i=0}^n \binom{n}{i}\binom{n}{i} $$

In step $\ast$ "disentangle" the double sum of a product where the factors depend only on one of the summation variables using distributivity several times (marked by $\ast\ast$):

$$ \sum_{{i,j=0}}^n \binom{n}{i}\binom{n}{j}= $$ $$ \sum_{j=0}^n \left(\sum_{i=0}^n \left(\binom{n}{i}\binom{n}{j}\right)\right)\stackrel{\ast\ast}{=} $$ $$ \sum_{j=0}^n \left(\left(\sum_{i=0}^n \binom{n}{i}\right)\binom{n}{j}\right)\stackrel{\ast\ast}{=} $$ $$ \left(\sum_{i=0}^n \binom{n}{i}\right)\left(\sum_{j=0}^n \binom{n}{j}\right)= $$ $$ \sum_{i=0}^n \binom{n}{i}\cdot \sum_{j=0}^n \binom{n}{j} $$

Then use some standard identities on sums of binomial coefficients in step $\ast\!\ast\!\ast$ to get: $$ \sum_{i=0}^n \binom{n}{i}\cdot \sum_{j=0}^n \binom{n}{j}- \sum_{i=0}^n \binom{n}{i}\binom{n}{i}= $$ $$ \left(\sum_{i=0}^n \binom{n}{i}\right)^2- \sum_{i=0}^n \left(\binom{n}{i}^2\right)\stackrel{\ast\ast\ast}{=} $$ $$ \left(2^n\right)^2- \binom{2n}{n}= 2^{2n}- \binom{2n}{n} $$

Answer 2

Examine the function $f(x)$

$$f(x) = \sum_{i=0}^n\sum_{j=0}^n{n \choose i}{n \choose j}x^ix^j$$

where the summation we want is given by

$$S = f(1) - \sum_{i=0}^n{n \choose i}^2$$

Computing each iterated sum, we get

$$f(x) = \sum_{i=0}^n{n \choose i}x^i(1+x)^n = (1+x)^{2n}$$

and

$$\sum_{i=0}^n{n \choose i}^2 = {2n \choose n}$$

by the Vandermonde identity, or combinatorial argument. This means what we are after is

$$S = 2^{2n} - {2n \choose n}$$