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: 
I'm going to make more explicit the point I think Phira is making. The identity really is just Vandermonde's convolution plus the upper negation rule for binomial coefficients. 

The upper negation rule for binomial coefficients is $$\binom{n}{k} = (-1)^k \binom{k-n-1}{k},$$ which holds when $k$ is an integer (see, for example, *Concrete Mathematics*, 2nd edition, p. 164).
Applying this, we get
$$\sum\_{0 \le k \le t} {t-k \choose r}{k \choose s} = \sum\_{0 \le k \le t} {t-k \choose t-k-r}{k \choose k-s}= \sum\_{0 \le k \le t} (-1)^{t-k-r}{-r-1 \choose t-r-k} (-1)^{k-s}{-s-1 \choose k-s}$$
$$ = (-1)^{t-r-s}\sum\_{0 \le k \le t}{-r-1 \choose t-r-k}{-s-1 \choose -s+k}.$$
Now, use Vandermonde's convolution (or, more generally, the [Chu-Vandermonde identity](http://en.wikipedia.org/wiki/Vandermonde%27s_identity#Chu.E2.80.93Vandermonde_identity)),
to get 
$$ = (-1)^{t-r-s}{-r-s-2 \choose t-r-s},$$
and then apply the upper negation rule again, which gives us what we want:
$$={t+1 \choose t-r-s} = {t+1 \choose r+s+1}.$$
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.