Question: How do I prove that

$$\sum\_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1} \>?$$

I saw this in a book discussing generating functions.

Answer: 
This approach is based on generating function.

By <http://math.arizona.edu/~faris/combinatoricsweb/generate.pdf>

We know that $\sum \limits\_{n=0}^{\infty} {n \choose k} y^n= \frac{y^k}{(1-y)^{k+1}} $

$x \cdot \sum \limits\_{l=0}^{\infty} {l \choose r} x^l \cdot \sum \limits\_{k=0}^{\infty} {k \choose s} x^k = x \cdot \frac{x^r}{(1-x)^{r+1}} \cdot \frac{x^s}{(1-x)^{s+1}}
=\frac{x^{r+s+1}}{(1-x)^{r+s+2}} = \sum \limits\_{n=0} {n \choose r+s+1} x^n$

The coefficient of $x^{t+1}$ of the
$x \cdot \sum \limits\_{l=0}^{\infty} {l \choose r} x^l \cdot \sum \limits\_{k=0}^{\infty} {k \choose s} x^k $ is $\sum \limits\_{l+k=t} {l \choose r}{k \choose s}$

Let $n=t+1$, 
${t+1 \choose r+s+1} = \sum \limits\_{l+k=t} {l \choose r}{k \choose s} = \sum \limits\_{0 \le k \le t} {t-k \choose r}{k \choose s}$
Look <http://fatosmatematicos.blogspot.com/2011/06/algumas-demonstracoes-da-convolucao-de.html>