proof of upper and lower bounds to binomial coefficient

Let 2kn be natural numbersMathworldPlanetmath. We’ll first prove the inequalityMathworldPlanetmath


We rewrite (nk) as

(nk) = n(n-1)(n-k+1)k!
= (1-1n)(1-k-1n)nkk!

Since each of the parenthesized factors lies between 0 and 1, we have


Since all the terms of the series ek=n=0kn/n! are positive when k is a positive real number, each term must be smaller than the whole sum; in particular, this implies that, for any non-negative integer k, we have ek>kk/k!. Rearranging this slightly,


Multiplying this inequality by the previous inequality for the binomial coefficientMathworldPlanetmath yields


To conclude the proof we show that

i=1n-1(1+1i)i=nnn!n2. (1)
i=1n-1(1+1i)i = i=1n-1(i+1)iii
= i=2nii-1(i=1n-1ii-1)(n-1)!

Since each left-hand factor in (1) is <e, we have nnn!<en-1. Since n-i<n 1ik-1, we immediately get

(nk) = i=2k-1(1-1i)k!<nkk!.

And from

kn (n-i)k(k-i)n 1ik-1

we obtain

(nk) = nki=1k-1n-ik-i
Title proof of upper and lower bounds to binomial coefficient
Canonical name ProofOfUpperAndLowerBoundsToBinomialCoefficient
Date of creation 2013-03-22 13:49:06
Last modified on 2013-03-22 13:49:06
Owner rspuzio (6075)
Last modified by rspuzio (6075)
Numerical id 12
Author rspuzio (6075)
Entry type Proof
Classification msc 05A10