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!
-
1$\begingroup$ Mathematica gives it as ${s\choose n}F(-n,-r,1-n+s,c)$ where $F$ is the 2F1 hypergeometric function. $\endgroup$– almagestMay 20, 2016 at 17:35
-
1$\begingroup$ 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. $\endgroup$– Qiaochu YuanMay 21, 2016 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*}