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$

Question

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<j\leq \lfloor \frac{n}{2} \rfloor$. 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.

Answer 1

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.