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)

Read more about this topic:  Binomial Coefficient

Famous quotes containing the words bounds and/or formulas:

    Great Wits are sure to Madness near alli’d
    And thin Partitions do their Bounds divide;
    Else, why should he, with Wealth and Honour blest,
    Refuse his Age the needful hours of Rest?
    John Dryden (1631–1700)

    That’s the great danger of sectarian opinions, they always accept the formulas of past events as useful for the measurement of future events and they never are, if you have high standards of accuracy.
    John Dos Passos (1896–1970)