You have a box with n marbles and we want to pick k out of it and we do not take the order of the marbles into account. For k fixed let m(n) denote the possible combinations of the marbles that we take out of the box , show that $m(n) \in \mathcal{O}(n^k)$
So isn't this the very definition of the binomial coefficent? so m(n)= ${n}\choose{k}$ and we have to show that ${n}\choose{k}$ $\leq c*n^k$
I know that ${\left(\frac{n}{k}\right)}^{k}$ $\leq$ ${n}\choose{k}$ $\leq {\left(\frac{en}{k}\right)}^{k}$
but how can I prove ${n}\choose{k}$ $\leq c*n^k$?
edit: I can use the fact that ${n}\choose{k}$ = $\frac{n!}{k!(n-k)!} = \frac{1* 2* \dots *(n-k)*\dots*n}{k!(n-k)!}$ = $\frac{(n-k+1) *\dots*n}{k!} \leq \frac{n^k}{k!} \leq n^k$
would this suffice?