$$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
On
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}$
On
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.
On
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} $$
On
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.
On
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.
On
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$$
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}$$