prove the identity $\sum_{k=0}^n {s+k \choose k}{n-k \choose m} = {s+n+1 \choose s+m+1} $

Question

I am not able to understand how to apply the vandemonde identity to prove this. Please help me proving this.

Answer 1

Some progress:

This sum will vanish if $m>n$. $$S=\sum_{k=0}^{n} {s+k\choose k} {n-k \choose m}$$ $$S=[x^m]\sum_{k=0}^{n} {s+k\choose k} (1+x)^{n-k}$$ next use the Binomial series with negative index as $$\sum_{k=0}^{n} {s+k \choose k} z^k=(1-z)^{-s-1}-z^{n+1} {n+s+1 \choose n+1} ~_2F_1[n+s+2,1;2+n;z]~~~~~(2)$$ Then, $$S=[x^m] (1+x)^nx^{-s-1}(1+x)^{s+1}\implies S=[x^{m+s+1}] (1+x)^{n+s+1}$$ $$\implies S={n+s+1 \choose m+s+1}.$$ Here $[x^j] f(x)$ means coefficient of $x^{j}$ in $f(x).$

Note: One is welcome to point out why second term in (2) would not matter.

Answer 2

$$\sum_{k=0}^{n}\binom{s+k}{k}\binom{n-k}{m}$$

Use the fact that $\binom{n}{k}=\binom{n}{n-k}$ $$\sum_{k=0}^{n}\binom{s+k}{k}\binom{n-k}{n-k-m}$$

Use $\binom{n}{k}=(-1)^k\binom{k-n-1}{k}$

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

Now apply Vandermonde's identity

$$(-1)^{n-m}\binom{-s-m-2}{n-m}$$$$\binom{n+s+1}{n-m}=\binom{n+s+1}{m+s+1}$$