$\sum_{\substack{i, j=0 \\ i \neq j}}^{n}{ }^{n} C_{i}{ }^{n} C_{j}$ is equal to

(B) $2^{2n-1}-{ }^{2n-1} C_{n-1}$

(C) $2^{2n}-\frac{1}{2}{ }^{2n} C_{n}$

JEE Main · 2022 · 26 Jul 2022 · Shift 2 · Binomial Theorem

\sum_{i, j = 0 i \neq = j}^{n}^{n} C_{i}^{n} C_{j}

is equal to

Answer: (A)

Summing over all ordered pairs

(i, j)

and then removing the diagonal

i = j

\sum_{i \neq = j}^{n} C_{i}^{n} C_{j} = (\sum_{i = 0}^{n}^{n} C_{i}) (\sum_{j = 0}^{n}^{n} C_{j}) - \sum_{i = 0}^{n} (^{n} C_{i})^{2}

. Each binomial row sums to

2^{n}

, so the first part is

2^{n} \cdot 2^{n} = 2^{2 n}

, and by the Vandermonde identity

\sum_{i = 0}^{n} (^{n} C_{i})^{2} =^{2 n} C_{n}

. Hence the value of the double sum is

2^{2 n} -^{2 n} C_{n}

JEE Main · 2022 · 26 Jul 2022 · Shift 2 · Single correct option