<s>[INST] 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
 [/INST] 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}$$
</s>