8
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Not quite sure about how you simplified the last step, will try it by hand and come back :P $\endgroup$ – Nescio Apr 1 '15 at 12:00
  • $\begingroup$ Got it! Thanks! $\endgroup$ – Nescio Apr 1 '15 at 12:23
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ unfortunately I am unable to follow most of proof 1, and in proof 2 I'm not sure how the lemma gives that $\lim \frac{(kn)!^{1/n}}{(kn)^k} = e^{-k}$, or how you did the algebra... $\endgroup$ – Nescio Apr 1 '15 at 11:59
1
$\begingroup$

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

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