Is binomial coefficient $\binom{n}{t}$ increasing in $t$

208 Views Asked by At

Let $t\geq \alpha n$ be an integer. I want to know whether there exists a nice lower bound for $\binom{n}{t}$. I know that the following is true

$\binom{n}{\alpha n} \geq \frac{1}{2\sqrt{n}}2^{h(\alpha)n}$, where $h(\alpha) = -\alpha\log{\alpha} - (1-\alpha)\log(1-\alpha)$ is the Binary entropy function . For a proof of this please see The exponential complexity of satisfiability problems .

1

There are 1 best solutions below

0
On

The binomial coefficient ${n \choose t}$ is not monotone in $t$, it increases when $t$ varies from $0$ to $\lfloor \frac{n}2\rfloor$, then we have

$${n \choose \lfloor \frac{n}2\rfloor} = {n \choose \lceil \frac{n}2\rceil},$$

and finally it decreases when $t$ varies from $\lceil \frac{n}2\rceil$ to $n$. More specifically, it is symmetric with ${n \choose t} = {n \choose n-t}$.

A proof of this symmetry follows immediately from the the definition

$${n \choose t} = \frac{n!}{t!(n-t)!},$$

and the monotonicity behavior also follows from this, using the recurrence relation

$${n \choose t+1} = {n \choose t} \frac{n-t}{t+1}.$$

So if $t=n$, then ${n \choose t}=1$ and this is the only lower bound you can have if you don't have additional restrictions on $t$ (from above).