6
$\begingroup$

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!)$

  • 0
    @fmartin: Ok, I posted an answer. I didn't do so before since I wasn't sure that the comments settled all your questions.2010-11-03

3 Answers 3

0

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

  • 0
    That was already me$n$tioned in the comments - see the prior discussion there.2010-11-02
1

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.

  • 0
    @Paolo: Of course, but he's asking about a specific proof - see the prior discussion in the comments.2010-11-02
1

Per fmartin's request, I've collected my above comments into an answer.

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.