10
$\begingroup$

Let $$x_n=\frac{1}{n^2}\sum_{k=0}^n \ln\left(n\atop k\right).$$ Find the limit of $x_n$.

What I can do is just use Stolz formula. But I could not proceed.

$\endgroup$
6
$\begingroup$

The limit is $\frac{1}{2}$. We have $$\begin{eqnarray*} \sum_{k=0}^n \log {n\choose k} &=& \sum_{k=0}^n \log n! - \sum_{k=0}^n \log k! - \sum_{k=0}^n \log (n-k)! \\ &=& (n+1)\log n! - 2\sum_{k=1}^n \log k!. \end{eqnarray*}$$ But $$\begin{eqnarray*} \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-j+1)\log j \\ &=& (n+1)\sum_{j=1}^n \log j - \sum_{j=1}^n j\log j \\ &=& (n+1)\log n! - n^2 \frac{1}{n}\sum_{j=1}^n \frac{j}{n}\log \frac{j}{n} - \sum_{j=1}^n j\log n \\ &=& (n+1)\log n! - n^2\int_0^1 dx\ x\log x - \frac{n(n+1)}{2}\log n + O(n\log n) \\ &=& (n+1)\log n! +\frac{n^2}{4} - \frac{n(n+1)}{2}\log n + O(n\log n). \end{eqnarray*}$$ (The error estimate above can probably be tightened.)

Using Stirling's approximation we find $$\begin{eqnarray*} \frac{1}{n^2}\sum_{k=0}^n \log {n\choose k} &=& -\frac{n+1}{n^2}(\log n! - n\log n) - \frac{1}{2} + O\left(\frac{\log n}{n}\right) \\ &=& -\frac{n+1}{n^2}(-n + O(\log n)) - \frac{1}{2} + O\left(\frac{\log n}{n}\right) \\ &=& \frac{1}{2} + O\left(\frac{\log n}{n}\right). \end{eqnarray*}$$

$\endgroup$
3
$\begingroup$

The sum does not diverge, but converges. I suspect it converges to $1/2$ based on the value at $n=5000$ [link], but I've only managed to bound it by $3/4$.

From Wikipedia, $$\binom{n}{k} \leq \left(\frac{n \cdot e}{k}\right)^k$$

Then, $$\begin{align} x_n=\frac{1}{n^2}\sum_{k=0}^n\ln \binom{n}{k}&\leq \frac{1}{n^2}\sum_{k=0}^n\ln \left(\frac{n \cdot e}{k}\right)^k\\ &=-\frac{1}{n^2}\sum_{k=0}^n k\ln \left(\frac{k}{n \cdot e}\right)\\ &=-\frac{1}{n}\sum_{k=0}^n \left(\frac{k}{n}\right)\ln \left(\frac{k}{n \cdot e}\right)\end{align}$$

Looking at this as a Riemann Sum,

$$\begin{align} \lim_{n \to \infty} x_n &\leq \lim_{n \to \infty}-\frac{1}{n}\sum_{k=0}^n \left(\frac{k}{n}\right)\ln \left(\frac{k}{n \cdot e}\right) \\ &= \int_0^1 -x\ln\left(\frac{x}{e}\right)\mathrm{d}x \\ &=\left.\frac{x^2}{4}-\frac{x^2}{2}\ln x+\frac{x^2}{2}\ln e\right|_0^1 \\ &=\frac{3}{4} \end{align}$$

You can also bound it from below by $\frac{1}{4}$ by taking $\binom{n}{k} \geq \left(\frac{n}{k}\right)^k$.

$\endgroup$
1
$\begingroup$

I've managed to reduce it somewhat. $$x_n=\frac{1}{n^2}\ln(\prod_{k=0}^n \binom{n}{k})$$

$$x_n=\frac{1}{n^2}\ln \left ( \frac{n!}{(n-0)!0!}\frac{n!}{(n-1)!1!}\frac{n!}{(n-2)!2!}...\frac{n!}{(n-n)!n!}\right )$$

$$x_n=\frac{1}{n^2}\ln \left ( \frac{n!^{(n+1)}}{(0!1!2!...n!)^2} \right )$$

$$x_n=\frac{n+1}{n^2}\ln \left ( n! \right )-\frac{2}{n^2}\ln \left ( 0!1!2!...n! \right )$$

$$x_n=\frac{n+1}{n^2}\ln \left ( n! \right )-\frac{2}{n^2}\sum_{k=0}^n \ln(k!)$$

Using Stirling's approximation for large $n$ ($ \ln(n!)=n \ln(n)-n$):

$$x_n=\frac{n+1}{n^2}(n \ln(n)-n)-\frac{2}{n^2}\sum_{k=0}^n \ln(k!)$$

$$x_n=\frac{n \ln(n)-n}{n}+\frac{n \ln(n)-n}{n^2}-\frac{2}{n^2}\sum_{k=0}^n \ln(k!)$$

$$x_n=\ln(n)-1+\frac{ \ln(n)-1}{n}-\frac{2}{n^2}\sum_{k=0}^n \ln(k!)$$

Noting that $\lim_{n \rightarrow \infty} \frac{\ln(n)}{n}=0$, for $n \rightarrow \infty$:

$$x_n=\ln(n)-1-\frac{2}{n^2}\sum_{k=0}^n \ln(k!)$$

$\endgroup$
0
$\begingroup$

$x_n=\frac{1}{n^2}\sum_{k=0}^{n}\ln{n\choose k}=\frac{1}{n^2}\ln(\prod {n\choose k})=\frac{1}{n^2}\ln\left(\frac{n!^n}{n!^2.(n-1)!^2(n-2)!^2...0!^2}\right)$ since ${n\choose k}=\frac{n!}{k!(n-k)!}$

$e^{n^2x_n}=\left(\frac{n^n(n-1)!}{n!^2}\right)e^{(n-1)^2x_{n-1}}=\left(\frac{n^{n-1}}{n!}\right)e^{(n-1)^2x_{n-1}}$

By Stirling's approximation, $n! \sim n^ne^{-n}\sqrt{2\pi n}$

$e^{n^2x_n}\sim \left(\frac{e^n}{n\sqrt{2\pi n}}\right)e^{(n-1)^2x_{n-1}}$

$x_n \sim \frac{(n-1)^2}{n^2}x_{n-1}+\frac{1}{n}-\frac{1}{n^2}\ln(n\sqrt{2\pi n})$

The $\frac{1}{n}$ term forces $x_n$ to tend to infinity, because $\frac{1}{n^2}\ln(n\sqrt{2\pi n})$ does not grow fast enough to stop it diverging.

$\endgroup$
0
$\begingroup$

$$ \frac{1}{n^2}\sum_{k=0}^{n}ln\binom n k =\frac{1}{n^2}\sum_{k=0}^{n}ln\frac{n!}{k!(n-k)!} =\frac{1}{n^2}\sum_{k=0}^{n}(ln(n!)-ln(k!)-ln((n-k)!)) =\frac{1}{n^2}\sum_{k=0}^{n}ln(n!)-\frac{2}{n^2}\sum_{k=1}^{n}ln(k!) =\frac{n+1}{n^2}ln(n!)-\frac{2}{n^2}\sum_{k=0}^{n}ln(k!) $$

because ln(n!)~nln(n)-n,so

$$ \frac{1}{n^2}\sum_{k=0}^{n}ln\binom n k =\frac{n+1}{n^2}(nln(n)-n)-\frac{2}{n^2}\sum_{k=1}^{n}(kln(k)-k) $$

then I am going to prove $\sum_{k=1}^{n}(kln(k)) \rightarrow \frac{n^2}{2}(ln(n)-1/2)$

$$ \int_{i=x-1}^{x}(iln(i))dx<xln(x)<\int_{i=x}^{x+1}(iln(i))dx $$

and

$$ \int(xln(x))dx=x^2/2(lnx-1/2) $$

so sum it up, we got $$ \sum_{k=1}^{n}(kln(k)) \rightarrow \frac{n^2}{2}(ln(n)-\frac{1}{2}) $$ then

$$ \frac{1}{n^2}\sum_{k=0}^{n}ln\binom n k =\frac{n+1}{n^2}(nln(n)-n)-\frac{2}{n^2}\sum_{k=1}^{n}(kln(k)-k) =\frac{n+1}{n}(ln(n)-1)-\frac{2}{n^2}(\frac{n^2}{2}(lnn-\frac{1}{2})-\frac{n(n+1)}{2}) =ln(n)-1-(ln(n)-1/2-1)=1/2 $$

$\endgroup$
0
$\begingroup$

For a two terms estimate of the behaviour of $\displaystyle\prod_{k=0}^{n}\binom{n}{k}$ one can check out March 2013 volume of Asymmetry problem V2-4 here (http://akotronismaths.blogspot.gr/p/asymmetry-electronic-mathematical.html)

$\endgroup$

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.