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

I was solving a problem and am stuck with this expression. Any leads on how can I simplify this expression?

$$\frac{{\sum\limits_{x=Q}^{N-P+Q} (x-Q) \binom{x}{Q} \binom{N-x}{P-Q}}}{{\sum\limits_{x=Q}^{N-P+Q} \binom{x}{Q} \binom{N-x}{P-Q}}}$$

UPDATE: I realized a mistake. expression updated.

share|cite|improve this question
For the updated question, note that $(x-Q)\binom xQ=(Q+1)\binom x{Q+1}$, and you can let the sum start at $Q+1$ since the $x=Q$ term is zero. – joriki Jan 19 '13 at 13:43
@joriki Thanks, using that with vandermonde identity simplified the equation. – nims Jan 19 '13 at 19:35
Are you sure? I make it $$ (Q+1)\frac{\binom{N+1}{P+2}}{\binom{N+1}{P+1}}=\frac{(Q+1)(N-P)}{P+2}\;. $$ (This refers to a comment you'd made but now edited, in which you said the result was $(Q+1)/(P+2)$. – joriki Jan 19 '13 at 19:39
@joriki my bad, i was using that expression in another expression where $(N-P)$ was getting cancelled. :) – nims Jan 19 '13 at 19:42
up vote 6 down vote accepted

There is a variation of the Vandermonde identity that reads, for $k,m,n\in\mathbf N$: $$ \sum_{i=0}^k\binom im\binom{k-i}n=\binom{k+1}{m+n+1}. $$ Here is how you can remember it: let $0\leq a_0<\cdots<a_{m+n}\leq k$ be one of the $\binom{k+1}{m+n+1}$ subsets of $m+n+1$ numbers $a_j$ from the $k+1$-set $\{0,\ldots,k\}$, arranged increasingly. Put $i=a_m$, then there are $\binom im$ choices left for $a_0,\ldots,a_{m-1}$, and $\binom{k-i}n$ choices for $a_{m+1},\ldots,a_{m+n}$.

One can restrict the range of $i$ to the values $m\leq i\leq k-n$, as other terms contribute $0$.

So your expression simplfies to $$ \frac{{\sum\limits_{x=Q}^{N-P+Q} \binom{x-1}{Q} \binom{N-x}{P-Q}}}{{\sum\limits_{x=Q}^{N-P+Q} \binom{x}{Q} \binom{N-x}{P-Q}}}= \frac{\binom{N}{P+1}}{\binom{N+1}{P+1}}=\frac{N-P}{N+1}. $$

share|cite|improve this answer
Thanks for the reply. I realized i made a mistake. What to do if the numerator becomes $$\sum\limits_{x=Q}^{N-P+Q} (x-Q) \binom{x}{Q} \binom{N-x}{P-Q}$$ – nims Jan 19 '13 at 13:05
@nims: If you meant another question than the one you posed, please change (edit) the question (and indicate there that you did so). – Marc van Leeuwen Jan 19 '13 at 13:41
Thanks, turns out the new expression can be easily solved by little operation as suggested in the comments and then applying Vandermonde identity as you suggested. – nims Jan 19 '13 at 19:40

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.