Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $k, \ell \leq n$ be non-negative integers. Does the following identity simplify? \begin{align} \sum_{j = 0}^{k} \binom{k}{j} \binom{j + n -\ell + 1}{n} = \binom{n - \ell + 1}{n} \phantom1_{2}\mathsf{F}_{1}(-k,n - \ell + 2, 2- \ell; -1) \end{align} where $\!\!\! \phantom1_{2}\mathsf{F}_{1}$ is a hypergeometric function. That is, does the right side have another representation in terms of simple functions given that $k,\ell$ and $n$ are non-negative integers?

share|cite|improve this question
$\binom{n-l+1}{n}=0$ if $l > 1$ I guess – GEdgar Apr 17 '12 at 19:27
Superficially it appears that the right side vanishes, but you must also consider the hypergeometric function. The sum is equal to $2^{k-1} k$ if $l = 2$ and $n = 1$. – user02138 Apr 17 '12 at 19:46
What do you consider to be a "simple function"? The theory behind Gosper's algorithm will tell you that if the sum exists as a hypergeometric then it's a rational polynomial times the summand. – Peter Taylor Apr 17 '12 at 20:44
Following @GEdgar's comment: how do you define $\binom{a}{b}$ when $a < b$ -- not as $0$? – Clement C. Jul 18 at 17:20

Let us denote: \begin{equation} S_k^{n,l} := \sum\limits_{j=0}^k \left( \begin{array}{c} k \\ j \end{array} \right) \left( \begin{array}{c} n-l+1+j \\ n \end{array} \right) \end{equation} Then we have: \begin{eqnarray} S_k^{n,l} &:=& \left. \frac{d^n}{n! d x^n} x^{n-l+1} \cdot \left(1+x\right)^k \right|_{x=1} \\ &=& \frac{1}{n!} \sum\limits_{p=0}^n \left(\begin{array}{c} n \\ p \end{array} \right) (n-l+1)_{(p)} k_{(n-p)} 2^{k-n+p} \\ &=&2^{k-n} \left( \begin{array}{c} k \\ n \end{array} \right) {}_2F_1\left[4-n,-n,1+k-n;2\right] \end{eqnarray}

The last result, that in terms of the hypergeometric function is not particularily useful when $n$, $l$, $k$ are integers. However the result above is useful for example if $k$ is large.

share|cite|improve this answer
+1, if only for the two concluding remarks. – Did Aug 20 '14 at 11:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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