3
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Mathematica gives it as ${s\choose n}F(-n,-r,1-n+s,c)$ where $F$ is the 2F1 hypergeometric function. $\endgroup$ – almagest May 20 '16 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 Yuan May 21 '16 at 3:44
1
$\begingroup$

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*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.