1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Inductive proof

  1. Dec 2, 2013 #1
    1. The problem statement, all variables and given/known data

    for reals x and y with x greater than y, prove that n*x^(n-1)(x-y)>=x^n-y^n for n>0.

    2. Relevant equations



    3. The attempt at a solution

    Let p(n) be that the statement is true for some n.
    base case: obviously follows

    inductive step: assume p(k) is true for some k.
    Look at (n+1)x^(n-1+1)(a-b) = (n*x^n+x^n)(x-y)
    = n*x*x^n - n*y*x^n+x*x^n-y*x^n

    I'm stuck here. I know there is a way to do it using the property (x^n-y^n) = (x-y)(some polynomial), but we were specifically asked not to use that and to do it by induction.
     
  2. jcsd
  3. Dec 2, 2013 #2
    You need to use ##x > y## at this point. Your first and third term can be simplified. Also, in the formal proof you need to show the base case and mention ##p(k+1)##. I also noticed a minor typo with the ##a-b##, but I'm sure that is all it was.

    Edit: You should change your ##n## variables to ##k## after introducing ##p(k)##.
     
  4. Dec 2, 2013 #3
    Yeah I'll show the base case and such details in the formal write up, it's really this step where I am stuck.

    So I simplified it to:

    k*x^(k+1)-k*y*x^k+x^(k+1)-y*x^k

    What am I supposed to do with x>y?
     
    Last edited: Dec 2, 2013
  5. Dec 2, 2013 #4
    Try to do a substitution using ##x > y## so that two terms cancel out and you create an inequality. i.e. either plug in ##x## for ##y## or vice versa for one of the terms. The step after that is similar.
     
  6. Dec 2, 2013 #5
    can we say

    k*x^(k+1)-k*y*x^k+x^(k+1)-y*x^k > k*x^(k+1)-k*y*x^k since x>y?
     
  7. Dec 2, 2013 #6
    Absolutely. You substituted in ##y## for one of the ##x## in the ##+x^{k+1}## term so the result is smaller than the original equation (because you were adding the term) and then they canceled. Can you do something similar for the next step?
     
  8. Dec 2, 2013 #7
    I don't see what to do here. If we take k*x^(k+1)-k*y*x^k and did the same thing wouldn't we just get zero?
     
  9. Dec 2, 2013 #8
    Depending on the substitution you do, yes, you could end up with 0. That's obviously not what you want though. The goal in this proof by induction is to end up with the inequality ##\geq x^{k+1} - y^{k+1}##. What substitution can you do to make it look like that? (You aren't done just yet, almost there!)
     
  10. Dec 2, 2013 #9
    I suspected I should substitute y into x in the second term of kx^(k+1)-ky*x^k, but wouldn't that not work since we would be subtracting a smaller number than before?
     
    Last edited: Dec 2, 2013
  11. Dec 3, 2013 #10
    never mind, I figured it out. thanks for all your help!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Inductive proof
  1. Proof by induction (Replies: 2)

  2. Proof by induction (Replies: 9)

  3. Proof by induction (Replies: 32)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)

Loading...