Lesson 2

Proving that binomial coefficients increase when approaching the center is straightforward: \[\frac{\binom{n}{k}}{\binom{n}{k-1}}=\frac{n-k+1}{k}\ .\] The ratio is greater than one for \(k<(n+1)/2\), equal to one when \(n\) is odd and \(k=(n+1)/2\), and less than one for \(k>(n+1)/2\).

For \(1\le k\le n\), the following estimates for binomial coefficients are often useful: \[\left(\frac{n}{k}\right)^{k} \le \binom nk \le \frac{n^k}{k!}< \left(\frac{ne}{k}\right)^{k} \ .\] The first two inequalities follow from \(\frac{n}{k}\le \frac{n-i}{k-i}\) and \(n-i \le n\) for \(0 \le i < k \le n\): \[\left(\frac{n}{k}\right)^{k} \le \frac{n}{k}\cdot \frac{n-1}{k-1}\dotsb \frac{n-k+1}{1}=\binom{n}{k}\le \frac{n^k}{k!}\ .\] The last inequality is equivalent to \(e^{k} > k^{k}/k!\), which follows from the Taylor series for \(e^{x}\): \[e^{x} = \sum_{n=0}^{\infty}\frac{x^n}{n!}\ .\]