Binomial Coefficient - Bounds and Asymptotic Formulas

Bounds and Asymptotic Formulas

The following bounds for hold:

Stirling's approximation yields the bounds:

and, in general, for m ≥ 2 and n ≥ 1,

and the approximation

as

The infinite product formula (cf. Gamma function, alternative definition)

yields the asymptotic formulas

as .

This asymptotic behaviour is contained in the approximation

as well. (Here is the k-th harmonic number and is the Euler–Mascheroni constant).

The sum of binomial coefficients can be bounded by a term exponential in and the binary entropy of the largest that occurs. More precisely, for and, it holds

where is the binary entropy of .

A simple and rough upper bound for the sum of binomial coefficients is given by the formula below (not difficult to prove)