Finding the limit of $\sqrt[n]{{kn \choose n}}$

Solution 1:

You were on the good track at the beginning. There were other simplifications you could have done, though. Start from :

$$r_k(n) := \frac{{kn+k \choose n+1}}{{kn \choose n}} = \frac{\frac{(kn+k)!}{(n+1)!(kn+k-n-1)!}}{\frac{(kn)!}{n!(kn-n)!}} = \frac{(kn+k)!n!(kn-n)!}{(n+1)!(kn+k-n-1)!kn!} =\frac{(kn+k-n)(kn+k-n+1)\cdots(kn+k)}{(n+1)(kn-n+1)\cdots(kn-n)}$$

However, let's change the way we simplify at the last step. We then get :

$$r_k(n) = \frac{1}{n+1} \frac{(kn+1)\cdots (kn+k)}{(kn-n+1)\cdots(kn+k-n-1)} = \frac{kn+k}{n+1} \prod_{j=1}^{k-1} \frac{kn+j}{(k-1)n+j}$$

Now, the magic is that the number of terms in the product is constant in $n$ (which was not the case with your simplifications). In addition, for all $j$,

$$\lim_{n \to + \infty} \frac{kn+j}{kn-n+j} = \frac{k}{k-1},$$

whence:

$$\lim_{n \to + \infty} r_k(n) = k \left( \frac{k}{k-1} \right)^{k-1} = \frac{k^k}{(k-1)^{k-1}},$$

and we are done.

Solution 2:

Proof 1:

Write $\binom{kn}{n}$ as a quotient of two central multinomial coefficients: $\binom{kn}{\underbrace{n,n,\cdots,n}_{k\text{ times}}} \cdot \left(\binom{(k-1)n}{\underbrace{n,n,\cdots,n}_{k-1\text{ times}}} \right)^{-1}$.

Now, to finish, it is enough to prove $\lim \binom{kn}{\underbrace{n,n,\cdots,n}_{k\text{ times}}}^{1/n} = k^k$. The proof of this is really nice: $\binom{kn}{\underbrace{n,n,\cdots,n}_{k\text{ times}}}$ is smaller than the sum $\sum_{a_1 + \cdots + a_k =nk} \binom{kn}{a_1,\cdots,a_k}=(\underbrace{1+\cdots+1}_{k\text{ times}})^{nk} = k^{nk}$, and so $\binom{kn}{\underbrace{n,n,\cdots,n}_{k\text{ times}}}^{1/n} \le k^k$.

To get a lower bound, just prove that the maximum of $f(a_1, \cdots, a_k)=\binom{nk}{a_1,a_2,\cdots,a_k} (\sum a_i = nk)$ is achieved at $\forall i: a_i = n$ by some convexity argument, and so $\binom{kn}{\underbrace{n,n,\cdots,n}_{k\text{ times}}}$ is bigger than the average of all $\binom{nk}{a_1,a_2,\cdots,a_k}$, which is $\frac{k^{kn}}{\binom{nk+k-1}{k-1}}$ (the denominator is number of solutions to $a_1 + \cdots + a_k = nk$, which is a polynomial in $n$ of degree $k-1$), and so $\binom{kn}{\underbrace{n,n,\cdots,n}_{k\text{ times}}}^{1/n} \ge \frac{k^k}{1+o(1)}$ and we're done.

Proof 2:

Lemma: $\lim \frac{n!^{1/n}}{n} = e^{-1}$. Given the lemma, $\lim \frac{(kn)!^{1/n}}{(kn)^k} = e^{-k}, \lim \frac{((k-1)n)!^{1/n}}{((k-1)n)^{k-1}} = e^{-(k-1)}$, and we find via some algebra:

$$\lim \binom{kn}{n}^{1/n} = \lim \frac{(kn)!^{1/n}}{(kn)^k} \left(\frac{((k-1)n)!^{1/n}}{((k-1)n)^{k-1}} \right)^{-1} \left( \frac{(n)!^{1/n}}{n} \right)^{-1} \frac{k^k}{(k-1)^{k-1}}= \frac{k^k}{(k-1)^{k-1}}$$

Proof of lemma: For example, prove the inequality $\frac{e^{n-1}}{n} \le \frac{n^n}{n!} \le e^{n-1}$ by induction, and take $n$'th root. This inequality can also be proved by taking logarithms and using the trivial bound $\int_{i-1}^{i} \ln x dx < \ln i < \int_{i}^{i+1} \ln x dx$.

Solution 3:

Note that $\frac{n!}{(n-k)!} \sim n^k$, now use the variables you have, you get $\frac{nk!}{(nk - n)!} \sim (nk)^n$. Hence the limit becomes $$ \lim_{n \to \infty} e^{\frac{1}{n} \bigg(n \log nk - n \log n +n +O(1) \bigg)} = k\exp(1) $$ This is because the second term is bounded by 2 corresponding integrals: $n \log n +n +1 <\log n! = \sum_{k=1}^{n} \log k < (n+1) \log (n+1) +n $.