12
$\begingroup$

I try to compute the following limit:

$$\lim_{n\to\infty}\left(\prod_{k=1}^{n} \binom{n}{k}\right)^\frac{1}{n}$$

I'm interested in finding some reasonable ways of solving the limit. I don't find any easy approach. Any hint/suggestion is very welcome.

$\endgroup$
12
$\begingroup$

All the binomial coefficients except the last one are at least $n$, so the $n$th root is at least $n^{\frac{n-1}{n}}$, so the limit is infinity.

$\endgroup$
  • $\begingroup$ @QiaochuYuan Oops, thanks. $\endgroup$ – Phira Jun 9 '12 at 17:13
5
$\begingroup$

Start with the identity $$\prod_{j=1}^n {n\choose j} =\prod_{k=1}^n {k^k\over k!}.$$ Since $k^k/k!\to \infty$, the same is true of its geometric mean: $$\left(\prod_{k=1}^n {k^k\over k!}\right)^{1/n}\to\infty.$$

$\endgroup$
  • $\begingroup$ an interesting and nice approach. Thanks! $\endgroup$ – user 1357113 Jun 9 '12 at 19:53
4
$\begingroup$

As noted by Phira and Byron Schmuland, the product diverges. I find an asymptotic expression for the product for large $n$, Eqn. (3) below.

I have found some inspiration for this solution in @sos440's answer here.

With a little work, one can show that $$\begin{equation*} \log \left(\prod_{k=1}^n{n\choose k}\right)^{1/n} = -\frac{n+1}{n}\log n! + (n+1)\log n + 2 \sum_{j=1}^n \frac{j}{n}\log\frac{j}{n}. \tag{1} \end{equation*}$$ For a derivation of (1), see below. Using Stirling's approximation, and the fact that $\sum_{j=1}^n \frac{j}{n}\log\frac{j}{n} \approx n\int_0^1 x \log x = -n/4$ (the error here is $O(\log(n)/n)$), we get $$\begin{equation*} \log \left(\prod_{k=1}^n{n\choose k}\right)^{1/n} \sim \frac{n}{2}+1 - \frac{1}{2} \log 2\pi n.\tag{2} \end{equation*}$$ Therefore, $$\begin{equation*} \left(\prod_{k=1}^n{n\choose k}\right)^{1/n} \sim \frac{e^{n/2+1}}{\sqrt{2\pi n}}. \tag{3} \end{equation*}$$ Clearly the product diverges. For $n=10$, $100$, and $1000$ the left and right side of (3) agree to $12\%$, $2.0\%$, and $0.28\%$, respectively.

From (3) we get the result $\lim_{n\to\infty} \left(\prod_{k=1}^n{n\choose k}\right)^{1/n^2} = \sqrt{e}$ for free. (Use $\lim_{n\to\infty} x^{1/n} = 1$ for $0<x<1$.)

Derivation of Eqn. (1)

Note that $$\begin{eqnarray*} \log \left(\prod_{k=1}^n{n\choose k}\right)^{1/n} &=& \log \left(\prod_{k=0}^n{n\choose k}\right)^{1/n} \\ &=& \frac{1}{n} \sum_{k=0}^n \log {n\choose k} \\ &=& \frac{1}{n} \sum_{k=0}^n \left(\log n! - \log k! - \log (n-k)! \right)\\ &=& \frac{1}{n} \left((n+1)\log n! - 2 \sum_{k=0}^n\log k! \right). \end{eqnarray*}$$ But $$\begin{eqnarray*} \sum_{k=0}^n\log k! &=& \sum_{k=1}^n\log k! \\ &=& \sum_{k=1}^n \sum_{j=1}^k \log j \\ &=& \sum_{j=1}^n \sum_{k=j}^n \log j \\ &=& \sum_{j=1}^n (n+1-j) \log j \\ &=& (n+1)\sum_{j=1}^n \log j - \sum_{j=1}^n j (\log j -\log n + \log n) \\ &=& (n+1)\log n! - \frac{n(n+1)}{2} \log n - \sum_{j=1}^n j\log\frac{j}{n}. \end{eqnarray*}$$ Eqn. (1) follows immediately.

Some key identities: $$\begin{eqnarray*} \log n! &=& \sum_{k=1}^n \log k \\ \sum_{k=j}^n 1 &=& n+1-j \\ \sum_{k=1}^n k &=& \frac{n(n+1)}{2} \\ \sum_{k=1}^n \sum_{j=1}^k a_{j k} &=& \sum_{j=1}^n \sum_{k=j}^n a_{j k} \end{eqnarray*}$$

$\endgroup$
  • $\begingroup$ Great answer. I was going to suggest maybe accelerating the $1/n$ would make it converge: interesting result! $\endgroup$ – Pedro Tamaroff Jun 10 '12 at 0:58
  • $\begingroup$ @PeterTamaroff: Thanks, Peter. As you probably know, if we hit the product with another power of $1/n$ we get this problem. Cheers! $\endgroup$ – user26872 Jun 10 '12 at 1:05
  • $\begingroup$ @oenamen: excellent work! Thanks! $\endgroup$ – user 1357113 Jun 10 '12 at 7:12
  • $\begingroup$ @Chris: Thank you for the interesting question! $\endgroup$ – user26872 Jun 10 '12 at 16:00
  • $\begingroup$ @oenamen: your answer was far more interesting than my question, a real lesson to study! Thanks! $\endgroup$ – user 1357113 Jun 10 '12 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.