Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

Thanks for your help!

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.