Proof by Mathematical InductionDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/