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.

  • $\begingroup$ Have you tried Zeilberger's algorithm? $\endgroup$ – Peter Taylor Jun 12 '18 at 14:36
  • $\begingroup$ @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? $\endgroup$ – Salomo Jun 12 '18 at 16:37
  • $\begingroup$ Your summation is over the entire support of $k$, which is what matters. $\endgroup$ – 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.


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.