Combination sum . I want to evaluate the following sum :
$$S(k,k')=\sum_{i} C_{i+k}^k C_{k'-i}^{k}$$ = $$S(k,k')=\sum_{i} \binom{i+k}{k} \binom{k'-i}{k}$$

I tried some steps but couldnt get further than :
$S(k,k')=2*(\sum_{i}^{(k'-k)/2}C_{i+k}^k C_{k'-i}^{k})$
 A: We have
$$S(k,\ell)=\sum_i\binom{i+k}k\binom{\ell-i}k\;.$$
This can be evaluated as a special case of identity $(5.26)$ in Graham, Knuth, & Patashnik, Concrete Mathematics, which is given as
$$\sum_{0\le k\le\ell}\binom{\ell-k}m\binom{q+k}n=\binom{\ell+q+1}{m+n+1}$$
for integers $\ell,m\ge 0$ and integers $n\ge q\ge 0$. Thus
$$S(k,\ell)=\binom{k+\ell+1}{2k+1}\;.$$
Here’s a combinatorial proof.
Let $A=\{0,1,\ldots,k+\ell\}$. There are $\binom{k+\ell+1}{2k+1}$ ways to choose $2k+1$ elements of $A$. Once these have been chosen, we can split them into the $k$ smallest, the $k$ largest, and the one in the middle. Alternatively, we could pick these three parts separately. The middle element $m$ must satisfy the inequality $k\le m\le\ell$ in order to leave room for $k$ elements above and below it. Let $i=m-k$, so that $0\le i\le\ell-k$. Then there are $i+k$ members of $A$ below $m$, so there are $\binom{i+k}k$ ways to choose $k$ of them, and there are $(k+\ell)-(k+i)=\ell-i$ members of $A$ above $m$ and hence $\binom{\ell-i}k$ ways to choose $k$ of them. Thus, for a fixed $m$, and $i=m-k$, there are $\binom{i+k}k\binom{\ell-i}k$ ways to choose $2k+1$ members of $A$ so that $m$ is the middle element. Summing over $i$ then yields the result.
A: This yields to snake oil (see e.g. Wilf's "generatingfunctionology").
We want a special case of "Vandermonde on its head":
$$
\sum_k \binom{n - k}{r} \binom{m + k}{s}
$$
We will need the identity:
$$
\sum_k \binom{k}{n} z^k
  = \frac{z^n}{(1 - z)^{n + 1}}
$$
and negative binomial coefficients:
$$
\binom{-n}{k} 
  = (-1)^k \binom{n + k - 1}{n - 1}
$$
Choose $n$ as free variable, so our sum is $s_n$, and consider the generating function:
$\begin{align}
S(z) &= \sum_{n \ge 0} s_n z^n \\
     &= \sum_{n \ge 0} z^n \sum_k \binom{n - k}{r} \binom{m + k}{s} \\
     &= \sum_k \binom{m + k}{s} \sum_{n \ge 0} \binom{n - k}{r} z^n \\
     &= \sum_k \binom{m + k}{s} z^k \sum_{n \ge 0} \binom{n - k}{r} z^{n - k} \\
     &= \sum_k \binom{m + k}{s} z^k \sum_j \binom{j}{r} z^j \\
     &= \sum_k \binom{m + k}{s} \frac{z^k \cdot z^r}{(1 - z)^{r + 1}} \\
     &= \frac{z^{r - m}}{(1 - z)^{r + 1}} \sum_k \binom{m + k}{s} z^{m + k} \\
     &= \frac{z^{r - m}}{(1 - z)^{r + 1}} \cdot \frac{z^s}{(1 - z)^{s + 1}} \\
     &= \frac{z^{r + s - m}}{(1 - z)^{r + s + 2}}
\end{align}$
Now we want:
$\begin{align}
s_n
  &= [z^n] S(n) \\
  &= [z^n] \frac{z^{r + s - m}}{(1 - z)^{r + s + 2}} \\
  &= [z^{m + n - r - s}] \frac{1}{(1 - z)^{r + s + 2}} \\
  &= (-1)^{m + n - r - s} \binom{-r - s - 2}{n + m - r - s} \\
  &= \binom{r + s + 2 + m + n - r - s - 1}{r + s + 2 - 1} \\
  &= \binom{m + n + 1}{r + s + 1}
\end{align}$
