二項係数の上界・下界を与える4つの不等式

${}_n\mathrm{C}_k=\dfrac{n(n-1)(n-2)\cdots(n-k+1)}{k(k-1)(k-2)\cdots(k-k+1)}\\ =\dfrac{n}{k}\times\dfrac{n-1}{k-1}\times\dfrac{n-2}{k-2}\times\cdots\times\dfrac{n-k+1}{k-k+1}$

よって，$\dfrac{n-i}{k-i}\geqq\dfrac{n}{k}$ が $i=1,2,...,k-1$ に対して成立することを示せば十分。これは分母を払うと

$-ki\geqq -ni$ となり成立する。

${}_n\mathrm{C}_k=\dfrac{n(n-1)(n-2)\cdots(n-k+1)}{k!}\\\leqq\dfrac{n^k}{k!}$

である。目標の式と比較すると，あとは $\dfrac{1}{k!}\leqq\dfrac{e^k}{k^k}$ を示せばよい。これは階乗を近似するスターリングの公式（の粗いバージョン）： $$k!\fallingdotseq\left(\dfrac{k}{e}\right)^k$$ と似ている。そこで，スターリングの公式とその証明 の記事を見ると，記事末の左側の不等式より $$k!\geqq\left(\dfrac{k}{e}\right)^k$$ がわかる。

$nH\left(\dfrac{k}{n}\right)=-k\log_2\dfrac{k}{n}-(n-k)\log_2\left(1-\dfrac{k}{n}\right)\\ =-\log_2\left(\dfrac{k}{n}\right)^k\left(1-\dfrac{k}{n}\right)^{n-k}$

より，不等式の右辺は $\left\{\left(\dfrac{k}{n}\right)^k\left(1-\dfrac{k}{n}\right)^{n-k}\right\}^{-1}$ となる。

この形から二項定理を思いつきたい：

$1=\left\{\dfrac{k}{n}+\left(1-\dfrac{k}{n}\right)\right\}^n\\ \geqq{}_n\mathrm C_k\left(\dfrac{k}{n}\right)^k\left(1-\dfrac{k}{n}\right)^{n-k}$

（二項定理で展開したときの1つの項のみを取り出した）

両辺に $\left\{\left(\dfrac{k}{n}\right)^k\left(1-\dfrac{k}{n}\right)^{n-k}\right\}^{-1}$ をかけると目標の不等式を得る。

2つめの上界と同じように $H$ を計算すると，示すべき不等式は

$$\dfrac{1}{n+1}\leqq{}_n\mathrm C_k\left(\dfrac{k}{n}\right)^k\left(1-\dfrac{k}{n}\right)^{n-k}$$ である。一方，

$1=\left\{\dfrac{k}{n}+\left(1-\dfrac{k}{n}\right)\right\}^n\\=\displaystyle\sum_{t=0}^n{}_n\mathrm C_t\left(\dfrac{k}{n}\right)^t\left(1-\dfrac{k}{n}\right)^{n-t}$

であり，上記の不等式の右辺は $t=k$ の項から出てくる。ここで， $$\displaystyle\sum_{t=0}^n{}_n\mathrm C_t\left(\dfrac{k}{n}\right)^t\left(1-\dfrac{k}{n}\right)^{n-t}$$ は $n+1$ 項からなるが，実は $t=k$ の項が一番大きい（→補足）。つまり，この項は $\dfrac{1}{n+1}$ 以上である。