# How to solve equation involving binomial coefficient?

I'm reading this paper which says

Let $$d=d(n)$$ be the positive real number for which

$$\binom n d p^{\binom d 2} = 1$$

where $$0 < p \le 1$$, then

$$d(n) = 2 \log_bn - 2 \log_b (\log_b n) + 2 \log_b\left(\frac 1 2 e\right) + 1 + O(1) \\= 2\log_bn+ O( \log_b \log_b n)$$

where $$b = \frac 1 p$$.

As the authors skimmed the proof, I've completely no idea how they reached the conclusion.

• I suppose you could try to use stirling and then just plug in $d$ and see what happens? – Maximilian Janisch Jun 30 at 22:07
• @MaximilianJanisch what you said probably works, but I think OP might want a motivated proof. – mathworker21 Jul 1 at 0:34

Setting $$b=1/p$$, the equation can be written as

$$\frac{n!}{d!(n-d)!}=b^{d(d-1)/2}$$

or

$$\log_b\left[\frac{n!}{d!(n-d)!}\right]=\frac{d(d-1)}{2}$$

Applying the Stirling approximation, the LHS becomes

$$\log_b \left(\sqrt{\frac{n}{2\pi d(n-d)}} \frac{ n^n}{d^d(n-d)^{n-d}}\right)\\ =\left(n+\frac{1}{2}\right)\log_b n- \left(d+\frac{1}{2}\right)\log_b d-\left(n-d+\frac{1}{2}\right)\log_b(n-d)+O(1)$$

We can consider the expansion for $$n=\infty$$ of the term $$\log_b(n-d)$$, which is

$$\log_b n-\frac{d}{n\log b}+O(n^{-2})$$

Substituting we get

$${ d}\,{\log_b n} +\frac{d}{\log b} -\frac{d^2}{n \log b} -\left(d+\frac{1}{2}\right)\log_b d +O(1)$$

Since this quantity has to be equal to $$d(d-1)/2$$, grouping the terms according to $$d$$ we have

$$d^2\left(\frac{1}{2}+\frac{1}{n\log b }\right)-d\left(\log_b n+\frac{1}{2}+\frac{1}{\log b} \right) +\left(d+\frac{1}{2}\right)\log_b d =O(1)$$

From this equation, we get that, as $$n \rightarrow \infty$$, the main term of the asymptotic expansion of $$d$$ is $$2\log_b n$$.

To determine the successive term of the expansion, we can set $$d=2\log_b n +f(n)$$. Taking the last equation, dividing by $$d$$, and making the substitution we get

$$\bigg[2\log_b n+f(n)\bigg]\left(\frac{1}{2}+\frac{1}{n\log b }\right)- \left(\log_b n+\frac{1}{2}+\frac{1}{\log b } \right) +\left(1+\frac{1}{2[2\log_b n +f(n)]}\right) \\ \log_b \bigg[2\log_b n+f(n)\bigg] =O(1)$$

Taking into account that the order of $$f(n)$$ is lower than $$\log n$$, incorporating some terms into the $$O(1)$$ error, the last equation becomes

$$\frac{1}{2}\left[2\log_b n+{f(n)}\right]- \log_b n + \log_b [2\log_b n+f(n)] =O(1)$$

from which

$$f(n)=-2\log_b (\log_b n) +O(1)$$

To further go into the expansion, we can set

$$d=2\log_b n -2\log_b (\log_b n ) +g(n)$$

Proceding as above by making the substitution, taking into account that the order of $$g(n)$$ is $$O(1)$$, and incorporating some terms into a residual $$O(1)$$ term, we get

$$\frac{1}{2}\left[2\log_b n -2\log_b (\log_b n)+{g(n)}\right]\\- \log_b n - \frac{1}{2} -\frac{1}{\log b}+\log_b 2\\+ \log_b [\log_b n+2\log_b(\log_b n) +f(n)] =O(1)$$

from which

$$g(n)=1+ \frac{2}{\log b}-2 \left(\log_b 2 \right) +O(1)\\ = 1+ 2\log_b e +2 \left(\log_b \frac{1}{2}\right) +O(1) \\ =1+ 2\log_b \left(\frac{1}{2}e \right) +O(1)$$

• Nice answer. But the exponent in the OP's question is $d\choose2$, not $n\choose2$, which changes your starting equation. Maybe it's just a typo in your answer, though. – cjferes Jul 3 at 22:27
• Thank you for your note. I just edited my answer. – Anatoly Jul 3 at 22:32
• Thank you for the clear and understandable answer! – UmbQbify -Key20- Jul 4 at 10:57