I'm new at writing proofs, and I'm stuck on this question. Can I use induction? I know that induction is often used for proofs involving positive integers.
Any help or insight would be greatly appreciated!
Thanks!
Any help or insight would be greatly appreciated!
Thanks!
-
Yes, induction can be used.
Solve for your base case n=1
x - y | x - y (where 4 | 8 means 8 is divisible by 4)
Assume for n=k
x - y | x^k - y^k
And prove for n = k+1
x - y | x^(k+1) - y^(k+1)
x - y | x^k * x - y^k * y
x - y | x(x^k) - x(y^k) + x(y^k) - y(y^k)
For the previous step, just add and subtract x(y^k).
x - y | x(x^k - y^k) + (x-y)(y^k)
Notice that x - y | x(x^k - y^k)
and also x - y | (x-y)(y^k)
So by using the Euclidean Algorithm we can conclude that x - y | x(x^k - y^k) + (x-y)(y^k)
And therefore x - y | x^(k+1) - y^(k+1), which completes the proof.
Solve for your base case n=1
x - y | x - y (where 4 | 8 means 8 is divisible by 4)
Assume for n=k
x - y | x^k - y^k
And prove for n = k+1
x - y | x^(k+1) - y^(k+1)
x - y | x^k * x - y^k * y
x - y | x(x^k) - x(y^k) + x(y^k) - y(y^k)
For the previous step, just add and subtract x(y^k).
x - y | x(x^k - y^k) + (x-y)(y^k)
Notice that x - y | x(x^k - y^k)
and also x - y | (x-y)(y^k)
So by using the Euclidean Algorithm we can conclude that x - y | x(x^k - y^k) + (x-y)(y^k)
And therefore x - y | x^(k+1) - y^(k+1), which completes the proof.