## Thursday, January 31, 2008

### Some useful mathematical formulae

• $e^a \geq 1+a$

• 1/(1+x) = 1 + O(x) when x is small.

• ${n\choose an} = O((\frac{1}{a^a (1-a)^{(1-a)}})^n)$, where $a\in (0,1)$.

• If $T(1) = 1$ and $T(n) = 2^nT(n/2)$, then $T(n) = 4^n$.
• ${n\choose k}\leq 2^{n\cdot H(k/n)}$, where $H(p) = -p\log p - (1-p)\log (1-p).$
• $\left(\frac{n}{k}\right)^k\leq {{n\choose k}}\leq\frac{n^k}{k!}\leq\left(\frac{n\cdot e}{k}\right)^k.$