How would you prove the following identity
$$\sum_{1\ \leq\ j\ <\ j'\ \leq\ n}\
\prod_{k\ \neq\ j,\,j'}^{n}
{\left(\, j + j'\,\right)^{2} \over \left(\, j – k\,\right)\left(\, j' – k\,\right)} =C_{n – 2}
$$
where $C_{k}$ is the $k$-th Catalan number defined as
$$
C_k\equiv{\left(\, 2k\,\right)! \over k!\left(\, k + 1\,\right)!}$$
Best Answer
Start by encoding the sum call it $S_n$ using residues. We have by inspection that $$S_n = \frac{1}{2}\sum_{1\ \leq\ j,\ j'\ \leq\ n \atop j\ne j'}\ \prod_{k\ \neq\ j,\,j'}^{n} {\left(\, j + j'\,\right)^{2} \over \left(\, j - k\,\right)\left(\, j' - k\,\right)} = \frac{1}{2} \sum_{q=1}^n \mathrm{Res} \left(f(z); z=q\right)$$ where $$f(z) = \prod_{p=1}^n\frac{1}{z-p} \sum_{j=1}^n (z-j)\times \frac{(-1)^{n-1-j} (z-j)(z+j)^{2n-4}}{(j-1)!(n-j)!}.$$
This is because
$$\prod_{k\ne j, j'}^n \frac{(j+j')^2}{(j-k)(j'-k)} = (j+j')^{2n-4} \prod_{k\ne j, j'}^n \frac{1}{j-k} \prod_{k\ne j, j'}^n \frac{1}{j'-k}$$
and we get from the residue at $z=j'$ from $f(z)$ for $j\ne j'$ the contribution
$$(j'-j) \prod_{p\ne j'}^n \frac{1}{j'-p} \times (j'-j) (-1)^{n-1-j} \frac{1}{(j-1)! (n-j)!} \times (j+j')^{2n-4}$$
and we have
$$(j'-j) \prod_{p\ne j'}^n \frac{1}{j'-p} = \prod_{p\ne j,j'}^n \frac{1}{j'-p}$$
and
$$(j'-j) (-1)^{n-1-j} \frac{1}{(j-1)! (n-j)!} = \prod_{p\ne j,j'}^n \frac{1}{j-p}.$$
There is a zero contribution when $j=j'$ because the factor $(z-j)^2$ cancels the pole.
We can therefore collect $S_n$ by integrating $f(z)$ around a contour that encloses the $n$ poles. We will then use the residue at infinity to evaluate the sum of the residues inside the contour.
Simplify $f(z)$ to obtain $$f(z) = \frac{1}{(n-1)!} \prod_{p=1}^n\frac{1}{z-p} \sum_{j=1}^n {n-1\choose j-1} (-1)^{n-1-j} (z-j)^2(z+j)^{2n-4}$$ which is $$f(z) = \frac{1}{(n-1)!} \prod_{p=1}^n\frac{1}{z-p} \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-j} (z-j-1)^2(z+j+1)^{2n-4}.$$
Now the residue at infinity of $f(z)$ is given by $$\mathrm{Res} \left(-\frac{1}{z^2} f\left(\frac{1}{z}\right); z=0\right).$$ The functional term becomes $$-\frac{1}{z^2} \frac{1}{(n-1)!} \prod_{p=1}^n\frac{1}{1/z-p} \\ \times \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-j} (1/z-j-1)^2(1/z+j+1)^{2n-4}.$$
This is $$-\frac{1}{z^2} \frac{1}{(n-1)!} \prod_{p=1}^n\frac{z}{1-pz} \\ \times \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-j} \frac{(1-(j+1)z)^2}{z^2} \frac{(1+(j+1)z)^{2n-4}}{z^{2n-4}}$$ which becomes $$-\frac{z^n}{z^2\times z^2\times z^{2n-4}} \frac{1}{(n-1)!} \prod_{p=1}^n\frac{1}{1-pz} \\ \times \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-j} (1-(j+1)z)^2 (1+(j+1)z)^{2n-4}.$$
Drop the minus sign (residues sum to zero) to obtain $$S_n = \frac{1}{2} \mathrm{Res} \left(\frac{1}{z^n} \frac{1}{(n-1)!} \prod_{p=1}^n\frac{1}{1-pz} \\ \times \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-j} (1-(j+1)z)^2 (1+(j+1)z)^{2n-4}; z=0\right).$$
Using $$(1-(j+1)z)^2 = 1 - 2(j+1)z + (j+1)^2z^2$$ we get three pieces from this, call them $A_n, B_n$ and $C_n.$ We will evaluate these making use of the disappearance of terms from formal power series in residue calculations and the fact that Stirling numbers of the second kind vanish when partitioning into more subsets than there are elements.
We have $$A_n = \frac{1}{2} \mathrm{Res} \left(\frac{1}{z^n} \frac{1}{(n-1)!} \prod_{p=1}^n\frac{1}{1-pz} \\ \times \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-j} \sum_{q=0}^{2n-4} {2n-4\choose q} (j+1)^q z^q; z=0\right).$$
This becomes $$A_n = \frac{1}{2} \mathrm{Res} \left(\frac{1}{z^n} \frac{1}{(n-1)!} \prod_{p=1}^n\frac{1}{1-pz} \\ \times \sum_{q=0}^{2n-4} {2n-4\choose q} z^q \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-j} (j+1)^q; z=0\right)$$ which is $$A_n = - \frac{1}{2} \mathrm{Res} \left(\frac{1}{z^n} \prod_{p=1}^n\frac{1}{1-pz} \times \sum_{q=0}^{2n-4} {2n-4\choose q} {q+1\brace n} z^q; z=0\right).$$ which simplifies to (powers $z^q$ with $q\ge n$ do not contribute to the residue) $$A_n = - \frac{1}{2} \mathrm{Res} \left(\frac{1}{z^n} \prod_{p=1}^n\frac{1}{1-pz} \times \sum_{q=0}^{n-1} {2n-4\choose q} {q+1\brace n} z^q; z=0\right)$$ which is (the Stirling number vanishes when $q+1 < n$) $$A_n = - \frac{1}{2} \mathrm{Res} \left(\frac{1}{z^n} \prod_{p=1}^n\frac{1}{1-pz} \times {2n-4\choose n-1} {n\brace n}z^{n-1};z=0\right) = -\frac{1}{2} {2n-4\choose n-1}.$$
For $B_n$ we obtain $$B_n = \mathrm{Res} \left(\frac{1}{z^n} \prod_{p=1}^n\frac{1}{1-pz} \times \sum_{q=0}^{2n-4} {2n-4\choose q} {q+2\brace n} z^{q+1}; z=0\right)$$ which simplifies to $$B_n = \mathrm{Res} \left(\frac{1}{z^n} \prod_{p=1}^n\frac{1}{1-pz} \times \sum_{q=0}^{n-2} {2n-4\choose q} {q+2\brace n} z^{q+1}; z=0\right)$$ which is $$B_n = \mathrm{Res} \left(\frac{1}{z^n} \prod_{p=1}^n\frac{1}{1-pz} \times {2n-4\choose n-2} {n\brace n}z^{n-1};z=0\right) = {2n-4\choose n-2}.$$
For $C_n$ we obtain $$C_n = - \frac{1}{2} \mathrm{Res} \left(\frac{1}{z^n} \prod_{p=1}^n\frac{1}{1-pz} \times \sum_{q=0}^{2n-4} {2n-4\choose q} {q+3\brace n} z^{q+2}; z=0\right)$$ which simplifies to $$C_n = - \frac{1}{2} \mathrm{Res} \left(\frac{1}{z^n} \prod_{p=1}^n\frac{1}{1-pz} \times \sum_{q=0}^{n-3} {2n-4\choose q} {q+3\brace n} z^{q+2}; z=0\right)$$ which is $$C_n = - \frac{1}{2} \mathrm{Res} \left(\frac{1}{z^n} \prod_{p=1}^n\frac{1}{1-pz} \times {2n-4\choose n-3} {n\brace n}z^{n-1};z=0\right) = - \frac{1}{2} {2n-4\choose n-3}.$$
Finally collecting the contributions from $A_n, B_n$ and $C_n$ we obtain $$-\frac{1}{2} {2n-4\choose n-1} + {2n-4\choose n-2} - \frac{1}{2} {2n-4\choose n-3} \\ = \left(-\frac{1}{2} \frac{n-2}{n-1} + 1 - \frac{1}{2} \frac{n-2}{n-1} \right) {2n-4\choose n-2} = \frac{1}{n-1} {2n-4\choose n-2} = C_{n-2}.$$
Addendum. Here we have used the basic Stirling number identity $$\sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-j} (j+1)^q = - (n-1)! {q+1\brace n}.$$
To prove this consider the generating function $$- \sum_{q\ge 0} \frac{z^q}{q!} \frac{1}{(n-1)!} \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-j} (j+1)^q \\= \frac{1}{(n-1)!} \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-1-j} \sum_{q\ge 0} \frac{z^q}{q!} (j+1)^q \\= \frac{1}{(n-1)!} \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-1-j} \exp((j+1)z) \\= \frac{\exp(z)}{(n-1)!} \sum_{j=0}^{n-1} {n-1\choose j} (-1)^{n-1-j} \exp(jz) \\= \frac{\exp(z)}{(n-1)!} (\exp(z)-1)^{n-1}.$$
Now observe the exponential generating function $$\sum_{q\ge 0} {q+1\brace n} \frac{z^q}{q!} = \left(\sum_{q\ge 0} {q\brace n} \frac{z^q}{q!}\right)'$$ which is $$ \left(\frac{1}{n!} (\exp(z)-1)^n\right)' = \frac{1}{n!} \times n \times (\exp(z)-1)^{n-1} \exp(z) \\ = \frac{1}{(n-1)!} (\exp(z)-1)^{n-1} \exp(z).$$
The two generating functions are the same, fin. Here we have used the bivariate generating function $$G(z, u) = \exp(u(\exp(z)-1))$$ of the Stirling numbers of the second kind which follows from the combinatorial class specification
$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\textsc{SET}(\mathcal{U}\times\textsc{SET}_{\ge 1}(\mathcal{Z})).$$