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: 
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.
Suppose we seek to verify that
$$\sum\_{0\le k\le t} {t-k\choose r} {k\choose s}
= {t+1\choose r+s+1}.$$

Introduce
$${t-k\choose r} = {t-k\choose t-k-r} =
\frac{1}{2\pi i} 
\int\_{|z|=\epsilon} 
\frac{1}{z^{t-k-r+1}} (1+z)^{t-k} \; dz.$$

This controls the range so we may extend $k$ to infinity,
getting for the sum

$$\frac{1}{2\pi i} 
\int\_{|z|=\epsilon} 
\frac{1}{z^{t-r+1}} (1+z)^{t} 
\sum\_{k\ge 0} {k\choose s} \frac{z^k}{(1+z)^k} \; dz
\\ = \frac{1}{2\pi i} 
\int\_{|z|=\epsilon} 
\frac{1}{z^{t-r+1}} (1+z)^{t} 
\sum\_{k\ge s} {k\choose s} \frac{z^k}{(1+z)^k} \; dz
\\ = \frac{1}{2\pi i} 
\int\_{|z|=\epsilon} 
\frac{1}{z^{t-r+1}} (1+z)^{t} \frac{z^s}{(1+z)^s}
\sum\_{k\ge 0} {k+s\choose s} \frac{z^k}{(1+z)^k} \; dz
\\ = \frac{1}{2\pi i} 
\int\_{|z|=\epsilon} 
\frac{1}{z^{t-r+1}} (1+z)^{t} \frac{z^s}{(1+z)^s}
\frac{1}{(1-z/(1+z))^{s+1}} \; dz
\\ = \frac{1}{2\pi i} 
\int\_{|z|=\epsilon} 
\frac{1}{z^{t-r-s+1}} (1+z)^{t+1} 
\frac{1}{(1+z-z)^{s+1}} \; dz
\\ = \frac{1}{2\pi i} 
\int\_{|z|=\epsilon} 
\frac{1}{z^{t-r-s+1}} (1+z)^{t+1} 
\; dz.$$

This evaluates to
$${t+1\choose t-r-s} = {t+1\choose r+s+1}$$
by inspection.