# Tricky computations in graph theory proof

Let $0 < p < 1$ be a constant, and set $b = 1/p$. Let $0 < \epsilon < 1/2$. Given a natural number $r \ge 2$, let $n_r$ be the maximal natural number for which

$\binom{n_r}{r} p^{\binom{r}{2}} \le r^{-(1+\epsilon)}$

Also, let $n_{r}^{\prime}$ be the minimal natural number for which

$\binom{n_{r}^{\prime}}{r} p^{\binom{r}{2}} \ge r^{1+\epsilon}$

It is clear that $n_r < n_{r}^{\prime}$. After some computations, one get that

$$n_r = \frac{r}{e} b^{(r-1)/2} + o(rb^{r/2})$$ and similarly $$n_{r}^{\prime} = \frac{r}{e} b^{(r-1)/2} + o(rb^{r/2})$$

My question is, how do we get the following:

$$n_{r}^{\prime}-n_r < \frac{5 \log{r}}{2r} n_r$$

I don't know how can we obtain that inequality. Equivalently, we want

$$\frac{n_{r}^{\prime}}{n_r} < 1 + \log{r^{5/2r}}$$

As $n_r$ is maximal, it follows that $$\binom{n_r+1}{r} p^{\binom{r}{2}} > r^{-(1+\epsilon)}$$ As well, as $n_{r}^{\prime}$ is minimal, we see that $$\binom{n_{r}^{\prime} - 1}{r} p^{\binom{r}{2}} < r^{1+\epsilon}$$

Then, the quotient of these inequalities gives $$\frac{\frac{(n_r^{\prime}-1)^r}{r^r}}{\frac{(n_r+1)^r}{r!}} \le \frac{\binom{n_{r}^{\prime} - 1}{r}}{\binom{n_r+1}{r}} < r^{2(1+\epsilon)} \le r^{3}$$

So, by Stirling's approx.

$$\left(\frac{n_r^{\prime}-1}{n_r+1}\right)^r < \frac{r^r}{r!} r^{3} \sim \frac{e^r r^{5/2}}{\sqrt{2 \pi}} < e^r r^{5/2}$$

Then $\left(\frac{n_r^{\prime}-1}{n_r+1}\right) < e r^{5/2r}$, now taking logarithms:

$$\log{\left(\frac{n_r^{\prime}-1}{n_r+1}\right)} < 1 + \log{r^{5/2r}}$$

The RHS is the one we desire, however, I don't know how to fix the LHS to get what we need: $\frac{n_r^{\prime}}{n_r}$.