# Homework Help: If b | a!(n-a)! can one say b | n!

1. Nov 28, 2009

1. The problem statement, all variables and given/known data

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

2. Relevant equations

m | n <=> n = am

3. 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!

2. Nov 28, 2009

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, ?