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

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?

• Your last equality is false. $(x^n+y^n)(x-y)=x^{n+1}+xy^n-x^ny-y^{n+1}$ May 19 '18 at 6:14
• In your base case, you need to take out "$= 1 - 1 = 0 = 8(0)$". Your TA will take out partial credits when he sees it. May 19 '18 at 6:33
• @scaaahu I'm not in school. I just do math because I want to understand Donald Knuth. But just out of curiosity why would they do that? Edit: Wait no. I see it. May 19 '18 at 6:37
• What do you mean by "why would they do that?" do what? May 19 '18 at 6:40
• @scaaahu Why would they mark me off. But never mind I see the error now. May 19 '18 at 6:45

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

• So if I'm understanding you correctly the substitution happens inside the term $x(x^n - y^n)$ which would be $x(x-y) + y^n(x-y)$ ? Then I could proceed to factor or am I missing a factoring technique in my tool belt? May 19 '18 at 6:26
• You do indeed use the inductive step to verify $x-y|x^n-y^n$, although the expression you wrote after that isn't right.
– J.G.
May 19 '18 at 7:17

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 :)

• That's still induction.
– J.G.
May 19 '18 at 8:05
• @J.G. what do you mean? I have not used a base case, inductive hypothesis, or an inductive step. I just cleverly rewrote the numerator. May 19 '18 at 8:08
• "It terminates like this" is your inductive hypothesis.
– J.G.
May 19 '18 at 8:11
• @J.G. hah... I didn't realise. Looks like it is an inductive proof. Is there a way of proving the assertion with-out the use of induction, do you know? May 19 '18 at 8:13
• I don't think so. I'm sure someone would suggest "use the factor theorem", but the proof of that probably requires induction on the degree of polynomials. My favourite on-SE discussion of what constitutes induction is math.stackexchange.com/a/1359020
– J.G.
May 19 '18 at 8:20

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)$
• I don't quite follow the notation you are using. Epp simply uses the variable r when using the inductive hypotheses for divisibility. Would this also be valid if? so then I think I proved it successfully on paper just before I logged on today. $xr(x-y) + y^n(x-y) = (xr+y^n)(x-y)$ May 19 '18 at 22:01
• Also Epp states that r is an integer. Sorry. May 19 '18 at 22:08
• @PossiblyDakota $p_{n-1}(x)$ and $p_n(x)$ are just polynomials of degree $n−1$ and $n$ in $x$ and $y$ thus they can be also indicated as some integer $r_1$ and $r_2$. It is a minor issue in the proof.
– user
May 19 '18 at 22:08