Prove by induction that $x^n-y^n$ is divisble by $x-y$ for $ n \ge 1 $

Question

I'm new to inductive proofs so I need some commentary on my proof since the book only gives a hint in the back. In "Discrete Mathematics with Applications" by Epp Third Edition in section 4.3 problem 13 states

For any integer $ n \ge 1, x^n - y^n$ is divisible by $(x - y)$ where x and y are any integers with $ x \ne y $

My Proof is as follows.

let $ Q(n) = x^n - y^n $

Then the base case is

$ Q(1) = x^1 - y^1 $

Now

$ Q(n + 1) = x^{n+1} - y^{n+1} = (x^n + y^n)(x-y)$

So now we can see $(x-y)$ is a factor and in turn divisible by $(x-y)$. I have just one hesitation. I didn't substitute from the inductive hypotheses. In every other inductive proof I've done this was a necessary step. My intuition on induction tells me that I have basically set up all of the dominoes but failed to knock down the first one (the substitution). Is this necessary for a valid proof or does this hold?

Answer 1

Your factorisation is incorrect. Use $x^{n+1}-y^{n+1}=x(x^n-y^n)+y^n(x-y)$.

Answer 2

Non-Inductive Proof (or so I thought).

---

Proof: Suppose there exists $z$ such that $$x^n-y^n = z(x-y).$$ This would imply that $z=\dfrac{x^n-y^n}{x-y}$. Now, here comes the trick: $$\frac{x^n-y^n}{x-y} = \frac{x^{n-1}(x-y)+yx^{n-1}-y^n}{x-y}=x^{n-1}+y\left(\frac{x^{n-1}-y^{n-1}}{x-y}\right).$$ Continuing in the same way, it follows that $$x^{n-1}+y\left(\frac{x^{n-1}-y^{n-1}}{x-y}\right)=x^{n-1}+yx^{n-2}+y\left(\frac{x^{n-2}-y^{n-2}}{x-y}\right)=\cdots$$ to which a pattern can be noticed, namely, $$z=\sum_{k=1}^nx^{n-k}y^{k-1}\tag*{$\bigcirc$}$$

---

I decided to not do an inductive proof in order to explore a different way of tackling this problem :)

Edit: Turns out, it is an inductive proof, but it just skips the base case and is differently worded than usual. Credit to @J.G. who pointed that out :)

Answer 3

Following the suggestion by J.G., for the induction step we assume true that

• $Q(n) = x^{n} - y^{n} = p_{n-1}(x)\cdot (x-y)$

were $p_{n-1}(x)$ is a polynomial of degree $n-1$ then

• $Q(n+1) = x^{n+1} - y^{n+1} = x\cdot(x^n-y^n)+y^n(x-y)=x\cdot\,\color{red}{p_{n-1}(x)\cdot(x-y)}+y^n(x-y)=p_n(x)\cdot(x-y)$