0
$\begingroup$

Suppose $n,k\to\infty$ such that $k/n^2\to a>0$. What is the limit of $\dfrac{{{k-1}\choose n}}{{{n+k-1}\choose n}}$?

Apparently there is a discrepancy between the correct answer $\exp(-1/a)$ and the answer I am getting after applying Stirling approximation. I wrote $$\dfrac{{{k-1}\choose n}}{{{n+k-1}\choose n}}=\dfrac{((k-1)!)^2}{(k-n-1)!(k+n-1)!}$$ Now applying Stirling formula to each factorial, taking $k$ and $n$ out wherever possible and using that $f(x)^{g(x)}\to \exp(\lim g(x)(f(x)-1))$, I find the limit is $\exp(-2/a)$ instead of $\exp(-1/a)$. Where am I going wrong?

Note we can apply Stirling because $k-n\to\infty$ since $k/n^2\to a$.

EDIT Let me write out my approach. I think I need to see why I went wrong. Let me replace $k-1$ by $k$ because $k/n^2\to a$ according to P. Quinton's suggestion in the comment. Then the quantity whose limit I wish to evaluate, is $\dfrac{(k!)^2}{(k-n)!(k+n)!}$.

We use the notation $f\sim g$ whenever $f/g\to1$. Applying Stirling formula, $$\dfrac{(k!)^2}{(k-n)!(k+n)!}\sim \dfrac{k^{2k+1}e^{-2k}}{(k-n)^{k-n+1/2}(k+n)^{k+n+1/2}e^{-2k}}$$ $$=\dfrac{k^{2k+1}}{k^{2k+1}(1-\frac{n}{k})^{k-n+1/2}(1+\frac{n}{k})^{k+n+1/2}}=(1-\frac{n}{k})^{n-k-1/2}(1+\frac{n}{k})^{-k-n-1/2}$$

Now I use $f(x)^{g(x)}\to e^{\lim g(x)(f(x)-1)}$ to get $$(1-\frac{n}{k})^{n-k-1/2}(1+\frac{n}{k})^{-k-n-1/2}\sim \exp(-\frac{n^2}{k}+n+\frac{n}{2k}-n-\frac{n^2}{k}-\frac{n}{2k})$$ $$=\exp(-\frac{2n^2}{k})\to e^{-\frac{2}{a}}$$

$\endgroup$
6
  • 1
    $\begingroup$ you can instead look at $k'=k-1$ with $k'/n^2\to a$. Stirling will be easier with $\frac{k'!^2}{(k'-n)!(k'+n)!}$ $\endgroup$
    – P. Quinton
    Mar 19, 2020 at 10:19
  • $\begingroup$ Thanks for the suggestion. I have added my approach to the question. Please check it if you can and if possible, please point out the error I am making. $\endgroup$ Mar 20, 2020 at 22:21
  • $\begingroup$ The error is when you use $f(x)^{g(x)}\to \dots$. I do not know this formula but you can rewrite the terms like this (forgetting the power $1/2$) $(1-\frac{n^2}{k}\frac{1}{n})^n (1+\frac{n^2}{k}\frac{1}{n})^{-n} (1-\frac{n^2}{k} \frac{1}{k})^{-k}$. The first two terms go to $e^{-1/a}$, the last to $e^{1/a}$, this gives you your result. $\endgroup$
    – P. Quinton
    Mar 21, 2020 at 9:03
  • $\begingroup$ I see, this makes sense. Thank you. $\endgroup$ Mar 22, 2020 at 4:54
  • $\begingroup$ any reference on this $f(x)^{g(x)}$ limit ? $\endgroup$
    – P. Quinton
    Mar 22, 2020 at 6:54

3 Answers 3

2
$\begingroup$

If you start letting $k=a n^2$ with $a >0$, the problem becomes simple just using Stirling approximations and continuing with Taylor series for large values of $n$.

In such a case (I hope that I am not totally wrong), you should get something like $$e^{-\frac 1a} \left( 1- \frac {3a+1 } { 6a^3n^2}+O \left(\frac 1{n^4}\right)\right)$$

$\endgroup$
4
  • $\begingroup$ Here's my question. Why do we have to use Taylor approximation? If you go on applying just Stirling you will get final answer to be $exp(-2/a)$. Let me see if I can write out my approach completely, and will notify you here. $\endgroup$ Mar 20, 2020 at 21:54
  • $\begingroup$ I have added my method to the question. Please check it. $\endgroup$ Mar 20, 2020 at 22:22
  • $\begingroup$ @LandonCarter. In my opinion, you use too late the fact that, for large $n$, $k\to an^2$. Nobody tells that $a=\epsilon$. But, I may be wrong. $\endgroup$ Mar 21, 2020 at 5:30
  • $\begingroup$ I don't think that's a problem. You can very well replace that last $\to$ by $\sim$ $\endgroup$ Mar 21, 2020 at 6:32
1
$\begingroup$

It turns out that your error is revealed in your comment:

I am not sure if it is entirely correct, just something I knew as a tool... but $f(x)^{g(x)}=\exp(g(x)\log(1+f(x)−1))$ and if $f(x)−1$ goes to $0$ then this quantity is like $\exp(g(x)(f(x)−1))$ since $\log(1+x)∼x$.

Do not use asymptotic equivalents without understanding exactly what they mean. See this post for the correct way to use asymptotic expansions. Specifically, $\ln(1+x) ∈ x + O(x^2) ⊆ x + o(x)$ as $x→0$, so $\exp(g(x)·\ln(f(x))) ∈ \exp(g(x)·(f(x)-1+o(f(x)-1)))$ as $f(x)-1 → 0$, and you cannot ignore the little-o term because it is multiplied by $g(x)$.

Note that correct asymptotic analysis can never result in incorrect answers, and will allow you to automatically know when you need to refine your asymptotic expansions. Here, for example, we can see that we need to refine the bound on the $\ln(f(x))$ until the error term multiplied by $g(x)$ goes to zero.

$\endgroup$
2
  • $\begingroup$ Thank you for the clarity. I shall follow this henceforth. $\endgroup$ May 13, 2020 at 21:42
  • $\begingroup$ @LandonCarter: You're welcome! If you have any questions about asymptotic expansion, feel free to ask in this chat-room. Also, if you think that my answer has addressed your question of where you went wrong, you can click on the tick to accept it. $\endgroup$
    – user21820
    May 14, 2020 at 5:44
0
$\begingroup$

Just a comment, after applying Stirling's approximation to

$$ y = \log \left(\frac{((k-1)!)^2}{(k-n-1)! (k-n+1)!}\right) , $$ I got $$ y = (-k+n+1) \log (k-n-1)+(-k+n-1) \log (k-n+1)+2 (k-1) \log (k-1)-2 n+2 . $$ After replacing $k$ by $a n^2$, I got $$ e^y = \frac{e^{2-2 n} (1-n (a n-1))^{-a n^2+n+1} (n (a n-1)+1)^{-a n^2+n-1} }{ \left(1-a n^2\right)^{2 -2 a n^2} }. $$ That is a $0/0$ situation. I applied a few L'Hoppitals and I gave up.

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