Σ_(i,j = 0; i ≠ j)ⁿ ⁿCᵢ ⁿCⱼ is equal to

Solution

Maths sir · 3 steps

Do not chase the i ≠ j terms one by one: take the full square, then remove the diagonal.

1. Full double sum. With no restriction, i and j run independently from 0 to n. So the double sum splits into a product of two single sums, (Σᵢ ⁿCᵢ)(Σⱼ ⁿCⱼ) = 2ⁿ × 2ⁿ = 2²ⁿ.
2. Diagonal terms. The terms with i = j add up to Σᵢ₌₀ⁿ (ⁿCᵢ)². Writing (ⁿCᵢ)² = ⁿCᵢ ⁿCₙ₋ᵢ, this is the coefficient of xⁿ in (1+x)ⁿ(1+x)ⁿ = (1+x)²ⁿ, which is ²ⁿCₙ.

   Σ_(i,j=0 i ≠ j)ⁿ ⁿCᵢ ⁿCⱼ = Σ_(i,j=0)ⁿ ⁿCᵢ ⁿCⱼ - Σᵢ₌₀ⁿ(ⁿCᵢ)² = 2²ⁿ - ²ⁿCₙ

3. So. The sum is 2²ⁿ - ²ⁿCₙ, which is option (a).

The idea to keep. For a restricted double sum like i ≠ j or i < j, start from the unrestricted sum, which factorises, and subtract or halve. The diagonal sum of squares is always ²ⁿCₙ.

Answer from the NTA final answer key. Solution by PrepWiser.