Need help with this induction proof

  • Thread starter garyljc
  • Start date
  • #1
garyljc
103
0
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
maze
659
4
Watch out for negative signs
 
  • #3
uman
352
0
This is false. For example, x=-2, y=1, n=2
 
  • #4
CompuChip
Science Advisor
Homework Helper
4,306
49
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
Kurret
143
0
You may use the axiom that if x>y, then xz>yz, for any z>0
 
  • #6
garyljc
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
garyljc
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,306
49
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,847
969
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
garyljc
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,847
969
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
garyljc
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,306
49
Can you show us the full proof? Just to check that you haven't forgotten anything.
 
  • #14
garyljc
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
garyljc
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,306
49
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
garyljc
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
garyljc
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,847
969
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
The|M|onster
83
0
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
garyljc
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,847
969
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
garyljc
103
0
lol ...
but halls ... even for the 1st question
do i need to prove the axiom ?
 
  • #24
CompuChip
Science Advisor
Homework Helper
4,306
49
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
garyljc
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 ?
 
  • #26
garyljc
103
0
As noted before, have you already proved "if x< y and 0< a< b, then ax< by"?

is anyone here ?
help me
i've post the proof

halls , i was wondering if i should just print this "if x< y and 0< a< b, then ax< by" since it's rather trivial
it's a one line proof
 
  • #27
garyljc
103
0
Have you already proved that: it a< b and x< y, then ax< by?

this is very trivial
do we have to proof it ?
if so , how do we ?
 
  • #28
CompuChip
Science Advisor
Homework Helper
4,306
49
Well, how trivial it is depends on how precise you want to get. I could also say that what you want to prove is trivial and you don't need to prove it, but apparently you think otherwise :smile:
Currently, your proof is globally of the form:
"Suppose <induction hypothesis>, then <what we want to prove> is true so we have proven <what we want to prove>".

So you can assume this axiom (as said before)
If x<y, then xz<yz, for any z>0​
Note that on both sides you are multiplying by the same number. So the axiom does not say that:
If 0<x<y, then x^2<y^2​
because z would have to be equal to x and y at the same time. So first try to find the missing step(s) here.
 
  • #29
HallsofIvy
Science Advisor
Homework Helper
41,847
969
is anyone here ?
help me
i've post the proof

halls , i was wondering if i should just print this "if x< y and 0< a< b, then ax< by" since it's rather trivial
it's a one line proof

this is very trivial
do we have to proof it ?
if so , how do we ?

You've said twice now that it is "trivial" and once that it is "a one line proof". Why are you now asking HOW to prove it?

Actually, the statement, as given here, is NOT true. For example, if a= 1, b= 2, x= -3, y= -2 then x< y, 0<a< b but ax= -3, by= -4 so ax is NOT less than by. You need at least y> 0 also. In that case, since x< y and a> 0, ax< ay. Since a< b and y> 0, ay< by. From ax< ay< by, ax< by.
 

Suggested for: Need help with this induction proof

Replies
8
Views
2K
  • Last Post
Replies
4
Views
8K
  • Last Post
Replies
3
Views
844
  • Last Post
Replies
15
Views
3K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
791
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
8
Views
5K
Top