Prove by double induction on $m,n$ that $(m+1)^n>mn\,\forall m,n\ge0.$
Here is what I got so far.
Induction on $m$.
Base step: $m=0.\\
(0+1)^n>0n, \forall n\ge0.\\
(0+1)^n=1^n=1>0n=0, \forall n\ge0.$
Inductive step: $(m+1+1)^n>(m+1)n, \forall n\ge0.$
Induction on $n.$
Base step: $n=0\\
(m+1+1)^0\stackrel{m\ge0}=1>(m+1)0=0$
Inductive step: $(m+1+1)^{n+1}>(m+1)(n+1), \forall n\ge0.\\
(m+1+1)^{n+1}=(m+1+1)^n(m+1+1)\stackrel{\text{Inductive Hypothesis:}}>(m+1+1)^n>(m+1)n\\
>(m+1)n(m+1+1)$
I have not managed to go beyond that.
Any help will be appreciated.
Best Answer
Fix $m$. From the base case $n=0$, assume that $(m+1)^n>mn$ holds for some $n\in\Bbb N$. Then for the inductive step of $n+1$, we have $$(m+1)^{n+1}=(m+1)(m+1)^n>(m+1)mn>m(n+1)\impliedby m+1>1+\frac1n$$ which is true for all $m>0$. When $m=0$, we have $(0+1)^n>0\cdot n$ which is also true, so induction on $n$ is complete.
Fix $n$. From the bases case $m=0$, assume that $(m+1)^n>mn$ holds for some $m\in\Bbb N$. Then for the inductive step of $m+1$, we have \begin{align}(m+1+1)^n&=(m+1)^n+\binom n1(m+1)^{n-1}+\cdots+\binom n{n-1}(m+1)+1\\&>mn+n(m+1)^{n-1}+\cdots+n(m+1)+1\\&=(m+1)n+n(m+1)^{n-1}+\cdots+n+1>(m+1)n\end{align} which is true for all $n\ge0$. Induction on $m$ is complete, and the result follows.