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}$ 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?
 A: 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.
A: $$
\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
