what is the summation of this finite sequence? $$\sum\limits_{t = 0}^{n - m} {\left( {\begin{array}{*{20}{c}}
{t + k}\\
t
\end{array}} \right)} \left( {\begin{array}{*{20}{c}}
{n - k - t}\\
{n - m - t}
\end{array}} \right)$$
$k$, $n$, $m$ are constants, and $k <= m <= n$. any closed form solution?
It is a problem from my textbook. It's so weird. I've thought about it for the whole night and still can't find the answer:( 
 A: The key is to recognize the given expression as the convolution of two simpler series. Using the known generating function
$$
\sum_{j=0}^\infty \binom{j+q}j x^j = (1-x)^{-q-1},
$$
we see that
\begin{align*}
\sum_{j=0}^\infty x^j \sum_{t=0}^j \binom{t+k}t \binom{j-t-(k-m)}{j-t} &= \sum_{j=0}^\infty \sum_{t=0}^j \binom{t+k}t x^t \binom{j-t-(k-m)}{j-t} x^{j-t} \\
&= \sum_{t=0}^\infty \binom{t+k}t x^t \sum_{j=t}^\infty \binom{j-t-(k-m)}{j-t} x^{j-t} \\
&= \sum_{t=0}^\infty \binom{t+k}t x^t \sum_{i=0}^\infty \binom{i-(k-m)}i x^i \\
&= (1-x)^{-k-1} (1-x)^{k-m-1} = (1-x)^{-m-2}.
\end{align*}
Since $(1-x)^{-m-2} = \sum_{j=0}^\infty \binom{j+m+1}j x^j$, we have derived the identity
$$
\sum_{j=0}^\infty x^j \sum_{t=0}^j \binom{t+k}t \binom{j-t-(k-m)}{j-t} = \sum_{j=0}^\infty \binom{j+m+1}j x^j;
$$
Taking the coefficients of $x^{n-m}$ on both sides gives
$$
\sum_{t=0}^{n-m} \binom{t+k}t \binom{n-t-k}{n-m-t} = \binom{n+1}{n-m} = \binom{n+1}{m+1}.
$$
A: This is an interesting question.
Using upper negation, applying the Vandermonde identity, using upper negation again  and applying symmetry gives the following:
$$\begin{align}
\sum_{t=0}^{n-m}{\color{red}t+k\choose \color{red}t}{n-k-\color{red}t\choose n-m-\color{red}t}&=\sum_{t=0}^{n-m}{-k-1\choose \color{red}t}{k-m-1\choose n-m-\color{red}t}(-1)^{t+(n-m-t)}\\
&=(-1)^{n-m}{-m-2\choose n-m}\\
&=(-1)^{(n-m)+(n-m)}{n+2-1\choose n-m}\\
&={n+1\choose {n-m}}\\
&={n+1\choose {m+1}}\qquad \blacksquare
\end{align}$$
More information about upper negation and the Vandermonde identity here:
https://proofwiki.org/wiki/Negated_Upper_Index_of_Binomial_Coefficient
http://en.wikipedia.org/wiki/Vandermonde%27s_identity
A: There is a fairly easy combinatorial proof. We count the number of subsets of $\{0,1,\ldots,n\}$ of size $m+1$ in two ways. First, of course, there are $\binom{n+1}{m+1}$ of them. Now suppose that $S=\{a_0,\ldots,a_m\}$ is such a subset, where $a_0<\ldots<a_m$. Clearly $a_k\ge k$; let $t=a_k-k\ge 0$. Moreover, 
$$n\ge m\ge a_k+(m-k)=m+t\;,$$
so $t\le n-m$. For a given $t\in\{0,\ldots,n-m\}$ there are 
$$\binom{a_k}k=\binom{t+k}k=\binom{t+k}t$$
ways to choose the $k$ members of $S$ below $a_k=t+k$ and 
$$\binom{n-(t+k)}{m-k}=\binom{n-k-t}{n-m-t}$$
ways to choose the $m-k$ members of $S$ above $a_k=t+k$. Thus, there are
$$\binom{t+k}t\binom{n-k-t}{n-m-t}$$
ways to choose $S$ with $a_k=t+k$ and altogether
$$\sum_{t=0}^{n-m}\binom{t+k}t\binom{n-k-t}{n-m-t}$$
ways to choose $S$. It follows that
$$\sum_{t=0}^{n-m}\binom{t+k}t\binom{n-k-t}{n-m-t}=\binom{n+1}{m+1}\;.$$
A: By  way of  enrichment here  is  another algebraic  proof using  basic
complex variables.

We seek to compute
$$\sum_{t=0}^{n-m} {t+k\choose t} {n-k-t\choose n-m-t}.$$
Introduce the integral representation
$${n-k-t\choose n-m-t}
= \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n-k-t}}{z^{n-m-t+1}} \; dz.$$
We use this to obtain an  integral for the sum. Note that when $t>n-m$
we  have $1>n-m-t+1$  which means  that the  integral is  zero (entire
function). Therefore we may extend the sum to infinity, getting
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{(1+z)^{n-k}}{z^{n-m+1}} 
\sum_{t\ge 0} {t+k\choose t} \frac{z^t}{(1+z)^t}\; dz.$$
This simplifies to
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{(1+z)^{n-k}}{z^{n-m+1}} 
\frac{1}{(1-z/(1+z))^{k+1}} \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{(1+z)^{n-k}}{z^{n-m+1}} 
\frac{(1+z)^{k+1}}{(1+z-z)^{k+1}} \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{(1+z)^{n+1}}{z^{n-m+1}} \; dz.$$
This integral evaluates by inspection to
$${n+1\choose n-m} = {n+1 \choose m+1}.$$

Apparently this method is due to Egorychev.
