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!

Prove that x^n-y^n is divisible by x-y

  1. Oct 12, 2014 #1
    I dont know how to prove by mathematical induction that x^n-y^n is divisible by x-y . . . Can you show me step by step? . . .Greetings!
     
  2. jcsd
  3. Oct 12, 2014 #2

    SteamKing

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    Sorry, but the rules of PF state clearly that you must make an attempt at solution.

    As to proofs by induction, start with n = 1, 2, 3, etc. and see if the resulting polynomial is divisible by x-y. If you don't run into a contradiction along the line, try making a general statement for any integer n.
     
  4. Oct 12, 2014 #3
    Code (Text):
    [itex]((x^n-y^n)/x-y)=>\frac {x^1-y^1} {x-y}=>\frac {x-y} {x-y} OK [/itex]
    Now, n= k
    Code (Text):
    [itex]x^k-y^k = m(x-y) ; [/itex] where m is a positive integer.
    Now, my question is n=k+1 where,
    Code (Text):
    [itex]x^k+1+-y^k+1= ?[/itex]
    I don´t understand the next step, i saw some explanations on internet but i dont understand ! Help me please. :s
     
  5. Oct 12, 2014 #4

    RUber

    User Avatar
    Homework Helper

    When you say "Divisible by" x-y, that means that (x-y) is a polynomial factor, not exactly that ##x^k - y^k = m(x-y)## where m is a positive integer, but that m is a polynomial.
    Note that ##x^2-y^2= (x-y)(x+y)## and ##(x^3 - y^3) = (x-y)(x^2 +xy +y^2) ##.
     
  6. Oct 13, 2014 #5

    SteamKing

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    Your Latex skills have let you down here. You need to use curly brackets { } to collect the right terms in the exponents.
    Code (Text):
    [itex]x^{k+1}-y^{k+1}= ?[/itex]
     
  7. Oct 13, 2014 #6

    ehild

    User Avatar
    Homework Helper
    Gold Member

  8. Oct 13, 2014 #7

    Mark44

    Staff: Mentor

    So noted, and dealt with.
     
  9. Oct 13, 2014 #8

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    I think that using the formula for the sum of a geometric sequence is the simplest way to do this but would NOT be a proof by induction.

    mxam, write [tex]x^{k+ 1}- y^{k+1}[/tex] as [tex]x(x^k)- y(y^k)= x(x^k)- (y(x^k)- y(x^k))- y(y^k)= x^k(x- y)+ y(x^k- y^k)[/tex]
     
  10. Oct 13, 2014 #9
    Are you allowed to use polynomial long division?
     
  11. Oct 13, 2014 #10
    Thanks for your answers. I saw a "clear" solution online, let me show you:

     
  12. Oct 13, 2014 #11

    Mark44

    Staff: Mentor

    There are three things you need to do in an induction proof:
    1. Show that the statement is true for some starting value of n, typically, but not always, n = 1.
    2. Assume that the statement is true for n = k. This is called the induction hypothesis.
    3. Using the induction hypothesis of step 2, show that the statement is true for n = k + 1.

    In your work shown above, you established step 1 by showing that x1 - y1 is divisible by x - y. For step 2, it was not clear that you were assuming that xk - yk is divisible by x - y. Also, you are throwing in a lot of symbols, such as => ("implies") that aren't appropriate here. You should be using = to connect expressions that have the same value.

    You didn't finish things by working through step 3. Another poster in this thread has already mentioned that you can't write xk - yk as a constant m times (x - y). You could write this as xk - yk = m(x)(x - y), where m(x) is a polynomial of degree k - 1.

    Finally, you don't need to wrap [ code ] tags around your [ itex ] tags.
     
  13. Oct 16, 2014 #12

    ehild

    User Avatar
    Homework Helper
    Gold Member

    It is always possible to add and subtract the same term to an expression. It is just a clever thing to do. You can arrange the expression so it is the sum of two terms, both divisible by x-y:
    x(xk−yk)-yk(x-y).

    ehild
     
  14. Oct 17, 2014 #13
    Thanks. . . .
     
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: Prove that x^n-y^n is divisible by x-y
  1. X^n - y^n proof (Replies: 10)

Loading...