Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Need help with this induction proof

  1. Jun 1, 2008 #1
    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. jcsd
  3. Jun 1, 2008 #2
    Watch out for negative signs
     
  4. Jun 1, 2008 #3
    This is false. For example, x=-2, y=1, n=2
     
  5. Jun 1, 2008 #4

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  6. Jun 1, 2008 #5
    You may use the axiom that if x>y, then xz>yz, for any z>0
     
  7. Jun 1, 2008 #6
    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 ?
     
  8. Jun 1, 2008 #7
    I'll just simplify it to become x^n.x < y^n.y
    is that it ?
     
  9. Jun 1, 2008 #8

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

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

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Have you already proved that: it a< b and x< y, then ax< by?
     
  11. Jun 2, 2008 #10
    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 ?
     
  12. Jun 2, 2008 #11

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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
  13. Jun 2, 2008 #12
    got it =)
    thanks
     
  14. Jun 2, 2008 #13

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    Can you show us the full proof? Just to check that you haven't forgotten anything.
     
  15. Jun 3, 2008 #14



    thanks halls i've got it now
     
  16. Jun 3, 2008 #15
    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 ?
     
  17. Jun 3, 2008 #16

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  18. Jun 4, 2008 #17
    so we must prove that not A then not B ?
     
  19. Jun 14, 2008 #18
    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 ?
     
  20. Jun 14, 2008 #19

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    As noted before, have you already proved "if x< y and 0< a< b, then ax< by"?
     
  21. Jun 14, 2008 #20
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Need help with this induction proof
  1. Need help with proof (Replies: 2)

  2. Help needed with a proof (Replies: 15)

Loading...