Need help with this induction proof

1. Jun 1, 2008

garyljc

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

2. Jun 1, 2008

maze

Watch out for negative signs

3. Jun 1, 2008

uman

This is false. For example, x=-2, y=1, n=2

4. Jun 1, 2008

CompuChip

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. Jun 1, 2008

Kurret

You may use the axiom that if x>y, then xz>yz, for any z>0

6. Jun 1, 2008

garyljc

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. Jun 1, 2008

garyljc

I'll just simplify it to become x^n.x < y^n.y
is that it ?

8. Jun 1, 2008

CompuChip

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. Jun 1, 2008

HallsofIvy

Staff Emeritus
Have you already proved that: it a< b and x< y, then ax< by?

10. Jun 2, 2008

garyljc

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. Jun 2, 2008

HallsofIvy

Staff Emeritus
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: Jun 15, 2008
12. Jun 2, 2008

garyljc

got it =)
thanks

13. Jun 2, 2008

CompuChip

Can you show us the full proof? Just to check that you haven't forgotten anything.

14. Jun 3, 2008

garyljc

thanks halls i've got it now

15. Jun 3, 2008

garyljc

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. Jun 3, 2008

CompuChip

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. Jun 4, 2008

garyljc

so we must prove that not A then not B ?

18. Jun 14, 2008

garyljc

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. Jun 14, 2008

HallsofIvy

Staff Emeritus
As noted before, have you already proved "if x< y and 0< a< b, then ax< by"?

20. Jun 14, 2008

The|M|onster

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.