# Direct proof that $\sum_{k=0}^m \binom{n}{k} \leq n^m$

Is there a short direct proof that $\sum_{k=0}^m \binom{n}{k} \leq n^m$ ? I can prove it by showing it is true for $m=2$ and then proving by induction. Is there a direct non-inductive proof?

-

The LHS is the cardinality of $A=\lbrace X \subseteq \lbrace 1,2,\ldots,n \rbrace \ | \ |X| \leq m\rbrace$.
The RHS is the cardinality of $B$, the set of all maps $\lbrace 1,2,\ldots,m \rbrace \to \lbrace 1,2,\ldots,n \rbrace$.
Consider the map $\phi : B \to A$, where $\phi(f)$ is simply the image of $f$, for any function $f$.
$\phi$ is obviously surjective, so $|B| \geq |A|$ and we are done.