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

Question

As part of homework I'm trying to find the limit of $\sqrt[n]{{kn \choose n}}$ (with $k\in\mathbb{N}$ a given parameter).

I've seen This limit: $\lim_{n \rightarrow \infty} \sqrt [n] {nk \choose n}$., on which the only answer suggests using Stirling's approximation, which I've never learned and I can't seem to understand.

Trying to solve this myself, I first tried finding the ratio directly, which gave me $$\frac{{kn+k \choose n+1}}{{kn \choose n}}=\frac{\frac{\left(kn+k\right)!}{\left(n+1\right)!\left(kn+k-n-1\right)!}}{\frac{kn!}{n!\left(kn-n\right)!}}=\frac{\left(kn+k\right)!n!\left(kn-n\right)!}{\left(n+1\right)!\left(kn+k-n-1\right)!kn!} =\frac{\left(kn+k-n\right)\left(kn+k-n+1\right)\cdots\left(kn+k\right)}{\left(n+1\right)\left(kn-n+1\right)\cdots\left(kn-n\right)} $$ That I'm not really sure how to use.

So instead I tried finding something that I might be able to say is bigger and smaller to use squeeze on, which gave me: $${kn \choose n}=\frac{kn!}{n!\left(kn-n\right)!}=\frac{\left(kn-n+1\right)\cdots\left(kn\right)}{n!}\leq k^{n}\frac{n^{n}}{n!}$$ And then showing that $$ \frac{\frac{\left(n+1\right)^{n+1}}{\left(n+1\right)!}}{\frac{n^{n}}{n!}}=\frac{\left(n+1\right)^{n+1}n!}{n^{n}\left(n+1\right)!}=\frac{\left(n+1\right)^{n}\left(n+1\right)}{n^{n}\left(n+1\right)}=\left(1+\frac{1}{n}\right)^{n}\to\epsilon$$ gives the larger limit of

$$\sqrt[n]{{kn \choose n}}\leq\sqrt[n]{k^{n}\frac{n^{n}}{n!}}=\sqrt[n]{k^{n}}\sqrt[n]{\frac{n^{n}}{n!}}=k\cdot\sqrt[n]{\frac{n^{n}}{n!}}\to k\cdot e $$

But it's obviously not the limit itself since for i.e. $k=1$ the limit is 1 and $k=2$ the limit is 4.

So I'm pretty much stuck, any hints on how I might be able to solve it?

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

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

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