# Vandermonde-type convolution with geometric term

Is there a closed-form solution to the following sum? \begin{align*} f(r, s, n) = \sum_{k=0}^{n}c^k\binom{r}{k}\binom{s}{n-k} \end{align*} I know this corresponds to find the coefficient of $x^n$ of the generating function \begin{align*} (1+cx)^r(1+x)^s \end{align*} but I don't know how to proceed from here. Any inputs would be great!

• Mathematica gives it as ${s\choose n}F(-n,-r,1-n+s,c)$ where $F$ is the 2F1 hypergeometric function. – almagest May 20 '16 at 17:35
• I don't see much hope for anything simpler than what you wrote. If you want to know something more specific, e.g. asymptotics, it'll be possible to say more. – Qiaochu Yuan May 21 '16 at 3:44

## 1 Answer

Here is a possible expression not very elegant. $$\sum_{k=0}^{n}c^k\binom{r}{k}\binom{s}{n-k} = \sum_{j=n-s}^{r} \binom{r}{j} (1-c)^{r-j}c^j \binom{j+s}{n}.$$ The proof begins with your idea: \begin{align*} (1+cx)^r(1+x)^s &= ((1-c)+c(1+x))^r(1+x)^s \\ &= \sum_{j=0}^r\binom{r}{j} (1-c)^{r-j}c^j(1+x)^{j+s} \\ &= \sum_{j=0}^r\binom{r}{j} (1-c)^{r-j}c^j \sum_{i=0}^{j+s}\binom{j+s}{i} x^i \\ &= \sum_{n=0}^{s} x^n \sum_{j=0}^{r} \binom{r}{j} (1-c)^{r-j}c^j \binom{j+s}{n}\\ &\quad+\sum_{n=1}^{r} x^{n+s} \sum_{j=n}^{r} \binom{r}{j} (1-c)^{r-j}c^j \binom{j+s}{n+s}. \end{align*}