# Induction Proof that $x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1}).$ [duplicate]

I seek an inductive proof that $$x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1}).$$ I am stuck.

• Welcome to Math SE. FYI, a quite similar question, but where it's restricted to have $y = 1$, is at Prove with induction that $\sum_{k=0}^{n-1}x^{k}=\frac{x^n-1}{x-1}$. Jun 8, 2020 at 19:42
• @PeterForeman On the contrary, there is a very simple inductive proof. (In a way, I agree with you, though, because it's just as simple to multiply the thing out, assuming, as we must in this case, that expressions containing ellipses "..." are allowed at all.) Jun 8, 2020 at 19:43
• The question is bound to be closed (rightly), unless some work is shown, and I had no intention of posting an answer, but surprisingly none of the answers to the question that has just been identified as a duplicate seems to mention the method that seemed so obvious to me (if induction must be used, which I agree seems to make little sense in this context): $x^{n+1} - y^{n+1} = x(x^n - y^n) + (x - y)y^n,$ etc. Even more surprisingly, all but one of the answers to the other question use division, even though the identity is valid in any commutative ring. OK, I'm sorry, I had to let off steam! Jun 8, 2020 at 21:06

I fail to see why induction is helpful let alone necessary; however, what is important is that the factor $$x^{n - 1} + x^{n - 2} y + \cdots + xy^{n - 2} + y^{n - 1}$$ only appears whenever $$n - 1 \geq 1,$$ i.e., $$n \geq 2.$$ Checking the case that $$n = 1$$ and $$n = 2$$ reveals that $$x^1 - y^1 = x - y$$ and $$x^2 - y^2 = (x - y)(x + y)$$ by the difference of squares.

Observe that these two cases would form the base cases for an inductive proof; however, assuming that $$n \geq 3,$$ one can prove the identity by basic algebraic manipulation.

Proof. Consider the quantity $$q = q(x, y) = (x - y)(x^n + x^{n - 1} y + \cdots + xy^{n - 1} + y^n).$$ By the distributive property, we have that \begin{align*} q &= x(x^n + x^{n - 1} y + \cdots + xy^{n - 1} + y^n) - y(x^n + x^{n - 1} y + \cdots + xy^{n - 1} + y^n) \\ \\ &= x^{n + 1} + x(x^{n - 1} y + x^{n - 2} y^2 + \cdots + xy^{n - 1} + y^n) - y^{n + 1} - y(x^n + x^{n - 1} y + \cdots + x^2y^{n - 2} + xy^{n - 1}) \\ \\ &= x^{n + 1} - y^{n + 1} + xy(x^{n - 1} + x^{n - 2} y \cdots + xy^{n - 2} + y^{n - 1}) - xy(x^{n - 1} + x^{n - 2} y + \cdots + xy^{n - 2} + y^{n - 1}) \\ \\ &= x^{n + 1} - y^{n + 1}, \end{align*} where the third equality holds by factoring $$y$$ and $$x$$ from the first and second terms, respectively. QED.

• That's absolutely all that's needed, I agree. Jun 8, 2020 at 21:10

The base case $$n = 2$$ is easy.

Assume for $$n \ge 2$$ that

$$\tag 1 x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1})$$

Then

$$\quad (x-y)(x^{n}+x^{n-1}y+\ldots+xy^{n-1}+y^{n}) =$$

$$\quad \quad \displaystyle (x-y)\;\bigr(x\, (x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1})+y^{n}\bigr) =$$

$$\quad \quad \displaystyle x\;\bigr[ (x-y) (x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1})\bigr]\;+(x-y)y^{n} =^{\text{by (1)}} \;$$

$$\quad \quad \displaystyle x\, (x^n-y^n)+(x-y)y^{n} = x^{n+1}-y^{n+1}$$

and the inductive step case has been proved.

Here is another (sketched) proof where you won't see any ellipses (or $$\Sigma\text{'s}$$ for that matter)...

We begin by using recursion to define a function $$F$$:

$$\quad F(1) = x + y$$

For $$n \ge 1$$

$$\quad F(n+1) = xF(n) + y^{n+1}$$

Exercise: Prove by induction that for all $$n \ge 1$$,

$$\quad x^{n+1} - y^{n+1} = (x-y)F(n)$$

• Doesn't that look a teensy bit like the method I sketched in my comment? Jun 8, 2020 at 23:58
• @CalumGilhooley All I did was try to figure out how to directly use $\text{(1)}$, and I approached it as a puzzle. So I used the 'I know nothing, figure out the puzzle' method. And from reading your comments I got rid of the division (want to make you happy). Jun 9, 2020 at 0:04
• @CalumGilhooley When working with the lhs I found it 'too tight' and tried the rhs. If I was more imaginative I would have come up with your method, attacking the lhs. Jun 9, 2020 at 0:09
• Making me happy is a lost cause, I think! This one question seems to have a weird way of winding me up, in several ways at once. I'm trying not to worry about it (especially as it's bound to be deleted). I'm off to bed now. Night-night! $\ddot\smile$ P.S. Initially I approached it in exactly the way you did. My comment was just the quickest way to sum up the idea. Jun 9, 2020 at 0:15