# 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?

• So, the last term of the sum is $\binom{n}{j}\binom{n}{n} \color{red}{\binom{n-j}{n+j}}$? How does that work? – Theo Bendit May 23 at 4:34
• It would provide interesting context to mention where this came from, book and/or course and/or other problem, what you tried, and any other information that might be relevant. – robjohn May 23 at 6:56

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.

\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