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?

  • $\begingroup$ 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? $\endgroup$ – Theo Bendit May 23 at 4:34
  • $\begingroup$ 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. $\endgroup$ – 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.