Problem 46. While the formula you proved in Problems 35 and 39.d is very
useful, it doesn't give us a sense of how big the binomial coefficients are.
We can get a very rough idea, for example, of the size of (²") by recognizing
that we can write (2n)n/n! as 2n n 2n- n-1 1 n+1, 1 and each quotient is at least
2, so the product is at least 2n. If this were an accurate estimate, it would
mean the fraction of n-element subsets of a 2n-element set would be about
2"/2²M = 1/2", which becomes very small as n becomes large. However it
of the terms in that product are much larger than 2. In fact, if 2n ) were
same for every k, then each would be the fraction
of 22M. This is much
larger than the fraction 1/2 But our intuition suggets that (2" ) is much larger
than (4) and is likely larger than n-1 2n ) so we can be sure our approximation
is a bad one. For estimates like this, James Stirling developed a formula to
approximate n! when n is large, namely n! is about (V2nn)nnjen. In fact
write this as
We read this notation as n! is asymptotic to 2nn Use Stirling's for-
approximately This is a much bigger fraction than 1/2
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.