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

Question

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.

Answer 1

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.

Answer 2

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