Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$\{{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}$$

share|improve this question
    
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. –  Marc van Leeuwen Mar 29 '12 at 11:33
1  
$\displaystyle\sqrt[10]{\prod_{k=0}^{10} \binom{10}{k}}\approx 44.7778$. See here. –  draks ... Mar 29 '12 at 11:54
    
If you want to do without Stirling's approximation, check Q6 in math.illinois.edu/~hildebr/putnam/problems/mock11sol.pdf –  Macavity Dec 16 '13 at 5:31
add comment

5 Answers 5

up vote 11 down vote accepted

$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} \,. $$

share|improve this answer
    
How can you get this$\frac{n(n+1)}{2}logn-\frac{n(n+2)}{4}$ –  89085731 Mar 30 '12 at 0:49
    
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}$$ –  bgins Mar 30 '12 at 6:27
add comment

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.

share|improve this answer
    
Interesting approach! –  Pedro Tamaroff Apr 2 '12 at 2:33
    
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! –  user26872 Jun 10 '12 at 0:49
add comment

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$$

share|improve this answer
    
Actually, I have already done this step, but I don't know how to continue. –  89085731 Mar 29 '12 at 11:50
5  
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. –  Marc van Leeuwen Mar 29 '12 at 13:50
add comment

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$.

share|improve this answer
    
Sorry I made a big mistake.Please see the revision. –  89085731 Mar 29 '12 at 12:51
1  
But what with the sequence $\small (G_n^{1 \over n}) $? –  Gottfried Helms Mar 29 '12 at 18:49
    
The divergence of $G_n$ can also be seen by noting $\binom{n}{k} \geq n} $ for $1\leq k \leq n-1.$ –  Ragib Zaman Jun 9 '12 at 17:59
add comment

$$\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.

share|improve this answer
    
Sorry I made a big mistake.Please see the revision. –  89085731 Mar 29 '12 at 12:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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