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
    Does anyone know how to get the "doesn't exist" symbol? I thought it was \nexists. Also, using \mathbb_{N} inside the definition of S breaks the rest of the expression (that's why I used a normal N instead of the blackboard-style N).2010-11-01
  • 1
    Try $\not\exists$. It's not great but it gets the message across.2010-11-01
  • 1
    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!2010-11-01
  • 1
    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} $2010-11-01
  • 1
    For integrality proofs of binomial coefficients see also [this thread](http://math.stackexchange.com/questions/2192), which includes my "layperson proof"2010-11-01
  • 1
    +1 for reading this book, it's one of my all time favorites!2010-11-01
  • 2
    There should not be an underscore after `\mathbb`; `\mathbb{N}` gives $\mathbb{N}$.2010-11-02
  • 1
    This result follows combinatorially from the fact that $\frac{(a+b)!}{a!b!}$ counts $a+b$ choose $a$, thus is an integer.2010-11-02
  • 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 mentioned 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.