How can you approximate $\sum_{i=0}^m \binom{n}{i}$?

Question

I am currently hearing a lecture about combinatorial optimization. I noticed that my professor often approximates $\binom{n}{m}$ by $n^m$ and I can understand why this can be done. Now I noticed that if he often approximates the expression $\sum_{i=0}^m \binom{n}{i}$ by $n^m$ as well, but I do not understand why this is true. Maybe he means $\sum_{i=0}^m \binom{n}{i}=O(n^m)$? But again I don't see why this holds. The best approximation I got so far is $\sum_{i=0}^m \binom{n}{i}\leq mn^m$.

Answer 1

Notice that since you approximate $\binom{n}{m}$ by $n^m$, in particular, we say that $\binom{n}{m}$ is $O(n^m)$. But in the similar fashion, $\binom{n}{m-1}$ is $O(n^{m-1})$ and so on. Thus you can approximate $$\sum_{i=0}^m \binom{n}{i}= O(1)+O(n)+O(n^2)+\dots + O(n^{m-1})+O(n^m) = O(n^m)$$