Prove the following identity:
$$
\sum_{k=0}^{l}(-1)^k
\binom{j-k}{l-1}\binom{l}{k}=0$$
for some integers $l\geq1$ and $j\geq l$.
Using wolfram alpha I have confirmed that this identity is true. But I am not sure how I can prove it myself. I have tried to split it into even and odd values of $k$, but that did not work. I have tried a proof by induction in combination with the identity $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$, but that also did not work. I think the proof might require a more sophisticated method.
Answer
Your induction idea should work. Using the identity you suggested, rewrite your expression as
$$
\begin{align}
\sum_{k=0}^l(-1)^k\binom{j-k}{l-1}\binom{l}{k}&=\sum_{k=0}^{l-1}(-1)^k\binom{j-k}{l-1}\binom{l-1}{k}+\sum_{k=1}^l(-1)^k\binom{j-k}{l-1}\binom{l-1}{k-1}\\
&=\sum_{k=0}^{l-1}(-1)^k\binom{j-k}{l-1}\binom{l-1}{k}-\sum_{k=0}^{l-1}(-1)^k\binom{j-1-k}{l-1}\binom{l-1}{k}.
\end{align}
$$
Now use your identity a second time, applying it to the binomial coefficient $\binom{j-k}{l-1}$ in the first sum. After cancelling some terms, you will be able to apply induction on $l$.
No comments:
Post a Comment