# Prove that $2^{mn}$ is always greater than or equal to $m^n$

I've been trying to prove the following inequality, but until now I've had problems coming up with a solution:

$$2^{mn} \ge m^n$$

$m$ and $n$ can assume any natural number.

I wasn't able to find any counterexample that would invalidate this inequality, so I am assuming that this statement is generally true, but of course this still has to be proven.

This is true for $m,n\in\mathbb{Z}_{\geq1}$.

Since $2^{mn}=(2^m)^n$ and $x^n$ is an increasing function on $x>0$, all that has to be shown is $2^m\geq m$ when $m\geq1$. This can be done via induction.

• $2^0\ge 0$ too. – Henning Makholm Jun 16 '15 at 22:24
• As an alternative to induction, Cantor's diagonal argument proves that $2^m\gt m.$ – bof Jun 16 '15 at 22:57

Let $A=\{1,2,...,n\}$ and $B=\{1,2,...,m\}.$ Then $m^n$ is the number of functions from $A$ to $B,$ while $2^{m \cdot n}$ is the number of relations from $A$ to $B$ (functions or not). And there's an injection from the set of functions to the set of relations.

Hint Suffices to show $2^m \ge m$ for all natural $m$. How about using Mathematical induction?

• Maybe you mean suffice to show $2^m \ge m.$ – coffeemath Jun 16 '15 at 21:46
• @coffeemath yes – gt6989b Jun 16 '15 at 21:46

Look at the function $f(x) = 2^x-x$.

$f'(x)=(2^x)(\log 2)- 1 > 0$ for $x \geq 1$. So $f$ is increasing. Now, $f(1) = 1$. Hence, $f(m) > 0$ for every natural number $m$.

More a comment than a solution, but it points to a more general result (one that I found independently and am pleased with):

In Prove that $n^k < 2^n$ for all large enough $n$, I showed that if $n$ and $k$ are integers and $k≥2$ and $n≥k^2+1$, then $2^n>n^k$.