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.

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

share|improve this question
1  
Try $\not\exists$. It's not great but it gets the message across. –  lhf Nov 1 '10 at 22:09
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! –  Bill Dubuque Nov 1 '10 at 22:11
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} $ –  Bill Dubuque Nov 1 '10 at 22:21
1  
For integrality proofs of binomial coefficients see also this thread, which includes my "layperson proof" –  Bill Dubuque Nov 1 '10 at 22:28
2  
There should not be an underscore after \mathbb; \mathbb{N} gives $\mathbb{N}$. –  J. M. Nov 2 '10 at 0:20

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
@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$.

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

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.