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.
 A: 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.
A: 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),
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}.$$
A: 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}$
A: Look http://fatosmatematicos.blogspot.com/2011/06/algumas-demonstracoes-da-convolucao-de.html
A: Note that this summation is Vandermonde's identity.
Calculate in both sums the ratio of consecutive summands and compare them. You will see that after a suitable change of variables they are the same. 
Therefore, the two sums only differ by a global factor in each term and the result.
If you want to know more about this, read about hypergeometric functions.
A: 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.
