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.

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}.$$