Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So I want to prove that for natural numbers $m,n,k$, if $k$ is no $0$ or $1$, and if $m<n$, then $k^m<k^n$. I jotted down the following proof, but I'm not sure how acceptable it is. I only have use of basic set theoretic properties of the naturals with addition, multiplication, and powers. I also have use of cancellation.

Let $$ K=\{k\in\omega\ |\ k^m<k^n\}. $$

Since $m<n$ there exists a $p^+\in\omega$ such that $m+p^+=n$. Consider $2$. I claim $2^{p^+}>1$. Now $p^+\neq 0$, since $0$ is not in the range of the successor. If $p^+=1$, then from the work above, $2^1=2>1$. Suppose then that $2^{p^+}>1$. Then $2^{p^{++}}=2^{p^+}\cdot 2>1$. This follows by transitivity since $1<2^{p^+}$, and $1<2$ implies $2^{p^+}\cdot 1<2^{p^+}\cdot 2$, that is $2^{p^+}<2^{p^{++}}$. Then from $1<2^{p^+}$ we have $2^m=2^m\cdot 1<2^m\cdot 2^{p^+}=2^{m+p^+}=2^n$, so $2\in K$. By the same reasoning we can show that any $k\neq 0,1$ is in $K$. If $k\neq 0,1$, then $1<k$. Again, I claim $k^{p^+}>1$. If $p^+=1$, we are done. So suppose $k^{p^+}>1$. Then since $1<k$, we have $k^{p^+}=k^{p^+}\cdot 1<k^{p^+}\cdot k=k^{p^{++}}$, so $1<k^{p^{++}}$ by transitivity, and so $k^{p^+}>1$ for all $p$, since $p^+\neq 0$. Then from $1<k^{p^+}$ we have $k^m\cdot 1<k^m\cdot k^{p^+}=k^{m+p^+}=k^n$, so $k\in K$, and the result follows.

All in all, this approach seems very ugly. Is there a way to clean it up? I wanted to use the time tested method of induction, but assuming $k^m<k^n$ seems to have little to do with showing $(k^+)^m<(k^+)^n$, since I don't know how to distribute powers. Thanks for any constructive criticism.

share|improve this question

3 Answers 3

up vote 1 down vote accepted

The idea is to show that for $k\geq2$ we have $k^{m^+}>k^m$. For that you need to show that $m\cdot k>m$ for $k\geq2$ and $m\geq1$. And to show that you need to show that $m+n>m$ for $n\geq1$.

Let's start with the last one, $m+n>m$ for $n\geq1$: We work with induction on $n$. For $n=1$ $m+n=m+1=m^+$. By the definition of the natural numbers you have $m\in m^+$ so it's true. Now assume that it's true for $n$. For $n^+$ we have $m+n^+=(m+n)^+$. Now $(m+n)<(m+n)^+$. By the induction hypothesis we have $m<m+n<(m+n)^+$.

Now let's show that $m\cdot k>m$ for $k\geq2$ and $m\geq1$ : We work with induction on $k$. For $k=2$ we have $m\cdot2=m\cdot1+m=m+m$. From the previous result (and since $m\geq1$) we have $m+m>m$ and thus $m\cdot2>m$. Assume that it's true for $k$. We have $m\cdot k^+=m\cdot k+m$. By the previous result $m\cdot k+m>m\cdot k$, By the induction hypothesis we have $m\cdot k>m$. Therefore $m\cdot k^+=m\cdot k+m>m\cdot k>m$ and we are done.

We can now show that $k\geq2$ we have $k^{m^+}>k^m$: We have $k^{m^+}=k^m\cdot k$. Since $k\geq2$ from the previous result we get $k^m\cdot k>k^m$ which is what we want.

Finalizing the proof let's show what you want by induction on $n$. If $n=0$ then the sentence is vacuously true. Assume that it's true for $n$. If $m<n^+$ then we have $m<n$ or $m=n$. Previously I showed that $k^n<k^{n^+}$. In case $m=n$ that suffices. In case $m<n$ by the induction hypothesis we have $k^m<k^n$. But $k^n<k^{n^+}$ and we are done.

share|improve this answer
    
Thanks Apostolos for spelling it out for me. I'm not too comfortable yet on choosing what to induct on when there are multiple variables. –  user8228 Mar 14 '11 at 10:21
    
@Bdubs: A usually (as in not always) helpful advice is to first try induction on the variables that appear at the rightmost of terms and after the $<$. This is because of the way arithmetic operations and the $<$ relation are defined. For example my reasoning here was to first perform induction on $n$. By trying that I figured out that the problem was reduced to showing $m<m\cdot k$, so I used induction on $k$ etc. –  Apostolos Mar 14 '11 at 10:50

I assume you have something like $k^0 = 1$, $ k^a \cdot k = k^{a^+}$, if $0<a$ and $1<b$ then $a < a \cdot b$, and the typical properties of order such as if $a<b$ and $b<c$ then $a<c$ and if $a<b$ and $b=c$ then $a<c$. In this case you also have $0 < 1 < k$.

First you want to show that $0 < k^m$. You have the initial step $0 < 1 = k^0$ (adjust this if instead you have $k^1 = k$) and the inductive step $0 < k^m < k^m \cdot k = k^{m^+}$.

Then for the main hypothesis you have the initial step $k^m < k^m \cdot k = k^{m^+}$ and the inductive step $k^m < k^n < k^n \cdot k = k^{n^+}$ for $m<n$.

share|improve this answer
    
Thanks Henry, I'm a little confused by which variable to induct on. Do I induct on $m$ and then $n$, and leave $k$ fixed? I guess my original approach treated $m$ and $n$ as fixed, and inducted on $k$. –  user8228 Mar 14 '11 at 9:08
    
I am sure it is easier to vary $m$ and then $n$ while leaving $k$ fixed, and I think you did so in your version. It is difficult to compare $k^a$ and $(k+1)^b$ until you have a lot more tools, such as binomial expansion or logarithms. –  Henry Mar 14 '11 at 10:24

I think for natural numbers since $k\ge 1$, $k^{n-m}$ should be greater than 1. Then it should be automatic.

share|improve this answer
3  
I'm working in the early stages of constructing that naturals with set theory, so I'm afraid that approach doesn't work. –  user8228 Mar 14 '11 at 8:32
    
You mean $k>1$, as $1^x=1$ for any number $x$. –  Asaf Karagila Mar 14 '11 at 9:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.