Theorem: The product of any n consecutive positive integers is divisible by n! for n ≥ 1.
Proof: Let p be such a product, represented as
(1) p = k(k + 1)…(k + n - 1) for some k ε
Z+
Then p can also be represented using
factorials:
(2) p = (k + n - 1)!/(k - 1)!
Now let m = k + n - 1, and (2) can be rewritten as
(3) p = m!/(m - n)!
To prove the theorem, it suffices to show that p/n! is an integer for any n ≥ 1 and any k ≥ 1. First note that since k ≥ 1, then k - 1 ≥ 0, hence
(4) m = n + k - 1 ≥ n ≥ 1
Now, if we divide p by n! we get
(5) p/n! = m!/(n!(m - n)!)
which, because of the relationship described in (4), is precisely C(m, n) =
m choose n:
(6) p/n! = C(m, n)
Since C(m, n) is always an integer, the theorem is proved. Q.E.D.