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

Question

                            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.

Answer 1

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

Answer 2

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