SOLUTION: Show that x - y is a factor of x^n - y^n for all positive integers n, using mathematical induction.
Algebra ->
Sequences-and-series
-> SOLUTION: Show that x - y is a factor of x^n - y^n for all positive integers n, using mathematical induction.
Log On
Question 1183950: Show that x - y is a factor of x^n - y^n for all positive integers n, using mathematical induction. Found 2 solutions by math_helper, robertb:Answer by math_helper(2461) (Show Source):
You can put this solution on YOUR website! Show that x - y is a factor of x^n - y^n for all positive integers n, using mathematical induction.
----------
NOTE: notatation "a | b" means "a divides b"
Base case: n=1: (x-y) | , base case holds
Hypothesis: assume (x-y) | (*) NOTE: k>1
Step case: let n=k+1:
RHS becomes
How do we apply (*)? By reworking this to something that has exponents less than or equal to k:
=
The left factor is of the form where (recall k>1) so we can apply (*) and say | ()
Since (x-y) divides one factor, it divides the entire product (if a|b then a|(bc)) .
Proof complete.
You can put this solution on YOUR website! Although for the most part the proof of the other tutor is correct, there is one part of the proof which is questionable,
and it is the part where it is indicated that
.
This is questionable since is NOT always an integer, and so induction does not apply in that case. The remedy is to use the inductive hypothesis directly.
Step 1. Check for n = 1: Obviously x - y divides x - y, so staement is true for n = 1.
Step 2. (Inductive hypothesis) Assume true for n = k, i.e., x - y divides .
Step 3. Prove that x - y divides .
Now .
Since x - y divides itself and by the inductive hypothesis x - y divides , it followes that x - y divides .
Therefore statement is true for , and the statement is PROVED.
