Proof of  $\sum_{0 \le k \le t} {t-k \choose r}{k \choose s}={t+1 \choose r+s+1}$? 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.

Let $r$, $t$, $s$ be fixed.
$\binom{t+1}{r+s+1}$ = number of possibilities how can I choose $r+s+1$ elements from $\{1,2,\dots,t+1\}$
Let us order the chosen elements increasingly: $a_1 < a_2 < \dots < a_{r+s+1}$
What is the number of possibilities where $a_{s+1}=k+1$? We have to choose $s$ elements from $\{1,2,\dots,k\}$ and the remaining $r$ elements from $\{k+2,\dots,t+1\}$. We have
$$\binom ks \cdot \binom {t-k}r$$
possibilities. 
The last expression is non-zero only for $k\ge 0$ and $t-k\ge 0$, which gives us the range of summation.

Although you are probably not interested in a combinatorial proof, since you explicitly mentioned generating functions.
