prove that x-y is a factor of x^n-y^n using mathematical induction

Hi fmunshi-ga,

A quick refresher of the Mathematical Induction Principle:

Let p(n) denote the statement involving the integer variable n. The
Principle of Mathematical Induction states:

If p(1) is true and, for some integer k >= 1 , p(k+1) is true whenever
p(k) is true then p(n) is true for all n >= 1.


Lets use this principle to prove that:
p(n):   (x-y) divides (x^n-y^n).


First we need to prove that p(1) is true.
p(1):   (x-y) divides (x^1-y^1)

This is elementary as (x^1-y^1)=(x-y) and any integer number can be
divided by itself.


We now need to prove that if p(k) is true for some integer k >= 1 then
p(k+1) is true as well.

So we need to prove that:

if
(x-y) divides (x^k-y^k)  for some integer k >= 1 
then
(x-y) divides (x^(k+1)-y^(k+1))


We can start by rewriting the right hand side of this expression:

x^(k+1)-y^(k+1) =  x^(k+1) - xy^(k+1) - y^(k+1) + xy^(k+1) =  x(x^k -
y^k)+y^k(x-y)


In other words, we now need to prove that

if
p(k):     (x-y) divides (x^k-y^k)  for some integer k >= 1 
then
p(k+1):   (x-y) divides x(x^k - y^k)+y^k(x-y)


Now, the hypotheses states that (x-y) divides (x^k-y^k) therefore
(x-y) divides x(x^k-y^k) and since (x-y) also divides y^k(x-y) we can
now state that (x-y) divides x(x^k - y^k)+y^k(x-y), given that the
hypothesis is true.


We now proved that:
p(1) is true
and 
for some integer k >= 1 , p(k+1) is true whenever p(k) is true

Using the Principle of Mathematical Induction we can now conclude that
p(n) is true, or (x-y) divides (x^n-y^n) for all n >= 1 (and for n=0,
since x^0-y^0=0).


Hope this helps,

If you need any further explanation, just let me know.

Kind regards,

rhansenne-ga.


Search terms used: "Mathematical Induction"

Links:

Google Search on Mathematical Induction:
://www.google.be/search?q=%22mathematical+induction%22

Understanding Mathematical Induction:
http://www.cc.gatech.edu/people/home/idris/AlgorithmsProject/ProofMethods/Induction/UnderstandingInduction.html

Mathematical Induction by Peter Suber
http://www.earlham.edu/~peters/courses/logsys/math-ind.htm

Mathematical Induction at California State University
http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html

Examples of Mathematical Induction at CSUSB:
http://www.math.csusb.edu/notes/proofs/pfnot/node10.html

Rhansenne-ga has given a fine answer, but I have a correction to the
expression used in the induction step.  It should perhaps have read:

"We can start by rewriting the right hand side of this expression: 
 
x^(k+1)-y^(k+1) =  x^(k+1) - xy^k - y^(k+1) + xy^k 
    =  x(x^k - y^k) + y^k(x-y)"

The change involves a couple of exponents of y, from k+1 to k, in the
first line of the equation.  Note that rhansenne is adding and
subtracting the same quantity to give this equality.

regards, mathtalk-ga