25 Appendix B. Some Useful Facts

25.1 B.1 Some Useful Inequalities

\(\)1 ≤a ≤b\(, we have \[ \binom {b}{a} \geq \left(\frac{b}{a}\right)^a. \] \)

\(\)n ≥1\(, we have \[ \sqrt{2\pi n}\left(\frac{n}{e}\right)^n e^{\lambda _1(n)} {\lt} n! {\lt} \sqrt{2\pi n}\left(\frac{n}{e}\right)^n e^{\lambda _2(n)}, \] where \[ \lambda _1(n) = \frac{1}{12n+1} \quad \text{and} \quad \lambda _2(n) = \frac{1}{12n}. \] \)

\(\)1 ≤a ≤b\(, we have \[ \binom {b}{a} \leq \left(\frac{eb}{a}\right)^a. \] \)

\(\)k ≥1\( and \)x ≥-1\(, we have \[ (1+x)^k \geq 1 + kx. \] \)

\(\)|x| ≤1\(, \[ \sqrt{1+x} \leq 1 + \frac{x}{2} - \frac{x^2}{16}. \] \)

\(\)x, y R^n\(, we have \[ |\langle x, y \rangle | \leq \| x\| _2 \cdot \| y\| _2. \] \)

25.2 B.2 Some Useful Identities and Bounds

\(\)a, b, c, d > 0\(. Then \)ba ≤dc\( if and only if \)aa+b ≤cc+d\(. \)

\(\)|x| < 1\(, \[ \ln (1+x) = x - \frac{x^2}{2} + \frac{x^3}{3} - \cdots . \] \)

\(\)0 ≤x < 1\(, we have \[ x - \frac{x^2}{2} \leq \ln (1+x) \leq x, \] and for \)0 ≤x ≤1/2\(, we have \[ -x - x^2 \leq \ln (1-x) \leq -x. \] \)

\(\)x ≤1/4\(, we have \[ 1 - 5x^2 \leq H(1/2 - x) \leq 1 - x^2, \] where \)H\( denotes the binary entropy function. \)