# Can someone show me why this factorization is true?

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

Can someone perhaps even use long division to show me how this factorization works? I honestly don't see anyway to "memorize this". I like to see some basic intuition behind this

-
Just multiply the expression out, the terms cancle – Ethan Dec 17 '12 at 0:46
Can you see the pattern better by generating a table using WolframAlpha - see this example? – Amzoti Dec 17 '12 at 0:49

It’s easier to verify that it multiplies back together correctly:

$$x\left(x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1}\right)=x^n+\color{red}{x^{n-1}y+\ldots+x^2y^{n-2}+xy^{n-1}}\;,\tag{1}$$

and

$$y\left(x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1}\right)=\color{red}{x^{n-1}y+x^{n-2}y^2+\ldots+xy^{n-1}}+y^n\;.\tag{2}$$

The two red blocks are identical, so when you subtract $(2)$ from $(1)$, all that remains is $x^n-y^n$.

Note that the identity has a very simple form in summation notation:

$$x^n-y^n=(x-y)\sum_{k=0}^{n-1}x^{n-1-k}y^k\;.$$

In each term the exponents of $x$ and $y$ sum to $n-1$, and there is a term for every possible pair of non-negative exponents with sum $n-1$. This observation may make it easier to remember.

That said, it is possible to do the long division. Here’s how it starts, enough to show the pattern:

$$\begin{array}{c|ll} &x^{n-1}&+&x^{n-2}y&+&x^{n-3}y^2&+&\dots&+&y^{n-1}\\ \hline x-y&x^n&&&&&&\dots&&&-&y^n\\ &x^n&-&x^{n-1}y\\ \hline &&&x^{n-1}y&&&&&&&-&y^n\\ &&&x^{n-1}y&-&x^{n-2}y^2\\ \hline &&&&&x^{n-2}y^2&&&&&-&y^n\\ &&&&&x^{n-2}y^2&-&x^{n-3}y^3\\ \hline &&&&&&&x^{n-3}y^3\\ &&&&&&\vdots\\ \hline &&&&&&&&&xy^{n-1}&-&y^n\\ &&&&&&&&&xy^{n-1}&-&y^n\\ \hline \end{array}$$

-
But that's working backwards no? – Hawk Dec 17 '12 at 0:54
Wonderful, I just did the exact same thing. Curiously, could you show the last term $y^n$? (is the last term added to $2y^n$? – Hawk Dec 17 '12 at 1:02
@sizz: Since there’s an easy way to remember the formula, all you really need is an easy way to check that the formula you’ve remembered is correct, and working backwards provides that. – Brian M. Scott Dec 17 '12 at 1:03
@sizz: It’s a bit difficult to format, but I’ll see what I can do. – Brian M. Scott Dec 17 '12 at 1:03
The reason I asked was because I got all the terms except the last one and it is supposed to be $y^{n-1}$. Yeah I was also pretty impressed with your formatting. Intuitively, I could've worked backards since i had seen the first few terms, but it's nice to see my mistake – Hawk Dec 17 '12 at 1:04

I don't know if you would allow this (If you don't allow it, then I can include a proof of the geometric sum formula).

$(x/y)^n-1=\sum_{k=0}^{n-1}(x/y)^k$ (Geometric sum)

Now multiply by $y^n$, to get:

$x^n-y^n=\sum_{k=0}^{n-1}x^ky^{n-k}$

-
Expand it out, I can't handle discrete – Hawk Dec 17 '12 at 0:55

Since you said above that you already believe that the result is true, that makes me think you really want to know how to come up with the result (if it had not been presented to you).

My answer would be: play with several examples!

That is, sharpen your pencil and get busy factoring out $x^n-y^n$ for $n=1,2,3,\dots$ using long division or any other tools at your disposal. Then look at the pattern formed by the coefficients as well as the powers of $x$ and $y$:

\begin{array}{c|c} n & x^n-y^n \\\hline 1 & x-y \\ 2 & (x-y) (x+y) \\ 3 & (x-y) \left(x^2+y x+y^2\right) \\ 4 & (x-y) \left(x^3+y x^2+y^2 x+y^3\right) \\ 5 & (x-y) \left(x^4+y x^3+y^2 x^2+y^3 x+y^4\right) \\ 6 & (x-y) \left(x^5+y x^4+y^2 x^3+y^3 x^2+y^4 x+y^5\right) \\ 7 & (x-y) \left(x^6+y x^5+y^2 x^4+y^3 x^3+y^4 x^2+y^5 x+y^6\right) \\ 8 & (x-y) \left(x^7+y x^6+y^2 x^5+y^3 x^4+y^4 x^3+y^5 x^2+y^6 x+y^7\right) \\ 9 & (x-y) \left(x^8+y x^7+y^2 x^6+y^3 x^5+y^4 x^4+y^5 x^3+y^6 x^2+y^7 x+y^8\right) \\ 10 & (x-y) \left(x^9+y x^8+y^2 x^7+y^3 x^6+y^4 x^5+y^5 x^4+y^6 x^3+y^7 x^2+y^8 x+y^9\right) \\ \end{array}

Hopefully this would lead you to conjecture that the formula you gave is indeed true for all $n$. Then to prove this, you would proceed by induction.

Hope that helps.

-

One reason the result looks difficult is because it seems to involve two variables.
But if you divide both sides by $y^n$, it can be rewritten as

\eqalign{\frac{x^n}{y^n} - 1 &= \left(\frac{x - y}{y}\right) \left( \frac{x^{n-1} + x^{n-2} y + \ldots + x y^{n-2} + y^{n-1}}{y^{n-1}}\right)\cr &= \left(\frac{x}{y} - 1 \right) \left(\frac{x^{n-1}}{y^{n-1}} + \frac{x^{n-2}}{y^{n-2}} + \ldots + \frac{x}{y} + 1 \right)} With $x/y = r$, this says $$r^n - 1 = (r - 1)(r^{n-1} + r^{n-2} + \ldots + r + 1)$$ Now $$r (r^{n-1} + r^{n-2} + \ldots + r + 1) = r^{n} + r^{n-1} + \ldots + r^2 + r$$ Subtract $1(r^{n-1} + \ldots + r + 1) = r^{n-1} + \ldots + r + 1$ and you see that the terms in $r, r^2, \ldots, r^{n-1}$ all cancel, leaving $$(r - 1)(r^{n-1} + r^{n-2} + \ldots + r + 1) = r^n - 1$$

-

You specifically asked about intuition, and I haven't seen this aspect mentioned:

$x^n-y^n$ is clearly zero when $x=y$, so the polynomial admits a factorization with $(x-y)$ as one of the factors, i.e. $$x^n-y^n=(x-y)P(x,y).$$ Then you can do long division to figure out $P(x,y)$ or just work it out by brute force. For instance, $P(x,y)$ must have a term $x^{n-1}$ in order to generate the $x^n$ term, and that introduces an undesirable $-yx^{n-1}$ which has to be canceled, leading to a term $+yx^{n-2}$ in $P(x,y)$. Do this for a few terms and you will quickly get the pattern.

-

I would recommend that you try this with induction. If you are not familiar with it, a statement is true for all $n\in\mathbb{N}$ if it is true for $n=1$ and if the truth of the statement for $n=i$ implies the truth of the statement for $n=i+1.$ This is called the inductive step. Clearly, for $n=1$, $$x-y=(x-y).$$ Now, if $$x^{i}-y^{i}=(x-y)(x^{i-1}+yx^{i-2}+\cdots+xy^{i-2}+y^{i-1}),$$ show that $$x^{i+1}-y^{i+1}=(x-y)(x^{i}+yx^{i-1}+\cdots+xy^{i-1}+y^{i}).$$ By working through this inductive proof, that should help with the intuition.

-
Induction shows me it is true. Well i already believe the equality holds. I am more interested in the building blocks, but as it stands the answer may be "pattern" from multiple values – Hawk Dec 17 '12 at 0:56

Cancelation: $$\begin{array}{cccccccccccccccc} x & (x^3 & + & x^2 y & + & xy^2 & + & y^3) \\ & & -y & (x^3 & + & x^2 y & + & xy^2 & + & y^3) \\[25pt] = & x^4 & + & x^3 y & + & x^2y^2 & + & xy^2 \\ & & - & x^3y & - & x^2y^2 & - & xy^2 & - & y^3 \\[25pt] = & x^4 & & & & & & & - & y^4 \end{array}$$

-