10
$\begingroup$

$\{{C_k^n}\}_{k=0}^n$ are binomial coefficients. $G_n$ is their geometrical mean.

Prove $$\lim\limits_{n\to\infty}{G_n}^{1/n}=\sqrt{e}$$

$\endgroup$
3
  • $\begingroup$ Unlikely: except for the two extremes they are all at least $n$, and usually quite a bit bigger. Also please show more context (where does this problem come from), and what you've found yourself so far. $\endgroup$ Mar 29, 2012 at 11:33
  • 1
    $\begingroup$ $\displaystyle\sqrt[10]{\prod_{k=0}^{10} \binom{10}{k}}\approx 44.7778$. See here. $\endgroup$
    – draks ...
    Mar 29, 2012 at 11:54
  • 1
    $\begingroup$ If you want to do without Stirling's approximation, check Q6 in math.illinois.edu/~hildebr/putnam/problems/mock11sol.pdf $\endgroup$
    – Macavity
    Dec 16, 2013 at 5:31

5 Answers 5

14
$\begingroup$

$G_n$ is the geometric mean of $n+1$ numbers: $$ G_n=\left[\prod_{k=0}^n{n\choose k}\right]^{\frac1{n+1}} $$ or with $\log$ representing the natural logarithm (to the base $e$), $$ \log G_n = \frac1{n+1} \sum_{k=0}^n \log {n\choose k} = \log n! - \frac2{n+1} \sum_{k=0}^n \log k! \,. $$ Stirling's approximation is $n! \approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$ or $$ \log n! \approx \frac12\log{(2\pi n)}+n\log\left(\frac{n}{e}\right) = \left(n+\frac12\right)\log n+\frac12\log 2\pi-n $$ so $$ \eqalign{ \log \left(G_n\right)^\frac1n & = \frac1n \log G_n = \frac1n \log n! - \frac2{n(n+1)} \log \prod_{k=0}^n k! \\ & = \frac1n \log n! - \frac2{n(n+1)} \sum_{k=0}^n \log k! \\ & \approx \left(1+\frac1{2n}\right) \log n - \frac2{n(n+1)} \sum_{k=1}^n \left(k+\frac12\right)\log k - \frac1{2n}\log 2\pi \\ & \approx \left(1+\frac1{2n}\right) \log n - \frac2{n(n+1)} \left[ \frac{n(n+1)}{2}\log n - \frac{n(n+2)}{4} \right] - \frac1{2n}\log 2\pi \\ & = \frac{\log n-\log 2\pi}{2n} + \frac{n+2}{2(n+1)} \\ & \rightarrow \frac12 \,, } $$ where the sum of logarithms was approximated using the definite integrals $$ \sum_{k=1}^n \log k \approx \int_1^n \log x\,dx = \Big[x\log x-x\Big]_1^n \approx \Big[x\log x-x\Big]_0^n $$ and $$ \sum_{k=1}^n k \log k \approx \int_0^n x\log x\,dx=\left[\frac{x^2}{2}\log x - \frac{x^2}{4}\right]_0^n $$ (using integration by parts as shown in a comment), so that $$ \eqalign{ \sum_{k=1}^n \left(k+\frac12\right)\log k &= \sum_{k=1}^n k \log k + \frac12 \sum_{k=1}^n \log k \\ &\approx \left( \frac{n^2}{2}\log n - \frac{n^2}{4} \right) + \frac12 \Big( n \log n - n \Big) \\ &= \frac{n^2+n}{2}\log n - \frac{n^2+2n}{4} \,. } $$ Thus $$ G_n=e^{\log G_n}\rightarrow e^{\frac12}=\sqrt{e} \,. $$

$\endgroup$
2
  • $\begingroup$ How can you get this$\frac{n(n+1)}{2}logn-\frac{n(n+2)}{4}$ $\endgroup$
    – 89085731
    Mar 30, 2012 at 0:49
  • $\begingroup$ Integration by parts ($n\ge0$): $$\matrix{u=\log x&dv=x^n\\du=x^{-1}dx&v=\frac1{n+1}x^{n+1}}$$ $$\eqalign{\int x^n\,\log x\,dx&=\int u\,dv=uv-\int v\,du\\&=\frac1{n+1}x^{n+1}\log x-\int \frac1{n+1}x^n\,dx\\&=\frac1{n+1}x^{n+1}\log x-\frac1{(n+1)^2}x^{n+1}+c}$$ $\endgroup$
    – bgins
    Mar 30, 2012 at 6:27
13
$\begingroup$

In fact, we have

$$ \lim_{n\to\infty}\left[\prod_{k=0}^{n}\binom{n}{k}\right]^{1/n^2} = \exp\left(1+2\int_{0}^{1}x\log x\; dx\right) = \sqrt{e}.$$

This follows from the identity

$$\frac{1}{n^2}\log \left[\prod_{k=0}^{n}\binom{n}{k}\right] = 2\sum_{j=1}^{n}\frac{j}{n}\log\left(\frac{j}{n}\right)\frac{1}{n} + \left(1+\frac{1}{n}\right)\log n - \left(1+\frac{2}{n}\right)\frac{1}{n}\log (n!),$$

together with the Stirling's formula.

In fact, I tried to write down the detailed derivation of this identity, but soon gave up since it's painstrikingly demanding to type $\LaTeX$ formulas in iPad2!

But you may begin with the identity

$$\log\binom{n}{k} = \log n! - \log k! - \log (n-k)!$$

and

$$ \log k! = \sum_{j=1}^{k} \log j,$$

and then you can change the order of summation.

$\endgroup$
2
  • $\begingroup$ Interesting approach! $\endgroup$
    – Pedro
    Apr 2, 2012 at 2:33
  • $\begingroup$ This is a great answer. I believe your second equation should read $\left(1+\frac{1}{n}\right)$ instead of $\left(1+\frac{2}{n}\right)$. Of course, it doesn't affect your nice result. I deal with a related limit here. Cheers! $\endgroup$
    – user26872
    Jun 10, 2012 at 0:49
3
$\begingroup$

Hint

G is geometric mean:

$$G=\sqrt[n]{C_n^0C_n^1C_n^2\cdots C_n^n}$$

Hence,

$$\ln G=\frac{1}{n}\sum_{k=0}^n \ln C_k^n$$

$\endgroup$
2
  • $\begingroup$ Actually, I have already done this step, but I don't know how to continue. $\endgroup$
    – 89085731
    Mar 29, 2012 at 11:50
  • 5
    $\begingroup$ I would just like to point out the obvious fact that there are $n+1$ binomial coefficients, not $n$, so the formulas need some adaptation. $\endgroup$ Mar 29, 2012 at 13:50
2
$\begingroup$

Sorry but the sequence $(G_n)$ does not converge, neither to $\sqrt{\mathrm e}$ nor to any other finite limit.

For every fixed $k$, Stirling's approximation yields ${2n\choose n+k}=2^{2n+o(n)}$. Keeping only the terms from $n-i$ to $n+i$ in $G_{2n}$, this yields, for every fixed nonnegative $i$ and every $n\geqslant i$, $$ (G_{2n})^{2n+1}=\prod\limits_{k=-n}^n{2n\choose n+k}\geqslant\prod\limits_{k=-i}^i{2n\choose n+k}=2^{2n(2i+1)+o(n)}, $$ hence $\liminf\limits_{n\to\infty} G_n\geqslant2^{2i+1}$. Since this holds for every fixed $i$, $\lim\limits_{n\to\infty} G_n=+\infty$.

$\endgroup$
3
  • $\begingroup$ Sorry I made a big mistake.Please see the revision. $\endgroup$
    – 89085731
    Mar 29, 2012 at 12:51
  • 1
    $\begingroup$ But what with the sequence $\small (G_n^{1 \over n}) $? $\endgroup$ Mar 29, 2012 at 18:49
  • $\begingroup$ The divergence of $G_n$ can also be seen by noting $\binom{n}{k} \geq n} $ for $1\leq k \leq n-1.$ $\endgroup$ Jun 9, 2012 at 17:59
0
$\begingroup$

$$\lim_{n\to\infty} G_n=\lim_{n\to\infty}\sqrt[n]{C_n^0C_n^1C_n^2\cdots C_n^n}=\lim_{n\to\infty}\sqrt[n]{\prod_{k=0}^n \binom{n}{k}}=\frac{n!}{G(n+2)^{2/n}},$$ where $G()$ is Barnes G-Function. $\lim_{n\to \infty}G_n$ diverges as can be seen here.

$\endgroup$
1
  • $\begingroup$ Sorry I made a big mistake.Please see the revision. $\endgroup$
    – 89085731
    Mar 29, 2012 at 12:51

Not the answer you're looking for? Browse other questions tagged .