If b divides a!(n-a)!, does b divide n!

[icantadd]

Homework Statement

Suppose b | a!(n-a)! and prove that b | n!

Homework Equations

m | n <=> n = am

The Attempt at a Solution

b | a!(n-a)! ,so that
a!(n-a)! = bs, so that
a!(n-a)!(nCa) = bs(nCa) (nCa is a combinations of n items)
n! = bs(nCa)
And so b is obviously a divisor of n!

 

[icantadd]

We can show a!b! divides (a+b)!

WLOG assume a > b,

First, make the following observation,

$$\frac{(a+b)!}{a!b!} = \frac{(a+b)(a+b-1) \ldots (b+1) b!}{a!b!} = \frac{(a+b)(a+b-1) \ldots (b+1)}{a!}$$

Now, by induction on b, if b=1,
$$(a+b)! = (a+1)! = (a+1)a! = (a+1)a!b!$$
So by definition we have that a!b! divides (a+b)!

So assume the result holds for b, and we will show the result holds for b+1. Now, consider,

$$\frac{(a+b+1)!}{a!(b+1)!} = \frac{(a+b+1)(a+b)(a+b-1) \ldots (b+1)!}{a!(b+1)!}$$


Next, we will be a bit tricky by bracketing things off right.


$$\frac{(a+b+1)(a+b)(a+b-1) \ldots (b+1)b!}{(b+1)!a!} = \frac{(a+b+1)b!(a+b)(a+b-1) \ldots (b+1)}{(b+1)!a!}$$

Now, it suffices to show the above is an integer. First let's consider what our inductive hypothesis tells us. It says that a! divides (a+b)(a+b-1) ... (b+1). So there is some integer d such that,

$$\frac{(a+b)(a+b-1) \ldots (b+1)}{a!} = d$$

Now we have to show the following is an integer,but

$$\frac{(a+b+1)b!}{(b+1)!} = \frac{(a + (b+1))b!}{(b+1)!} = \frac{ab! + (b+1)!}{(b+1)!}$$

Err, ?