Use Induction to prove $\forall m,n \in \Bbb Z_{\ge 0}, 1 +mn \leq (1 + m)^n$                             Use Induction to prove: 

$$\forall m,n \in N, 1 +mn \leq (1 + m)^n$$
for integers $m,n\ge 0$.
My biggest problem with this proof is the fact that there's more than 1 variable I need to induct on. I'm doing this by simple induction so my idea is to show that:
$$1 + (m+1)(n+1) \leq (1 + m+ 1)^{n+1}$$
I'm not sure if this is the right way to approach this problem (if i'm even supposed to induct on both variables) since I've only done proofs dealing with a single variable. I was going to do 3 cases: m = n. m < n and m > n.
My proof attempt:
Base case: m = n 
I did m =0 and n =0 and it satisfied the inequality.
$1 + (m+1)(n+1) = 1 + mn + m + n + 1$
$1 +mn + m + n + 1 \leq (1+m)^n(1 +mn)$
Sad to say this is about as far as I could go. I have no idea how I can show that this works for $(m+1) and (n+1)$
Any help? thanks.
 A: This is known as Bernoulli's Inequality: for all $x\ge-1$ and non-negative integer $n$,
$$
(1+x)^n\ge1+nx
$$
This can be proven by induction:
Note that the inequality above is true for $n=0$.
Suppose that $x\ge-1$ and for a non-negative integer $n$, we have
$$
(1+x)^n-nx\ge1
$$
Then
$$
\begin{align}
(1+x)^{n+1}-(n+1)x
&=(1+x)^n-nx+x(1+x)^n-x\\
&\ge1+x((1+x)^n-1)\\
&\ge1
\end{align}
$$
If $-1\le x\le0$, then both $x$ and $(1+x)^n-1$ are negative. If $x\ge0$, then both both $x$ and $(1+x)^n-1$ are positive. Therefore, if $x\ge-1$, $x((1+x)^n-1)\ge0$. This justifies the last inequality above.
Note that if $x\ne0$ and $n\ge1$, the last inequality is strict. Thus, for $x\ne0$ and $n\ge2$, we have
$$
(1+x)^n\gt1+nx
$$
A: The trick is not to induct on $m$, just do the induction on $n$. You don't have to induct for both variables. Let $m\ge 0$ be arbitrary instead, then the base case $n=0$ is verified since $1+0=(1+m)^0$. Next assume we have proven this for some $n\ge 0$. Then
$$1+mn\le (1+m)^n$$
Multiply both sides by $(1+m)$ to get
$$1+mn+m+m^2n\le (1+m)^{n+1}$$
now we see that $m(n+1)=mn +m=m(n+1)\le m(n+1)+m^2n$ so that we can subtract off $m^2n$ and get
$$1+m(n+1)\le (1+mn)(1+m)\le (1+m)^{n+1}.$$
