Inverting binomial coefficients

Question

Given $x$ and $k$, I am interested in finding the number $n$ such that: \begin{align}\tag{1} \binom{n}{k} \leq x < \binom{n + 1}{k} \end{align} In particular, I'm interested in the case where $n \geq 1024$ and $k \leq 10$.

I have found an approximation formula for $n$ when $t$ is "small" in comparison to $n$, but I don't understand where how this approximation was obtained:

\begin{align} x = \binom{n}{t} \iff n = (k! x)^{1 / k} + \frac{k - 1}{2} + \frac{k^2 - 1}{24} \frac{1}{(k! x)^{1 / k}} + \mathcal{O}\left(\frac{1}{(k! x)^{3 / k}}\right) \end{align}

Since this approximation can be a non-integer value, I've had to manually check that of one $\lceil n \rceil$ or $\lfloor n \rfloor$ satisfies inequality $(1)$. Experimentally, this formula seems to hold, but I don't understand why. Can anyone steer me in the right direction?

Answer 1

We can try to find the $x$ that satisfies $$ x = \binom{n}{k} = \frac{\prod_{i=0}^{k-1} (n-i)}{k!} $$ this can be rewritten as $$ x k! = n^k \prod_{i=0}^{k-1} \left(1- \frac{i}{n} \right) $$ Since we know that $n \gg k$ the product in first order would be unity and hence we get as a first estimate that $$ x k! = n^k \Rightarrow n = ( x k! )^\frac{1}{k} $$ If we want to have a more accurate result, we can expand the following: $$ x k! = \prod_{i=0}^{k-1} (n-i) = n^k + \left( \sum_{0 \leq i_1 < k} (-i_1) \right) n^{k-1} + \left( \sum_{0 \leq i_1 < i_2 < k} (-i_1)(-i_2) \right) n^{k-2} + \cdots + (-1)^k (k-1)! $$ where we expanded the product and group all terms with the same power of $n$. The multiple sums that appear as the coefficients can be computed in different ways. For the case of large values of $n$, the first few terms give a very good estimate, which results in: $$ x k! \approx n^k - \frac{k(k-1)}{2}n^{k-1} + \frac{k(k-1)(k-2)(3k-1)}{24} n^{k-2} + {\cal O}(n^{k-3}) $$ If we write $y = (x k!)^\frac{1}{k}$ we can try to invert the above equation by making an expansion for $n$ in terms of $y$. Since $y$ itself is a large quantity the expansion has the form $$ n = y \left( 1 + \frac{a_1}{y} + \frac{a_2}{y^2} + \dots \right) $$ and we would like to solve the coefficients $a_i$. This can be done by inserting the expansion in the result for $x k!$. Now that results needs tone expanded in terms of inverse powers of $y$. That is a lot of work and I don't write here, but gives you something of the form $$ y^k = y^k + \left[ \dots \right] y^{k-1} + \left[ \dots \right] y^{k-2} + \dots $$ Since both sides have to be equal, each term $[\dots]$ gives an equation in the constants $a_i$ that successively can be solved. You will find that $$ a_1 = \frac{k-1}{2} $$ $$ a_2 = \frac{k^2-1}{24} $$