Return to Answer

This follows immediately from a theorem due to Hoeffding.

Indeed, rewrite the inequality in question as $$\binom nk\le\exp(-nH(k/n)),\tag{10}\label{10}$$ where $k\in\{0,\dots,n\}$ and $H(q):=q\ln q+(1-q)\ln(1-q)$. By symmetry, without loss of generality $$k\ge n/2.$$

Let $S:=\sum_1^n X_i$, where the $X_i$'s are independent Bernoulli random variables with parameter $1/2$. Then, using the trivial inequality $P(S=k)\le P(S\ge k)$ and Hoeffding's theorem, we have $$2^{-n}\binom nk=P(S=k)\le P(S\ge k) \\ \le\exp\Big(-n\Big[\frac kn\,\ln\frac{k/n}{1/2} +\Big(1-\frac kn\Big)\,\ln\frac{1-k/n}{1-1/2}\Big]\Big) \\ =2^{-n} \exp(-nH(k/n)).$$ So, we get \eqref{10}.

This follows immediately from a theorem due to Hoeffding.

Indeed, rewrite the inequality in question as $$\binom nk\le\exp(-nH(k/n)),\tag{10}\label{10}$$ where $k\in\{0,\dots,n\}$ and $H(q):=q\ln q+(1-q)\ln(1-q)$. By symmetry, without loss of generality $$k\ge n/2.$$

Let $S:=\sum_1^n X_i$, where the $X_i$'s are independent Bernoulli random variables with parameter $1/2$. Then, using the trivial inequality $P(S=k)\le P(S\ge k)$ and Hoeffding's theorem, we have $$2^{-n}\binom nk=P(S=k)\le P(S\ge k) \\ \le\exp\Big(-n\Big[\frac kn\,\ln\frac{k/n}{1/2} +\Big(1-\frac kn\Big)\,\ln\frac{1-k/n}{1-1/2}\Big]\Big) \\ =2^{-n} \exp(-nH(k/n)). \tag{20}\label{20}$$ So, we get \eqref{10}.

In fact, as seen from \eqref{20}, much stronger inequalities than \eqref{10} hold: $$\sum_{j=k}^n\binom nj\le\exp(-nH(k/n))\quad\text{if }k\ge n/2$$ and, equivalently, $$\sum_{j=0}^k\binom nj\le\exp(-nH(k/n))\quad\text{if }k\le n/2.$$

This follows immediately from a theorem due by Hoeffding.

Indeed, rewrite the inequality in question as $$\binom nk\le\exp(-nH(k/n)),\tag{10}\label{10}$$ where $k\in\{0,\dots,n\}$ and $H(q):=q\ln q+(1-q)\ln(1-q)$. By symmetry, without loss of generality $$k\ge n/2.$$

Let $S:=\sum_1^n X_i$, where the $X_i$'s are independent Bernoulli random variables with parameter $1/2$. Then, using the trivial inequality $P(S=k)\le P(S\ge k)$ and Hoeffding's theorem, we have $$2^{-n}\binom nk=P(S=k)\le P(S\ge k) \\ \le\exp\Big(-n\Big[\frac kn\,\ln\frac{k/n}{1/2} +\Big(1-\frac kn\Big)\,\ln\frac{1-k/n}{1-1/2}\Big]\Big) \\ =2^{-n} \exp(-nH(k/n)).$$ So, we get \eqref{10}.

This follows immediately from a theorem due to Hoeffding.

Indeed, rewrite the inequality in question as $$\binom nk\le\exp(-nH(k/n)),\tag{10}\label{10}$$ where $k\in\{0,\dots,n\}$ and $H(q):=q\ln q+(1-q)\ln(1-q)$. By symmetry, without loss of generality $$k\ge n/2.$$

Let $S:=\sum_1^n X_i$, where the $X_i$'s are independent Bernoulli random variables with parameter $1/2$. Then, using the trivial inequality $P(S=k)\le P(S\ge k)$ and Hoeffding's theorem, we have $$2^{-n}\binom nk=P(S=k)\le P(S\ge k) \\ \le\exp\Big(-n\Big[\frac kn\,\ln\frac{k/n}{1/2} +\Big(1-\frac kn\Big)\,\ln\frac{1-k/n}{1-1/2}\Big]\Big) \\ =2^{-n} \exp(-nH(k/n)).$$ So, we get \eqref{10}.

This follows immediately from a theorem due by Hoeffding.

This follows immediately from a theorem due by Hoeffding.

Indeed, rewrite the inequality in question as $$\binom nk\le\exp(-nH(k/n)),\tag{10}\label{10}$$ where $k\in\{0,\dots,n\}$ and $H(q):=q\ln q+(1-q)\ln(1-q)$. By symmetry, without loss of generality $$k\ge n/2.$$

Let $S:=\sum_1^n X_i$, where the $X_i$'s are independent Bernoulli random variables with parameter $1/2$. Then, using the trivial inequality $P(S=k)\le P(S\ge k)$ and Hoeffding's theorem, we have $$2^{-n}\binom nk=P(S=k)\le P(S\ge k) \\ \le\exp\Big(-n\Big[\frac kn\,\ln\frac{k/n}{1/2} +\Big(1-\frac kn\Big)\,\ln\frac{1-k/n}{1-1/2}\Big]\Big) \\ =2^{-n} \exp(-nH(k/n)).$$ So, we get \eqref{10}.