CombinatorialIdentity Difficult

Problem - 4318

Show $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{m+k}{q}=(-1)^n\binom{m}{q-n}$$


Using Vandermonde's identity gives $$\binom{m+k}{q}=\sum_{k=0}^{q}\binom{k}{l}\binom{m}{q-l}$$

Therefore, $$\begin{align*} \sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{m+k}{q} =\ &\sum_{k=0}^{n}(-1)^k\binom{n}{k}\sum_{l=0}^{q}\binom{k}{l}\binom{m}{q-l} \\ =\ &\sum_{l=0}^{q}\binom{m}{q-l}\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{k}{l} \end{align*}$$

When $k < l$, $\binom{k}{l} = 0$. Thus, the above relation can be reduced to $$\sum_{l=0}^{q}\binom{m}{q-l}\sum_{k=l}^{n}(-1)^k\binom{n}{k}\binom{k}{l}$$

The conclusion of # 4302 states $$\sum_{k=l}^{n}(-1)^k\binom{n}{k}\binom{k}{l}=0$$

when $l < n$. Therefore, $$\sum_{l=0}^{q}\binom{m}{q-l}\sum_{k=l}^{n}(-1)^k\binom{n}{k}\binom{k}{l}=\sum_{l=n}^{n}\binom{m}{q-l}(-1)^n\binom{n}{n}\binom{n}{n} =(-1)^n\binom{m}{q-n}$$

report an error