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

[mxam]

I don't 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!

 

[SteamKing]

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.

 

[mxam]

[itex]((x^n-y^n)/x-y)=>\frac {x^1-y^1} {x-y}=>\frac {x-y} {x-y} OK [/itex]

Now, n= k

[itex]x^k-y^k = m(x-y) ; [/itex] where m is a positive integer.

Now, my question is n=k+1 where,

[itex]x^k+1+-y^k+1= ?[/itex]

I don´t understand the next step, i saw some explanations on internet but i don't understand ! Help me please. :s

 

[RUber]

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)$.

 

[SteamKing]

[itex]((x^n-y^n)/x-y)=>\frac {x^1-y^1} {x-y}=>\frac {x-y} {x-y} OK [/itex]

Now, n= k

[itex]x^k-y^k = m(x-y) ; [/itex] where m is a positive integer.

Now, my question is n=k+1 where,

[itex]x^k+1+-y^k+1= ?[/itex]

I don´t understand the next step, i saw some explanations on internet but i don't understand ! Help me please. :s

Your Latex skills have let you down here. You need to use curly brackets { } to collect the right terms in the exponents.

[itex]x^{k+1}-y^{k+1}= ?[/itex]

 

[ehild]

Do you know the expression for the sum of a geometric sequence ? See http://www.regentsprep.org/regents/math/algtrig/atp2/geoseq.htm

ehild

 

[Mark44]

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

So noted, and dealt with.

 

[HallsofIvy]

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 $$x^{k+ 1}- y^{k+1}$$ as $$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)$$

 

[GFauxPas]

Are you allowed to use polynomial long division?

 

[mxam]

Thanks for your answers. I saw a "clear" solution online, let me show you:

[itex]((x^n-y^n)/x-y)=>\frac {x^1-y^1} {x-y}=>\frac {x-y} {x-y} OK [/itex]

Now, n= k

[itex]x^k-y^k = m(x-y) ; [/itex] where m is a positive integer.

n=k+1

[itex]x^{k+1}-y^{k+1}[/itex]

[itex](x^1)(x^k)-(y^1)(y^k)[/itex]

[itex]x(x^k)-x(y^k)+x(y^k)-y(y^k)[/itex]

And later the solution. But I don't understand just 1 thing, why are using $x(y^k)$? . . . where the origin for it? . . .

I appreciated your time. This is a old homework of Algebra, but is exercise unresolved, and now, i want to know the real way to resolve it. . .

 

[Mark44]

Thanks for your answers. I saw a "clear" solution online, let me show you:

[itex]((x^n-y^n)/x-y)=>\frac {x^1-y^1} {x-y}=>\frac {x-y} {x-y} OK [/itex]

Now, n= k

[itex]x^k-y^k = m(x-y) ; [/itex] where m is a positive integer.

n=k+1

[itex]x^{k+1}-y^{k+1}[/itex]

[itex](x^1)(x^k)-(y^1)(y^k)[/itex]

[itex]x(x^k)-x(y^k)+x(y^k)-y(y^k)[/itex]

And later the solution. But I don't understand just 1 thing, why are using $x(y^k)$? . . . where the origin for it? . . .
I appreciated your time. This is a old homework of Algebra, but is exercise unresolved, and now, i want to know the real way to resolve it. . .

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 x¹ - y¹ is divisible by x - y. For step 2, it was not clear that you were assuming that x^k - y^k 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 x^k - y^k as a constant m times (x - y). You could write this as x^k - y^k = 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.

 

[ehild]

Thanks for your answers. I saw a "clear" solution online, let me show you:...x(x^k)−x(y^k)+x(y^k)−y(y^k) And later the solution. But I don't understand just 1 thing, why are using x(y^k)? . . . where the origin for it? . . .

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(x^k−y^k)-y^k(x-y).

ehild

 

[mxam]

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(x^k−y^k)-y^k(x-y).

ehild

Thanks. . . .