Approximation for $(1 - \frac{1}{x})^x$

According to this survey paper on Bloom Filters, we can do the following approximation

$$(1 - \frac{1}{m})^{kn} \approx e^{\frac{-kn}{m}}$$

which allegedly is a $O(\frac 1m)$ approximation. I am curious as to why this is so. I know that:

• $(1 - \frac{1}{x})^x$ eventually converges to $e^{-1}$ because of L'Hospital's rule.

• $(1 - \frac{1}{x})^x$ can be expressed as $e^{-1} \prod_{i=1}^{\infty} e^{\frac{-1}{(i+1)x^i}}$ using a Taylor expansion.

However, I don't see a clean way of showing that it is a $O(\frac 1m)$ approximation.

migrated from cs.stackexchange.comOct 18 '17 at 18:17

This question came from our site for students, researchers and practitioners of computer science.

We have: $$\left(1 - \frac{1}{x}\right)^x = e^{x\log\left(1-\frac{1}{x}\right)} = e^{x\left(-\frac{1}{x}-\frac{1}{2x^2}+o\left(\frac{1}{x^2}\right)\right)} = e^{\left(-{1}-\frac{1}{2x}+o\left(\frac{1}{x}\right)\right)}$$
by Taylor expansion of $\log(1-t)$ at $0$. Then by expanding the exponential : $$e^{\left(-\frac{1}{2x}+o\left(\frac{1}{x}\right)\right)} = 1-\frac{1}{2x}+o\left(\frac{1}{x}\right) + o\left(\frac{1}{x}\right) = 1+O(1/x)$$
So that plugging everything back: $$\left(1 - \frac{1}{x}\right)^x = e^{-1}(1+O(1/x)) = e^{-1}+O(1/x)$$
• If you have more terms in the bigO you can collapse them, for instance, $O(1/x^2)+O(1/x^3)$ is a $O(1/x^2)$. Doing the computations with an arbitrary long Taylor expansion should yield the same result in the end. If you're happy with this answer, please mark it as Solved! – user70925 Oct 18 '17 at 8:51
• Oh, wow, changing sign inside the brackets changes sign in power of $e$. – rus9384 Oct 18 '17 at 9:01