Approximation of binomial coefficients

Question

Let us suppose I have this quantity: $$ 1- \left( 1-\frac{1}{M} \right) ^ k $$ In a pretty important dimostration I read, the author says that "for $k$ small compared to $M$, the quantity is approximately $\frac{k}{M}$." Now, since: $$ 1- \left( 1-\frac{1}{M} \right) ^ k = k \cdot \frac{1}{M} - \sum_{i=2}^k (-1)^i \binom{k}{i} \frac{1}{M^i} $$ and: $$ \big( \frac{k}{i} \big)^i \leq \binom{k}{i} \leq \frac{k^i}{i!} \big( 1- \frac{i}{2k} \big)^{i-1} \leq \frac{k^i}{i!} \big( \frac{1}{2} \big)^{i-1} $$ I can see it... but I would like to prove it!

How can I extimate the quantity $$ - \sum_{i=2}^k (-1)^i \binom{k}{i} \frac{1}{M^i} $$ in such a way that it is obvious that, for $k$ relatively small to $M$, this quantity is small?

Answer 1

Hint: for $M > 1$ and $i > 1$, $\frac{1}{M^i} \le \frac{1}{M^2}$. So, if you replace each $M^i$ in your sum by $M^2$, you will find that for fixed $k$, the sum is bounded above by a constant multiple of $\frac{1}{M^2}$.

Answer 2

$$\left(1-\frac{1}{M}\right)^k =\exp\left(k\log\left(1-\frac{1}{M}\right)\right)=\exp\left(-\frac{k}{M}+O\left(\frac{k^2}{M^2}\right)\right)$$ hence $$1-\left(1-\frac{1}{M}\right)^k = \frac{k}{M}\left(1-O\left(\frac{k}{M}\right)\right).$$