# Discrete Math problem

I believe this is an induction problem.

Let $a, b$ be positive integers with $a < b$. Prove that for any natural number $n$, $a^n < b^n$.

I feel I should start with a base case $n = 1$ which yields true since $a$ is already less than $b$.

Next I would implement the induction hypothesis, but I'm kinda shaky on what that is.

After that I would check the $n + 1$ case.

Could someone check and verify what I'm doing?

-
Minor point, post should be edited to make sure negatives are not allowed. For $-10\lt -2$, but $(-10)^2\gt (-2)^2$. –  André Nicolas Nov 28 '12 at 5:35

For $n\in\Bbb Z^+$ let $P(n)$ be the statement that $a^n<b^n$. You get the induction off the ground by showing that $P(1)$ is true; indeed that’s simply the original hypothesis, that $a<b$. The induction step is to show that if $P(n)$ is true for some positive integer $n$, then $P(n+1)$ is also true. Thus, your induction hypothesis is $P(n)$: $a^n<b^n$. From this assumption you want to prove $P(n+1)$, i.e., that $a^{n+1}<b^{n+1}$. You can do this in two steps. First multiply your induction hypothesis by $a$ to conclude that $a^{n+1}<ab^n$. Then multiply the inequality $a<b$ by $b^n$, and put the pieces together to get $a^{n+1}<b^{n+1}$.

-
Can I set a and b to equal some arbitrary integers and test the hypothesis? –  blutuu Nov 28 '12 at 5:39
@blutuu: You could, but it’s pointless. What you have to do is show that if $a<b$ and $a^n<b^n$, where $n$ is some positive integer, then $a^{n+1}<b^{n+1}$. The induction hypothesis is just that: a hypothesis, something that is assumed. You have no reason to test it. –  Brian M. Scott Nov 28 '12 at 5:49
Ok then. So do I just go ahead and "put the pieces together" to arrive at a^n+1 < b^n+1 or is there more to this? I assume that would prove that the induction hypothesis is true. –  blutuu Nov 28 '12 at 5:55
@blutuu: Yes, that’s all there is to it, and no, that does not in and of itself prove that the induction hypothesis is true. It appears to me that much of your problem is that you don’t understand the logic behind proof by induction. It goes like this. You prove $P(1)$, and you prove that $P(n)$ implies $P(n+1)$ for every positive integer $n$. The claim is that when you’ve done this, you’ve proved that $P(n)$ really is true for every $n\in\Bbb Z^+$. To see why, suppose that it isn’t; then there must be a smallest positive integer $m$ such that $P(m)$ is not true. Can $m=1$? No: we checked ... –  Brian M. Scott Nov 28 '12 at 5:59
... that $P(1)$ is true. But then $m>1$, so $m-1$ is a positive integer. And $m$ was the smallest ‘bad’ integer $-$ the smallest for which $P$ is false $-$ so $P(m-1)$ must be true. But in the induction step we proved that if $P$ holds for some pos. integer, like $m-1$, it also holds for the next larger pos. int., which in this case is $m$. That is, $P(m-1)$ is true, and that implies that $P(m)$ is true, contradicting the hypothesis that $P(m)$ is false. Thus, there can’t be a smallest ‘bad’ pos. int., and therefore there can’t be any ‘bad’ pos. int.: $P(n)$ must be true for all pos. ints. –  Brian M. Scott Nov 28 '12 at 6:02

You're off to a good start. For the inductive step, assume that $a^k < b^k$ for some $k \geq 1$.

Then, what can you conclude?

-
I think n = k + 1? Then we test to see if it holds, correct? –  blutuu Nov 28 '12 at 5:37
Note that $n$ is not involved in the inductive hypothesis. We want to show that if $a^k < b^k$, then $a^{k+1} < b^{k+1}$. The question is, how can you get there? –  JavaMan Nov 28 '12 at 5:39
Looking at Brian Scott's answer I would multiply both sides by a and then by b^n. I'm not sure about it on my own. –  blutuu Nov 28 '12 at 5:43