Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

1 Answer

up vote 4 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|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
1  
@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
add comment

Your Answer

 
discard

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.