find condition on $a(n)$ such that the $\lim_{n\rightarrow\infty}\frac{a(n)\cdot (n-a(n))}{\log\binom{n}{a(n)}}=+\infty$

80 Views Asked by At

I met the following problem in my research but I don't know how to deal with it:

What is the condition on $a(n)$ such that $$\lim_{n\rightarrow\infty}\frac{a(n)\cdot (n-a(n))}{\log\binom{n}{a(n)}}=+\infty$$

note that $a$ can be (no neccessary) function on $n$ thus $\binom{n}{a}$ is $\binom{n}{a(n)}$

Example. If $a(n)=n/2$ then this condition is satisfied.

1

There are 1 best solutions below

3
On

Let $s=1/n$ and $r = a/n = a \cdot s $

We have (see) the bound

$$\frac{1}{a \cdot(n-a) }\log \binom{n}{a} \le \frac{n}{a \cdot (n-a) } H(r)= s \frac{H(r)}{r \cdot (1-r)} \tag 1$$

where $H(r)= -r \log r -(1-r)\log (1-r)$ is the binary entropy function. The bound is quite tight (we might add the corresponding lower bound to make it more complete).

We want $(1)$ to tend to zero as $s \to 0$.

Let's assume $r$ has some limit.

If $r$ tends to some value inside $(0,1)$, then we are done.

If $r \to 0$, then the RHS of $(1)$ tends to

$$ - s \log (r) = -s \log s - s \log a$$

Hence, it's enough to assume $a\ge 1$, and we are also done.

If $r \to 1$ , then the RHS of $(1)$ tends to

$$ - s \log (1-r) = -s \log(1- a s) $$

Again, it's enough to prescribe

$$ a \le n-1 \implies 1-r \ge s $$

Hence, it seems the desired limit is verified practically always. All we are requiring is $0<a<n$ and that $a/n$ has some limit (but I guess this also can be relaxed).