# Proving that if a and b are natural numbers, then a!b! | (a+b)!

This is the first exercise from Sierpinski's Elementary Theory of Numbers. He gives a proof using induction and I was wondering if this approach was correct as well:

$a!b!|(a+b)! \iff \exists c \in \mathbb{N} \text{ such that } (a+b)! = c(a!b!)$

Assuming without loss of generality that $a \leq b$:

$a!b! = \displaystyle\prod\limits_{n=1}^a n^2 \displaystyle\prod\limits_{n=a+1}^b n$

Then we define the set S:

$S = \{n \in \mathbb{N} :n < a^2 \wedge \not \exists m \in \mathbb{N}\text{ such that }m^2=n) \}$

If $c = \displaystyle\prod\limits_{n \in D}n \displaystyle\prod\limits_{n=b+1}^{a+b}n$,

then $(a+b)! = c(a!b!)$

-
Try $\not\exists$. It's not great but it gets the message across. – lhf Nov 1 '10 at 22:09
Something appears to be wrong. The 2nd last equation is c = de, where e = (b+1)...(a+b). Therefore (a+b)! = d(b+1)...(a+b)a!b! = da!(a+b)! implies 1 = d a! – Bill Dubuque Nov 1 '10 at 22:11
Note that Sierpinski's proof is expressed more clearly by explicitly mentioning the underlying binomial idenity, viz. $\binom{a+b}{a} = \binom{a+b-1}a + \binom{a+b-1}{a-1}$ – Bill Dubuque Nov 1 '10 at 22:21
For integrality proofs of binomial coefficients see also this thread, which includes my "layperson proof" – Bill Dubuque Nov 1 '10 at 22:28
There should not be an underscore after \mathbb; \mathbb{N} gives $\mathbb{N}$. – J. M. Nov 2 '10 at 0:20

The proposed approach doesn't work. The 2nd last equation is $c = de$, where $e = (b+1)\cdots (a+b)$. Therefore $(a+b)! = d(b+1)\cdots (a+b)a!b! = da!(a+b)!$ implies $1 = d a!$

Note that Sierpinski's inductive proof is expressed much more clearly by explicitly mentioning the underlying binomial identity that enables the descent, viz. $\binom{a+b}a = \binom{a+b-1}a + \binom{a+b-1}b$.

For various integrality proofs of binomial coefficients see also this thread. There you'll find a very simple proof I discovered that shows how to write a binomial coefficient as a product of fractions whose denominators are all coprime to any given prime p.

-

It is known that (a+b)!/a!b! represents the number of combinations of (a + b) elements, taken "b to b". Therefore, it is an integer.

-
@Paolo: Of course, but he's asking about a specific proof - see the prior discussion in the comments. – Bill Dubuque Nov 2 '10 at 17:33

Try $a=b=2$. Then $(a+b)!/a!/b! = 6$ and so $\prod_{n=b+1}^{a+b} n = 12$ cannot divide your $c$.

-
That was already mentioned in the comments - see the prior discussion there. – Bill Dubuque Nov 2 '10 at 17:32