Dhrubajyoti Ghosh
Estimates used by the Probabilistic Method
Solving problems using the Probabilistic Method involves using various estimates. I have included some of them (mainly for self-reference) and their proofs.Result 1. \[ \binom{n}{k} \le \frac{n^k}{k!}. \]
Proof
Follows from the formula for \( \binom{n}{k} \).
Result 2. \[ \left( \frac{n}{k} \right)^k \le \binom{n}{k} \le \left( \frac{en}{k} \right)^k. \]
Proof
The first inequality is equivalent to \[ \left( 1 - \frac{1}{k} \right) \cdots \left( 1 - \frac{k - 1}{k} \right) \le \left( 1 - \frac{1}{n} \right) \cdots \left( 1 - \frac{k - 1}{n} \right). \] To get the second inequality, use Result 1 and \[ e^k = \sum_{i = 0}^{\infty} \frac{k^i}{i!} \ge \frac{k^k}{k!} \Rightarrow \frac{1}{k!} \le \left( \frac{e}{k} \right)^k.\]
Result 3. \[ \left( \frac{n}{e} \right)^n \le n! \le en\left( \frac{n}{e} \right)^n. \]
Proof
The first inequality was proved in Result 2. For the second inequality, consider \[ \sum_{i = 1}^{n - 1} \ln i \le \int_1^n \ln x \,dx. \]
Result 4. For all real \(x\), \[ 1 + x \le e^x. \]
Proof
Straightforward for \( x \le -1 \) and \( x \ge 0 \). Letting \( x = -t \) where \( 0 \lt t \lt 1 \), we need to prove \( 1 - t \le e^{-t} \). Now \[ e^t = 1 + t + \frac{t^2}{2!} + \cdots \lt 1 + t + t^2 + \cdots = \frac{1}{1 - t}, \] from which our claim follows.
Corollary 4.1. \[ (1 - p)^m \le e^{-mp}. \]
Corollary 4.2.
For \( 0 \le p \le \frac{1}{2} \),
\[ 1 - p \ge e^{-2p}. \]
Follows from
\[ 1 - p \ge \frac{1}{1 + 2p} \ge e^{-2p}. \]
Proof
Result 5.
I don't have a proof of this:
\[ \frac{2^{2m}}{2\sqrt{m}} \le \binom{2m}{m} \le \frac{2^{2m}}{\sqrt{2m}}. \]