Stirling's Approximation

Stirling's approximation gives an approximate value for the factorial function  or the gamma function  for . The approximation can most simply be derived for  an integer by approximating the sum over the terms of the factorial with anintegral, so that

			(1)
			(2)
			(3)
			(4)
			(5)

source :http://mathworld.wolfram.com/StirlingsApproximation.html

The product of n consecutive integer is divisible by n!

Proof 1

let n consecutive numbers are m+1, ... , m+n

then, the product is (m+1) * (m+2) * ... * (m+n) = (m+n)!/m! = (m+n) C m

we know binomial coefficient is integer. hence the proof is done.

Proof 2

You could argue by induction on n. The result is obvious if n=1.

For the inductive step, assume that (n−1)! divides any product of n−1 consecutive integers. Now consider products of n consecutive integers.

Say your product is P(k)=(k+1)(k+2)…(k+n). First, you may assume k≥0: If one of the factors k+j is 0, then P(k)=0 and obviously n! divides it. If k+n=−t−1<0, this is the same as

and t≥0.

Now argue by induction on k. The result clearly holds if k=0, since P(0)=n!.

Suppose n!|P(k). Then P(k+1)=(k+2)(k+3)…(k+n+1). Split the last factor as (k+1)+n. We have

The first summand is P(k), which is divisible by n! by the inductive assumption on k. The second summand is n times a product of n−1 consecutive integers, thus n times a multiple of (n−1)!, by the inductive assumption on n. Clearly, n times a multiple of (n−1)! is a multiple of n!, and the sum of two multiples of n! is a multiple of n!, so n!|P(k+1).

We are done by induction.

source : http://math.stackexchange.com/questions/12067/the-product-of-n-consecutive-integers-is-divisible-by-n-without-using-the-prop

I heard it first from friend's blog when i was freshmen.