Lower bound on binomial coefficient

inequality binomial-coefficients information-theory

I encountered the following claim

$$\frac{1}{n+1}2^{nH_2(k/n)} \le \binom{n}{k} \le 2^{nH_2(k/n)}$$

where $H_2$ is the binary entropy function. The upper bound is rather well known but how does one show the lower bound?


Solution 1:

The lower bound is a rewriting of $\int_0^1 x^k (1-x)^{n-k} \leq 2^{-nH_2(k/n)}$, which is estimation of the integral by (maximum value of function integrated, which occurs at $x=\frac{k}{n}$) x (length of interval).

Related

When does a continuous map $f:X\rightarrow \mathbb{H}P^n$ lift to $S^{4n+3}$?
Show that $\int_0^1 \frac{\ln(1+x)}x\mathrm dx=-\frac12\int_0^1 \frac{\ln x}{1-x}\mathrm dx$ without actually evaluating both integrals
Squares in $(\operatorname{rad}(1)^2+1)\cdot(\operatorname{rad}(2)^2+1)\ldots(\operatorname{rad}(n)^2+1)$
convert ceil to floor
$S$ be a collection of subsets of $\{1,...,100\}$ ; any two sets in $S$ has non-empty intersection , what is the maximum possible value of $|S|$?
Connected open subsets in $\mathbb{R}^2$ are path connected.
On Ramanujan's approximation, $n!\sim \sqrt{\pi}\big(\frac ne\big)^n\sqrt [6]{(2n)^3+(2n)^2+n+\frac 1{30}}$
Books in foundations of mathematical logic
Create a number by multi by $2$ and divide by $3$ (integer part)
Why we wonder to know all derivations of an algebra?
Calculate Fourier series of $f(x)=x^2$ , $x \in \ [-\pi,\pi]$
Derivative of the Riemann zeta function for $Re(s)>0$.