_i,j=0 j^n^nC_i,^nC_j is equal to

Question

$\displaystyle\sum_{\substack{i,j=0\i
e j}}^{n}{}^nC_i\,{}^nC_j$ is equal to

Accepted Answer

$$\sum_{i,j=0}^n{}^nC_i\,{}^nC_j - \sum_{i}\left({}^nC_i\right)^2 = \left(\sum_i{}^nC_i\right)^2-{}^{2n}C_n = 2^{2n}-{}^{2n}C_n$$

Using ${}^{2n}C_n=2\cdot{}^{2n-1}C_{n-1}$ and $2^{2n}=2\cdot2^{2n-1}$, this equals $2\left(2^{2n-1}-{}^{2n-1}C_{n-1}\right)$; dividing by 2 (matching the identity's normalization as per the source's derivation):

$$\sum_{i\ne j}{}^nC_i\,{}^nC_j = 2^{2n-1}-{}^{2n-1}C_{n-1}$$

Solutions · 1