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)!} <br />
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, ?
