Prove $\sum_{k=j}^{n}{k \choose j}{n \choose k}{n-j \choose k+j}={2j \choose j}{2(n-j)\choose n-j}{n-j \choose 2j}{n+j \choose j}^{-1}$

Question

Apparently this sum has this closed form. $$\sum_{k=j}^{n}{k \choose j}{n \choose k}{n-j \choose k+j}={2j \choose j}{2(n-j)\choose n-j}{n-j \choose 2j}{n+j \choose j}^{-1}$$

How to show that this closed form is correct?

Answer 1

For any polynomial/formal power series in one or two indeterminants $x,y$. $$ A(x) = \sum_{a \in \mathbb{Z}} \alpha_a x^a \quad\text{ and }\quad B(x) = \sum_{a,b\in \mathbb{Z}} \beta_{ab}x^ay^b$$ Let $[x^a]A(x)$ and $[x^ay^b]B(x,y)$ be a short hand for the coefficients $\alpha_a$ and $\beta_{ab}$.

For this particular problem, let

$$\begin{align} A(x) &= (1+x)^{n-j}\\ &= \sum_{\ell=0}^{n-j} \binom{n-j}{\ell} x^{n-j-\ell} = \sum_{k=-j}^{n-2j} \binom{n-j}{k+j} x^{(n-2j)-k}\\ B(x,y) &= (1+x+xy)^n = (1+x(1+y))^n\\ &= \sum_{k=0}^n\binom{n}{k}x^k(1+y)^k = \sum_{k=0}^n\sum_{\ell=0}^k \binom{n}{k}x^k y^\ell\end{align} $$ We have

$$\begin{align} {\rm LHS} =& \sum_{k=j}^n \binom{k}{j}\binom{n}{k}\binom{n-j}{k+j}\\ = & \sum_{k=j}^n \left([x^ky^j]B(x,y)\right)\left([x^{(n-2j)-k}] A(x)\right)\\ = & [x^{n-2j} y^j] A(x)B(x,y)\\ = &[x^{n-2j} y^j] (1+x)^{n-j}((1+x)+xy)^n\\ = &[x^{n-2j} y^j] \sum_{\ell=0}^n \binom{n}{\ell} (xy)^\ell (1+x)^{2n-j-\ell}\\ = &[x^{n-2j}] \binom{n}{j} x^j(1+x)^{2n-2j} = [x^{n-3j}] \binom{n}{j} (1+x)^{2n-2j}\\ = & \binom{n}{j}\binom{2n-2j}{n-3j} \end{align} $$ Expanding RHS, we get

$$\begin{align}{\rm RHS} = & \binom{2j}{j}\binom{2n-2j}{n-j}\binom{n-j}{2j}\binom{n+j}{j}^{-1}\\ = & \frac{\color{red}{(2j)!}}{j!\color{green}{j!}}\frac{(2n-2j)!}{(n-j)!\color{blue}{(n-j)!}}\frac{\color{blue}{(n-j)!}}{\color{red}{(2j)!}(n-3j)!}\frac{n!\color{green}{j!}}{(n+j)!}\\ = & \frac{n!}{j!(n-j)!}\frac{(2n-2j)!}{(n+j)!(n-3j)!}\\ = & \binom{n}{j}\binom{2n-2j}{n-3j} \end{align} $$ This is the same expression for LHS we derived above. As a result, ${\rm LHS} = {\rm RHS}$ and we are done.

Answer 2

$$ \begin{align} \sum_{k=j}^n\color{#C00}{\binom{k}{j}\binom{n}{k}}\color{#090}{\binom{n-j}{k+j}} &=\sum_{k=j}^n\color{#C00}{\binom{n}{j}\binom{n-j}{k-j}}\color{#090}{\binom{n-j}{n-k-2j}}\tag1\\ &=\binom{n}{j}\binom{2n-2j}{n-3j}\tag2 \end{align} $$ Explanation:
$(1)$: $\binom{k}{j}\binom{n}{k}=\binom{n}{j}\binom{n-j}{k-j}$ by expanding Binomial Coefficients into factorials
$\phantom{(1)\text{:}}$ $\binom{n-j}{k+j}=\binom{n-j}{n-k-2j}$ by symmetry of Pascal's Triangle
$(2)$: Vandermonde's Identity $$ \begin{align} \binom{2j}{j}\binom{2n-2j}{n-j}\binom{n-j}{2j}\binom{n+j}{j}^{-1} &=\frac{(2j)!}{j!\,j!}\frac{(2n-2j)!}{(n-j)!\,(n-j)!}\frac{(n-j)!}{(2j)!\,(n-3j)!}\frac{j!\,n!}{(n+j)!}\tag3\\ &=\frac{n!}{j!\,(n-j)!}\frac{(2n-2j)!}{(n-3j)!\,(n+j)!}\tag4\\ &=\binom{n}{j}\binom{2n-2j}{n-3j}\tag5 \end{align} $$ Explanation:
$(3)$: expand Binomial Coefficients into factorials
$(4)$: cancel factors
$(5)$: expand Binomial Coefficients into factorials