9
$\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$
  • $\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$ – Marc van Leeuwen Mar 29 '12 at 11:33
  • 1
    $\begingroup$ $\displaystyle\sqrt[10]{\prod_{k=0}^{10} \binom{10}{k}}\approx 44.7778$. See here. $\endgroup$ – draks ... Mar 29 '12 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 '13 at 5:31
13
$\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$
  • $\begingroup$ How can you get this$\frac{n(n+1)}{2}logn-\frac{n(n+2)}{4}$ $\endgroup$ – 89085731 Mar 30 '12 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 '12 at 6:27
12
$\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$
  • $\begingroup$ Interesting approach! $\endgroup$ – Pedro Tamaroff Apr 2 '12 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 '12 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$
  • $\begingroup$ Actually, I have already done this step, but I don't know how to continue. $\endgroup$ – 89085731 Mar 29 '12 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$ – Marc van Leeuwen Mar 29 '12 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$
  • $\begingroup$ Sorry I made a big mistake.Please see the revision. $\endgroup$ – 89085731 Mar 29 '12 at 12:51
  • 1
    $\begingroup$ But what with the sequence $\small (G_n^{1 \over n}) $? $\endgroup$ – Gottfried Helms Mar 29 '12 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$ – Ragib Zaman Jun 9 '12 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$
  • $\begingroup$ Sorry I made a big mistake.Please see the revision. $\endgroup$ – 89085731 Mar 29 '12 at 12:51

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.