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?

```

```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search