Is there an asymptotic formula for an inverse function of the binomial coefficient?

Fix a positive integer $k$. Let $$f(n):= \frac{k!\binom{n}{k}}{n^k}$$ Then $\lim_{n\to \infty} f(n) = 1$. Hence $f(n) \ge 1-\epsilon$ for large $n$.

Define $n_0(\epsilon)$ as the least positive integer such that $n\ge n_0$ implies $f(n)\ge 1 -\epsilon$. Is there an asymptotic for $n_0(\epsilon)$ as $\epsilon\to 0$? A lower bound for $n_0(\epsilon)$ for fixed small $\epsilon$ would be useful too.

-
For fixed k, this is a rational function of n. The asymptotics for $n\to\infty$ is therefore quite straightforward. –  Michael Renardy Sep 27 '13 at 15:40
Yes, the asymptotic for $f(n)$ can be found. The difficulty is in finding an asymptotic for inverse function $n_0(\epsilon)$. –  Colin Tan Sep 27 '13 at 16:02
Why is this a difficulty? You expand f(n)-1 in powers of 1/n, and then you want to expand 1/n in powers of f(n)-1. This is what the inverse function theorem does for you. –  Michael Renardy Sep 27 '13 at 17:04
Michael, you are right. With Liviu's answer, I see that I can write down the Taylor expansion of $n_0(\epsilon)$. –  Colin Tan Sep 28 '13 at 11:37

The approximation coming from the normal approximation of the binomial distribution is $$k = \sqrt{-2n\ln(1-\epsilon)}.$$ To get more terms write $\Delta=-\ln(1-\epsilon)$, then by expanding $-\ln(1-i/n)$ as a Taylor series in $i$ and summing over $i=0\ldots k-1$, you get a series $$\Delta = 1/2\,{\frac {k\, ( k-1 ) }{n}}+1/12\,{\frac {k\, ( 2\, k-1) ( k-1 ) }{n^2}}+1/12\,{\frac {{k}^{2} ( k-1) ^{2}}{{n}^{3}}} + \cdots$$ which converges if $k=O(n^c)$ for $c<1$ (but is useless if $c$ is too close to 1). The dominant term for moderately small $k$ is $k^2/2n$. You can use a series reversion method to get more terms of the inverse. I think (without much checking) that $$k = \sqrt{2n\Delta} + \frac{3-2\Delta}{6} + \text{smaller terms},$$ and note that we are already running into the issue of $k$ being an integer.

-
Using your series for $\Delta$ is helpful. With that, I would be able to get an expression of $n$ in terms of $\Delta$ and $k$, which is my intended goal. –  Colin Tan Sep 28 '13 at 11:43

Following Vidit's idea, allow for $t=\frac{1}{n}$ to be real and positive. Then

$$f_k(n)=f_k(t)=\prod_{j=1}^k\Bigl(\, 1-(j-1)t\,\Bigr).$$

Then $\newcommand{\eps}{\varepsilon}$

$$\eps=\eps(t)= 1-f(t)$$

satisfies $\eps(0)=0$ and

$$\frac{d\eps}{dt}|_{t=0} =\sum_{j=1}^n (j-1)=\frac{k(k-1)}{2} \neq 0.$$

Thus $t\mapsto \eps(t)$ is strictly increasing for $t$ small and thus $t\mapsto \eps(t)$ is locally invertible near $t=0$. You are asking for its inverse

$$t=t(\eps)$$

or more precisely its Taylor expansion near $\eps=0$. This can be found by implicit differentiation from the equation

$$\eps =1-f((t) \Rightarrow 1 =-\frac{df}{ft}(0)\cdot \frac{dt}{d\eps}.$$

Hence

$$\frac{1}{n_0(\eps)}=t=\frac{2\eps}{k(k-1)}+O(\eps^2).$$

Hence

$$n_0(\eps)=\eps^{-1}\frac{k(k-1)}{2}\bigl( 1+O(\eps)\bigr).$$

-

Too long to fit in a comment and render all the math correctly... but why can't we just expand out $f_k(n)$ to $$f_k(n) = \frac{n!}{n^k(n-k)!} = \prod_{j=1}^{k}\left(1-\frac{j-1}{n}\right)$$ Since the terms in this product expansion are indexed in decreasing order, for any $k$ we immediately have, for instance: $$\left(1-\frac{k-1}{n}\right)^{k-1} \leq f_k(n) \leq \left(1-\frac{1}{n}\right)^{k-1}.$$ On the other hand, if we want to be more refined (as indicated by your comment), one can keep track of the product more carefully. Isolating the $n^{-1}$ terms gives us: $$f_k(n) = 1 - \left(\frac{1}{n}+\cdots + \frac{k-1}{n}\right) +\text{O}(n^{-2})$$ and of course the expression in parentheses is just $\frac{k(k-1)}{2n}$.

-
Thank you Vidit. Your computation gives a lower bound for $n_0(\epsilon)$. But this lower bound may not be sharp asymptotically in $\epsilon$. –  Colin Tan Sep 27 '13 at 16:53