# A combinatorial identity: $\sum_{k=0}^j (-1)^k \frac{n-2k}{n-j-k} \binom{n}{k} \binom{n-j-k}{j-k} = 0$

I would like to prove the following identity: For $$0< j\leq \left\lfloor{n \over 2}\right\rfloor$$, $$\sum_{k=0}^j (-1)^k \frac{n-2k}{n-j-k} \binom{n}{k} \binom{n-j-k}{j-k} = 0.$$ I have checked for several small $$j$$, but no clue on how to prove it for all $$0. I have thought about whether one can have a combinatorial proof, like using inclusion-exclusion, but it seems not possible becuase some terms would not be integers. Would be glad if there is any proof or hint. Thanks.

• Have you tried Zeilberger's algorithm? – Peter Taylor Jun 12 '18 at 14:36
• @PeterTaylor Thanks for the suggestion. First time hear this algorithm and have just googled it. It seems not fit our case as the summation is not over all $k$ but just $0\leq k \leq j$. Or could you explain more? – Salomo Jun 12 '18 at 16:37
• Your summation is over the entire support of $k$, which is what matters. – Peter Taylor Jun 12 '18 at 17:34

We have that for $0< j<n/2$, \begin{align} \sum_{k=0}^j (-1)^k \frac{n-2k}{n-j-k} \binom{n}{k} \binom{n-j-k}{j-k}&= \frac{1}{n-2j} \sum_{k=0}^j (-1)^k (n-2k) \binom{n}{k} \binom{n-j-k-1}{j-k}\\ &= \frac{n}{n-2j} \sum_{k=0}^j (-1)^k \binom{n}{k} \binom{n-j-k-1}{j-k} \\&\qquad-\frac{2n}{n-2j} \sum_{k=1}^j (-1)^k \binom{n-1}{k-1} \binom{n-j-k-1}{j-k}. \end{align} Hence it suffices to show that $$\sum_{k=0}^j (-1)^k \binom{n}{k} \binom{n-j-k-1}{j-k} =2\sum_{k=1}^j (-1)^k \binom{n-1}{k-1} \binom{n-j-k-1}{j-k}\tag{\star}.$$ Now use the fact that $$(-1)^k\binom{n-j-k-1}{j-k}=(-1)^j\binom{2j-n}{j-k}.$$ Then, by Vandermonde's identity, the LHS of $(\star)$ is $$\sum_{k=0}^j (-1)^k \binom{n}{k} \binom{n-j-k-1}{j-k}= (-1)^j\sum_{k=0}^j \binom{n}{k} \binom{2j-n}{j-k}=(-1)^j\binom{2j}{j}$$ and the RHS of $(\star)$ is $$2\sum_{k=1}^j (-1)^k \binom{n-1}{k-1} \binom{n-j-k-1}{j-k}= 2(-1)^j\sum_{k=1}^j \binom{n-1}{k-1} \binom{2j-n}{j-k} \\=2(-1)^j\binom{2j-1}{j-1}=(-1)^j\binom{2j}{j}$$ and we are done.