I was reading up a statement in probability which said that
$nC_0 + nC_1 + nC_2 +\dots+ nCm$ is of order $n^m$
where $nCm$ is notation for number of combinations from a collection of $n$ taking $m$ at a time
How to prove this mathematically? If not possible how to logically reason it out?
It is not so close estimation. Must be better estimations of this sum, based on Stirling's approximation.
For this question: just to write $$ nC_0+nC_1+nC_2+\ldots+nC_m \\ = 1 + \dfrac{n}{1}+\dfrac{n(n-1)}{1\cdot 2} + \ldots + \dfrac{n(n-1)\cdots(n-m+1)}{1\cdot 2 \cdots \cdot m}\\ \le 1+\frac{n}{1!}+\frac{n^2}{2!}+\ldots +\dfrac{n^m}{m!} \\ \le \left(1+\dfrac{1}{1!}+\dfrac{1}{2!}+\ldots+\dfrac{1}{m!}\right)n^m \\ <e\cdot n^m, $$
where $e$ is the base of the natural logarithm (see here), $e\approx2.71828$.