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:

    How far men go for the material of their houses! The inhabitants of the most civilized cities, in all ages, send into far, primitive forests, beyond the bounds of their civilization, where the moose and bear and savage dwell, for their pine boards for ordinary use. And, on the other hand, the savage soon receives from cities iron arrow-points, hatchets, and guns, to point his savageness with.
    Henry David Thoreau (1817–1862)

    It is sentimentalism to assume that the teaching of life can always be fitted to the child’s interests, just as it is empty formalism to force the child to parrot the formulas of adult society. Interests can be created and stimulated.
    Jerome S. Bruner (20th century)