Upper Bound for Binomial Coefficient

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n, k \in \Z$ such that $n \ge k \ge 0$.

Then:

$\dbinom n k \le \left({\dfrac {n e} k}\right)^k$

where $\dbinom n k$ denotes a binomial coefficient.


Proof

From Lower and Upper Bound of Factorial, we have that:

$\dfrac {k^k} {e^{k - 1} } \le k!$

so that:

$(1): \quad \dfrac 1 {k!} \le \dfrac {e^{k - 1} } {k^k}$


Then:

\(\ds \dbinom n k\) \(=\) \(\ds \dfrac {n^\underline k} {k!}\) Definition of Binomial Coefficient
\(\ds \) \(\le\) \(\ds \dfrac {n^k} {k!}\)
\(\ds \) \(\le\) \(\ds \dfrac {n^k e^{k - 1} } {k^k}\) from $(1)$
\(\ds \) \(\le\) \(\ds \dfrac {n^k e^k} {k^k}\)

Hence the result.

$\blacksquare$


Sources