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.

Prove that:

(I can't prove without binomial coefficient.)

$$ \big(m+n\big)!\over m!n!$$ is a natural number

you can use : formula for the largest power of a prime dividing a factorial $$ n!=p_1^\alpha* p_2^\beta* ... $$ $$ \alpha= \lfloor n/p \rfloor + \lfloor n/p^2 \rfloor+... $$

share|improve this question
    
Well, if you use that formula, this boils down to an elementary $\lfloor x+y \rfloor \ge \lfloor x \rfloor + \lfloor y \rfloor$. Did you try to prove that? –  Alexander Shamov Nov 29 '12 at 15:51

1 Answer 1

up vote 5 down vote accepted

Let $p$ be a prime. Write $\nu_p(k)$ for the exponent of $p$ in the prime decomposition of $k$. We have for $i \in \mathbb N$: $$ \frac{n+m}{p^i} = \frac n{p^i} + \frac{m}{p^i} $$ so, making the right hand side possibly smaller $$ \frac{n+m}{p^i} \ge \left\lfloor\frac n{p^i}\right\rfloor + \left\lfloor\frac m{p^i}\right\rfloor $$ Now the right hand side is an integer, hence by definition of the floor function $$ \left\lfloor \frac{n+m}{p^i}\right\rfloor \ge \left\lfloor\frac n{p^i}\right\rfloor + \left\lfloor\frac m{p^i}\right\rfloor $$ This gives \begin{align*} \nu_p(n!m!) &= \nu_p(n!) + \nu_p(m!)\\ &= \sum_{i=1}^\infty \left\lfloor \frac{n}{p^i} \right\rfloor + \sum_{i=1}^\infty \left\lfloor\frac m{p^i}\right\rfloor\\ &\le \sum_{i=1}^\infty \left\lfloor \frac{n+m}{p^i}\right\rfloor \\ &= \nu_p\bigl((n+m)!\bigr) \end{align*} And therefore $$ n!m! = \prod_p p^{\nu_p(n!m!)} \biggm| \prod_p p^{\nu_p((n+m)!)} = (n+m)! $$ that is the denominator divides the numerator in $\frac{(n+m)!}{n!m!}$ and so the quotient is an integer.

share|improve this answer
    
form very last equation $n!m! = (n+m)!$ ? –  nikita2 Nov 29 '12 at 15:53
1  
Note the $|$ ... it is to be read as "divides", as in $2\mid 4$... –  martini Nov 29 '12 at 15:53

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.