Need help with this induction proof

  • Thread starter garyljc
  • Start date
  • #1
103
0

Main Question or Discussion Point

Hi all,
I was doing Analysis when I came across with this problem
It reads that : Proof that if x<y , therefore x^n<y^n

Could anyone help me out with this ?
Thanks

Gary L
 

Answers and Replies

  • #2
655
3
Watch out for negative signs
 
  • #3
352
0
This is false. For example, x=-2, y=1, n=2
 
  • #4
CompuChip
Science Advisor
Homework Helper
4,302
47
So the main part of the proof is (note the extra assumptions I had to make, in bold):
Suppose that 0 < x < y, and we have an n integer such that x^n < y^n. Prove that x^(n + 1) < y^(n + 1).

Somehow, you will have to put the assumption in there again, and there is as far as I see only one obvious way to do it... how would you rewrite, for example, the left hand side of the inequality?
 
  • #5
144
0
You may use the axiom that if x>y, then xz>yz, for any z>0
 
  • #6
103
0
Should I state that in order for this to be true both x and y have to be positive ?

Or should I actually do it by case analysis , where by I consider both positive and negative ?
 
  • #7
103
0
So the main part of the proof is (note the extra assumptions I had to make, in bold):
Suppose that 0 < x < y, and we have an n integer such that x^n < y^n. Prove that x^(n + 1) < y^(n + 1).

Somehow, you will have to put the assumption in there again, and there is as far as I see only one obvious way to do it... how would you rewrite, for example, the left hand side of the inequality?
I'll just simplify it to become x^n.x < y^n.y
is that it ?
 
  • #8
CompuChip
Science Advisor
Homework Helper
4,302
47
Yes, you could do that (though it's more like the reverse of a simplification, as you're writing it in a more difficult way -- though more convenient in this case). But you haven't proven why that equation holds yet. Remember, all you know is that x < y and that x^n < y^n. Now try to combine that with the "simplification" to prove x^(n + 1) < y^(n + 1). Also look at Kurret's hint, it's quite useful.
 
  • #9
HallsofIvy
Science Advisor
Homework Helper
41,794
925
I'll just simplify it to become x^n.x < y^n.y
is that it ?
Have you already proved that: it a< b and x< y, then ax< by?
 
  • #10
103
0
Have you already proved that: if a< b and 0< x< y, then ax< by?
is this the first very step i have to do in order to proceed ?
correct me if i'm wrong , but without this step , does it mean this equation might not hold ?
 
  • #11
HallsofIvy
Science Advisor
Homework Helper
41,794
925
I assume that your induction step is "if xn< yn, then (xn)x< (yn)y so xn+1< yn+1". In order to go from the second to the third inequality, you have to know that "if a< b and 0< x< y, then ax< by" which is NOT exactly the same as the order axiom "if a< b and 0< x then ax< bx".

Of course, it's easy to prove that for all positive numbers which is true here:

If 0< a< b, and 0< x< y, then, first, ax< bx (multiplying both sides of a< b by the positive number x) and, second, bx< by (multiplying both sides of x< y by the positive number b). The result follows from transitivity.
 
Last edited by a moderator:
  • #12
103
0
Yes, you could do that (though it's more like the reverse of a simplification, as you're writing it in a more difficult way -- though more convenient in this case). But you haven't proven why that equation holds yet. Remember, all you know is that x < y and that x^n < y^n. Now try to combine that with the "simplification" to prove x^(n + 1) < y^(n + 1). Also look at Kurret's hint, it's quite useful.
got it =)
thanks
 
  • #13
CompuChip
Science Advisor
Homework Helper
4,302
47
Can you show us the full proof? Just to check that you haven't forgotten anything.
 
  • #14
103
0
I assume that your induction step is "if xn[/sub]< yn, then (xn)x< (yn)y so xn+1< yn+1". In order to go from the second to the third inequality, you have to know that "if a< b and 0< x< y, then ax< by" which is NOT exactly the same as the order axiom "if a< b and 0< x then ax< bx".

Of course, it's easy to prove that for all positive numbers which is true here:

If 0< a< b, and 0< x< y, then, first, ax< bx (multiplying both sides of a< b by the positive number x) and, second, bx< by (multiplying both sides of x< y by the positive number b). The result follows from transitivity.



thanks halls i've got it now
 
  • #15
103
0
Can you show us the full proof? Just to check that you haven't forgotten anything.
my steps are actually discussed throughout the thread ...


but now , i got another similar proof ... but it reads something like contra positive
whereby i have to proof this similar statement from the RHS instead of LHS
is there anything additional that i need to consider ?
 
  • #16
CompuChip
Science Advisor
Homework Helper
4,302
47
Yes, you should consider the way a contrapositive proof works. If the statement is: "If A, then B" then how would you prove this from the contrapositive.
 
  • #17
103
0
Yes, you should consider the way a contrapositive proof works. If the statement is: "If A, then B" then how would you prove this from the contrapositive.
so we must prove that not A then not B ?
 
  • #18
103
0
this is what i came up with for the first step
x<y , we want to prove that x^n<y^n
assuming x^n<y^n , x^(n+1)<y^(n+1) must be also true
0<x<y
therefore x^(n+1)<y^(n+1)
is x^n . x < y^n . y
and since x<y
therefore it is true for all values of n #

is that correct ?
 
  • #19
HallsofIvy
Science Advisor
Homework Helper
41,794
925
this is what i came up with for the first step
x<y , we want to prove that x^n<y^n
assuming x^n<y^n , x^(n+1)<y^(n+1) must be also true
0<x<y
therefore x^(n+1)<y^(n+1)
is x^n . x < y^n . y
and since x<y
therefore it is true for all values of n #

is that correct ?
As noted before, have you already proved "if x< y and 0< a< b, then ax< by"?
 
  • #20
so we must prove that not A then not B ?
If A => B is your original implication, then the contrapositive would be ~B => ~A. ~A => ~B would be the inverse of the original implication and the converse of the contrapositive.
 
  • #21
103
0
As noted before, have you already proved "if x< y and 0< a< b, then ax< by"?
halls i dont get it
but isn't that given by the question ?
 
  • #22
HallsofIvy
Science Advisor
Homework Helper
41,794
925
Sorry, I hadn't realized that you had introduced a completely new question:
"but now , i got another similar proof ... but it reads something like contra positive
whereby i have to proof this similar statement from the RHS instead of LHS
is there anything additional that i need to consider ? "

I thought you were still on the first question!

The contrapositive of "If A then B" is "If not B then not A" and is equivalent to the original statement- proving one proves the other.
 
  • #23
103
0
lol ...
but halls ... even for the 1st question
do i need to prove the axiom ?
 
  • #24
CompuChip
Science Advisor
Homework Helper
4,302
47
You call it an axiom, which is by definition something you don't prove.
But I wouldn't say it is an axiom, just a theorem. And I don't think that it is trivial (if it is, then the entire question is rather trivial as it immediately follows from the axiom). I think the following is an axiom,
If 0 < a < b then for any x > 0, a x < b x.​
Note how there is just an x on both sides of the inequality, whereas you want to prove that
If 0 < a < b then for any y > x > 0, a x < b y.​
 
  • #25
103
0
compu chip thanks for the advice
so could you take a look at what i've come up for the first proof
is it sufficient to proof it ?
 

Related Threads for: Need help with this induction proof

  • Last Post
Replies
4
Views
8K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
2K
Replies
3
Views
1K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
8
Views
3K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
3K
Top