A Limit that has Binomials $\lim_{n\to \infty}\sqrt[n^2 +n]{\prod_{i=0}^n \frac{n!}{i!(n-i)!}} $

Question

I found a weird binomial limit in a Olympiad problem.

$$\lim_{n\to \infty}\sqrt[n^2 +n]{\prod_{i=0}^n \frac{n!}{i!(n-i)!}} $$

My first aproavh was to try to make it into a Riemann Sum but that doesn't seem to work. Can any help me?

Answer 1

$$ f(n) = \sqrt[n^2 +n]{\prod_{i=0}^n \frac{n!}{i!(n-i)!}} $$

$$ \ln f(n) = \frac{1}{n^2+n} \sum_{i=0}^n \left[ \ln(n!) - \ln(i!) - \ln((n-i)!)\right] $$

Since $\sum_{i=0}^n \ln(i!) = \sum_{i=0}^n \ln((n-i)!)$ by change of index variable,

$$ \ln f(n) = \frac{1}{n^2+n} \left[ (n+1) \ln(n!) - 2 \sum_{i=0}^n \ln(i!) \right] $$

We can also write $n!$ as a product and therefore $\ln(n!)$ as a sum:

$$ \ln f(n) = \frac{1}{n^2+n} \left[ \sum_{j=1}^n (n+1)\ln j - 2 \sum_{i=0}^n \sum_{j=1}^i \ln j \right] $$

$$ \ln f(n) = \frac{1}{n^2+n} \left[\sum_{j=1}^n (n+1)\ln j -2 \sum_{j=1}^n (n-j+1) \ln j\right] $$ $$ \ln f(n) = \frac{1}{n^2+n} \sum_{j=2}^n (2j-n-1) \ln j $$

where the $j=1$ case can be dropped since $\ln 1=0$.

Now we can use Riemann sum bounds, on

$$ g(n) = \sum_{j=2}^n (2j-n-1) \ln j $$

Since $(2x-n-1)\ln x$ is increasing for positive real $x$,

$$ \int_1^n (2x-n-1) \ln x\, dx \leq g(n) \leq \int_2^{n+1} (2x-n-1) \ln x\, dx $$

(where equality holds only when $n=1$.) The indefinite integral is solved by integration by parts:

$$ \begin{align*} G(n,x) &= \int (2x-n-1) \ln x\, dx \\ G(n,x) &= \big[x^2-(n+1)x\big]\ln x - \int \frac{x^2-(n+1)x}{x} dx \\ G(n,x) &= \big[x^2-(n+1)x\big]\ln x - \frac{1}{2}x^2 + (n+1)x + C \end{align*} $$

$$ G(n,n)-G(n,1) \leq g(n) \leq G(n,n+1) - G(n,2) $$

$$ \begin{align*} g(n) &\geq \left(-n\ln n + \frac{1}{2}n^2 + n \right) - \left(n+\frac{1}{2}\right) \\ g(n) &\geq \frac{1}{2} n^2 -n\ln n +\frac{1}{2} \\ g(n) &\leq \left(\frac{1}{2} (n+1)^2\right) - \left((2-2n)\ln 2 +2n\right) \\ g(n) &\leq \frac{1}{2}(n-1)^2 + (2n-2) \ln 2 \end{align*} $$

Going back to $f$,

$$ \frac{\frac{1}{2} n^2 - n \ln n + \frac{1}{2}}{n^2+n} \leq \ln f(n) \leq \frac{\frac{1}{2}(n-1)^2 + (2n-2) \ln 2}{n^2+n} $$ $$ \lim_{n\to \infty} \ln f(n) = \frac{1}{2} $$ $$ \lim_{n\to\infty} f(n) = \sqrt{e} $$

This agrees with the numerical evaluation $1.6487...$ in a comment.

Answer 2

Probably too complex.

Using the Barnes G function $$\prod_{i=0}^n \frac {n!}{i!\,(n-i)!}= \frac{\Gamma (n+1)^n}{G(n+1)\, G(n+2)}$$

Using the asymptotics $$\log(G(p))=\frac{1}{4} (2 \log (p)-3) p^2+\left(\log \left(\frac{\sqrt{2 \pi }}{p}\right)+1\right) p+\frac{1}{12} (5 \log (p)-6 \log (2 \pi )-12 \log (A)+1)-\frac{1}{12 p}-\frac{1}{240 p^2}+O\left(\frac{1}{p^3}\right)$$ Applying it twice as well as Stirling approximation and Taylor series to finish, we end with the simple $$\log\Bigg[\sqrt[n^2 +n]{\prod_{i=0}^n \frac{n!}{i!(n-i)!}}\Bigg]=\frac 12 +\frac {1-\log(2\pi n)} n+O\left(\frac{1}{n^3}\right)$$