Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Proof by Mathematical Induction


Date: 09/24/1999 at 23:29:30
From: James
Subject: A question on mathematical induction

I must prove the following statement by mathematical induction: For 
any integer n greater than or equal to 1, x^n - y^n is divisible by 
x-y where x and y are any integers with x not equal to y.

I am confused as to how to approach this problem. Reading the examples 
in my textbook have not helped explain divisibility. Can you shed some 
light on this and get me going in the right direction?

Thank you for your help.


Date: 10/12/1999 at 14:23:28
From: Doctor Marykim
Subject: Re: A question on mathematical induction

Hi James,

Since you are not familiar with divisibility proofs by induction, I 
will begin with a simple example. The main point to note with 
divisibility induction is that the objective is to get a common factor 
of the divisor out of the expression.

As you know, induction is a three-step proof:

Prove 4^n + 14 is divisible by 6

Step 1. When n = 1:

      4 + 14 = 18 = 6 * 3

Therefore true for n = 1, the basis for induction.

Step 2. Assume true for n = k

     i.e.: 4^k + 14 = 6 * A, where A is a positive integer.

Rearranging this we get: 4^k = 6A - 14

Now consider n = k+1:

     4^(k+1) + 14 = 4*(4^k) + 14
                  = 4(6A-14) + 14    (from out assumption)
                  = 24A - 56 + 14
                  = 24A - 42
                  = 6(4A-7)

Therefore, if true for n = k, then true for n = k+1 

Step 3.
However, the statement was proved true for n = 1 (Step 1)
So the statement is true for n = 1+1 = 2 (step 2)
Thus the statement is true for n = 2+1, 3+1, ... (iterating step 2)
Therefore the statement is true for all positive integral n

Now back to your original question:

Prove (x^n) - (y^n) is divisible by x - y

Step 1. This is a trivial step, so I'll leave it up to you.

Step 2. Assume true for n = k, i.e.: x^k - y^k = (x-y)A, where A is a 
positive integer. If you follow the same steps as in the example 
above, you should be able to get a common factor of x-y in your final 
expression.

Step 3. This will be exactly the same as in the other example.

If you need any more help, feel free to write back.

- Doctor Marykim, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
High School Discrete Mathematics
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/