Animated Solution for Mathematics - Binomial Theorem: ${\sum }_{\begin{array}{c}i,j=0\\ i\ne j\end{array}}^n{}^n{C}_i{}^n{C}_j$ is equal to

Imagine a square grid where the indices $i$ and $j$ both range from $0$ to $n$. Each cell contains the product of two binomial coefficients, ${}^n{C}_i\times {}^n{C}_j$.

Our objective is to calculate the sum of all values in this grid, subject to the constraint that we must exclude the diagonal where $i=j$.

Seeing the Whole

To find the sum of the entire grid, we first ignore the constraint. The total sum $S$ is defined by the double summation:

Because the terms ${}^n{C}_i$ and ${}^n{C}_j$ are independent, we can factor the summation into the product of two independent sums:

By the binomial theorem, we know that the sum of binomial coefficients ${\sum }_{k=0}^n{}^n{C}_k$ is equal to $2^n$. Therefore, the total sum of the grid is:

The constraint requires us to exclude the diagonal terms where $i=j$. The sum of these diagonal elements is given by:

This expression represents the sum of the squares of the binomial coefficients. According to the well-known combinatorial identity, this sum is equivalent to choosing $n$ items from a set of $2n$ items:

To obtain the sum of the off-diagonal elements, we subtract the diagonal sum from the total sum of the grid.

The final expression for the required sum is:

By visualizing the grid and decomposing the problem into the total sum and the diagonal sum, we have transformed a complex summation into a clear, elegant result. Always look for symmetry and total-sum properties when approaching such problems.