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 for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer.

I'm not familiar to factorial and I don't have much idea, can someone show me how to prove this? Thank you.

share|improve this question
    
Prove that the factorial ratio satisfies a two-term recurrence relation with integer coefficients and integer initial value. –  user02138 Oct 17 '12 at 3:26
1  
I wonder if there isn't some way to make this into a product of binomial coefficients. –  MJD Oct 17 '12 at 5:00
2  
This was a 1972 IMO problem –  Jeremy Oct 17 '12 at 5:40

1 Answer 1

up vote 4 down vote accepted

Consider a prime $p$. The highest power of $p$ dividing the numerator is $$\alpha_{Nr} = \left(\left \lfloor \dfrac{2m}{p}\right \rfloor + \left \lfloor \dfrac{2m}{p^2}\right \rfloor + \left \lfloor \dfrac{2m}{p^3}\right \rfloor + \cdots \right) + \left(\left \lfloor \dfrac{2n}{p}\right \rfloor + \left \lfloor \dfrac{2n}{p^2}\right \rfloor + \left \lfloor \dfrac{2n}{p^3}\right \rfloor + \cdots \right)$$

The highest power $p$ dividing the denominator is $$\alpha_{Dr} = \left(\left \lfloor \dfrac{m}{p}\right \rfloor + \left \lfloor \dfrac{m}{p^2}\right \rfloor + \left \lfloor \dfrac{m}{p^3}\right \rfloor + \cdots \right) + \left(\left \lfloor \dfrac{n}{p}\right \rfloor + \left \lfloor \dfrac{n}{p^2}\right \rfloor + \left \lfloor \dfrac{n}{p^3}\right \rfloor + \cdots \right) + \left(\left \lfloor \dfrac{m+n}{p}\right \rfloor + \left \lfloor \dfrac{m+n}{p^2}\right \rfloor + \left \lfloor \dfrac{m+n}{p^3}\right \rfloor + \cdots \right)$$

You may want to look at this post that discusses the highest power of a prime dividing $N!$.

The goal now is to show that $\alpha_{Nr} > \alpha_{Dr}$. If we prove that $$\lfloor 2x \rfloor + \lfloor 2y \rfloor \geq \lfloor x \rfloor + \lfloor y \rfloor + \lfloor x+y \rfloor$$ we are then done. Can you now prove this one?

We have $x = \lfloor x \rfloor + \{x \}$ and $y = \lfloor y \rfloor + \{y \}$.

We will consider 4 cases.

Case $1$: $\{x\} <1/2$, $\{y\} <1/2$. Then $\lfloor 2x \rfloor = 2 \lfloor x \rfloor$ and $\lfloor 2y \rfloor = 2 \lfloor y \rfloor$ and $\lfloor x + y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor$. Hence, we have $$\lfloor 2x \rfloor + \lfloor 2y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor + \lfloor x+y \rfloor$$

Case $2$: $\{x\} <1/2$, $\{y\} >1/2$ or $\{x\} >1/2$, $\{y\} <1/2$. Then $$\lfloor 2x \rfloor + \lfloor 2y \rfloor = 2 \lfloor x \rfloor + 2 \lfloor y \rfloor + 1$$ Further, $$\lfloor x+y \rfloor \leq \lfloor x \rfloor + \lfloor y \rfloor + 1$$ Hence, we have $$\lfloor 2x \rfloor + \lfloor 2y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor + \lfloor x+y \rfloor$$

Case $3$: $\{x\} >1/2$, $\{y\} >1/2$. Then $$\lfloor 2x \rfloor + \lfloor 2y \rfloor = 2 \lfloor x \rfloor + 2 \lfloor y \rfloor + 2$$ Further, $$\lfloor x+y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor + 1$$ Hence, we have $$\lfloor 2x \rfloor + \lfloor 2y \rfloor > \lfloor x \rfloor + \lfloor y \rfloor + \lfloor x+y \rfloor$$

share|improve this answer

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.