On the geometric mean of the binomial coefficients

Today we prove a remarkable asymptotic result regarding the binomial coefficients. Namely, let G_n=\left(\prod_{k=1}^n\binom{n}{k}\right)^{\tfrac{1}{n+1}}. We will show

\displaystyle \lim_{n\to\infty}G_n^{\frac{1}{n}}=\sqrt{e}.

Before getting to the proof, I should say that this is most definitely not my creation; I believe the first publication of this proof may be credited to Polya (but I am not sure). In any case, I was shown this proof at MSU in my Putnam training seminar. It was presented by Dr. Ignacio Uriarte-Tuero. Any unintended errors introduced are mine alone.

To start, we use the definition of \binom{n}{k} to write

\begin{aligned} G_n^{n+1}&=\prod_{k=1}^n\binom{n}{k}\\&=\frac{(n!)^{n+1}}{\prod_{k=1}^n(k!)^2}\end{aligned}

Now for 1\leq j\leq n, we want to examine the power of j which appears in the fraction. So, for instance, n appears n+1 times in the numerator and twice in the denominator from (n!)^2, n-1 appears n+1 times in the numerator and four times in the denominator from (n!)^2 and ((n-1)!)^2, etc. We get the formula

G_n^{n+1}=\prod_{k=1}^n(n+1-k)^{n+1-2k}

We now multiply by 1 in a clever way. Noting that \sum_{k=1}^n(n+1-2k)=0 we obtain

G_n^{n+1}=\prod_{k=1}^n(n+1-k)^{n+1-2k}=\prod_{k=1}^n\left(\frac{n+1-k}{n+1}\right)^{n+1-2k}

as the denominator has total exponent 0. We can now write

G_n=\prod_{k=1}^n\left(\frac{n+1-k}{n+1}\right)^{1-\frac{2k}{n+1}}=\prod_{k=1}^n\left(1-\frac{k}{n+1}\right)^{1-\frac{2k}{n+1}}

We want to examine G_n^{\frac{1}{n}}. Taking logarithms, we get

\frac{1}{n}\ln(G_n)=\frac{1}{n} \sum_{k=1}^n(1-\frac{2k}{n+1})\ln(1-\frac{k}{n+1})

We now recognize this expression as a Riemann sum of the function g(x)=(1-2x)\ln(1-x) on the interval {}[0,1]. (Ok, it is not exactly a Riemann sum; we should be dividing by n+1, not n. But in the limit this will not matter.) Taking limits, it follows that

\lim_{n\to\infty}\frac{\ln(G_n)}{n}=\lim_{n\to\infty}\frac{1}{n} \sum_{k=1}^n(1-\frac{2k}{n+1})\ln(1-\frac{k}{n+1})=\int_0^1(1-2x)\ln(1-x)dx

Evaluating the integral is now easy via integration by parts; it turns out that

 \int_0^1(1-2x)\ln(1-x)dx=\frac{1}{2}

and thus \lim_{n\to\infty}\ln(G_n^{\frac{1}{n}})=\frac{1}{2} and \lim_{n\to\infty} G_n^{\frac{1}{n}}=\sqrt{e}.

And we’re done! As always, thanks for reading!

Advertisements
This entry was posted in Asymptotics, Combinatorics, Contest Math. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s