0
$\begingroup$

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?

  • 1
    Minor point, post should be edited to make sure negatives are not allowed. For $-10\lt -2$, but $(-10)^2\gt (-2)^2$.2012-11-28

2 Answers 2

1

For $n\in\Bbb Z^+$ let $P(n)$ be the statement that $a^n. You get the induction off the ground by showing that $P(1)$ is true; indeed that’s simply the original hypothesis, that $a. 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. From this assumption you want to prove $P(n+1)$, i.e., that $a^{n+1}. You can do this in two steps. First multiply your induction hypothesis by $a$ to conclude that $a^{n+1}. Then multiply the inequality $a by $b^n$, and put the pieces together to get $a^{n+1}.

  • 0
    Can I set a and b to equal some arbitrary integers and test the hypothesis?2012-11-28
  • 0
    @blutuu: You could, but it’s pointless. What you have to do is show that if $a and $a^n, where $n$ is some positive integer, then $a^{n+1}. The induction hypothesis is just that: a **hypothesis**, something that is assumed. You have no reason to test it.2012-11-28
  • 0
    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.2012-11-28
  • 0
    @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 ...2012-11-28
  • 0
    ... 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.2012-11-28
  • 0
    Ok that clears this up for me. For the last part of the induction I end up with a^n+1 < ab^n and ab^n < b^n+1. I'm no stuck on how to relate those two inequalities.2012-11-28
  • 0
    @blutuu: The relation $<$ is transitive: if $x and $y, then $x. You have $a^{n+1}, so ... ?2012-11-28
  • 0
    Oh yeah, of course! Ok I understand that now. Thanks for clearing that up.2012-11-28
  • 0
    @blutuu: You’re welcome; I’m glad it clicked.2012-11-28
1

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?

  • 0
    I think n = k + 1? Then we test to see if it holds, correct?2012-11-28
  • 0
    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?2012-11-28
  • 0
    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.2012-11-28