Bound on binomial coefficient

Dependencies:

1. Binomial Coefficient
2. Stirling's approximation (incomplete)

For $0<k\le n$, $${\left(\frac{n}{k}\right)}^k\le (\genfrac{}{}{0ex}{}{n}{k})\le {\left(\frac{ne}{k}\right)}^k$$

Proof

$$\frac{n-i}{k-i}=\frac{(n-k)+(k-i)}{k-i}=1+\frac{n-k}{k-i}\ge 1+\frac{n-k}{k}=\frac{n}{k}$$ $$(\genfrac{}{}{0ex}{}{n}{k})=\prod _{i=0}^{k-1}\frac{n-i}{k-i}\ge \prod _{i=0}^{k-1}\frac{n}{k}={\left(\frac{n}{k}\right)}^k$$

By Stirling's approximation, $$e^{k}k!\ge \sqrt{2\pi k}{k}^k\ge k^k$$ $$(\genfrac{}{}{0ex}{}{n}{k})\le \frac{n^k}{k!}\le {\left(\frac{ne}{k}\right)}^k$$

Dependency for: None

Info:

• Depth: 1
• Number of transitive dependencies: 2

Transitive dependencies:

1. Binomial Coefficient
2. Stirling's approximation (incomplete)