Derivation of factorization of $a^n-b^n$ How does one prove that:
$$a^n-b^n=(a-b)\left(a^{n-1}+a^{n-2}b+a^{n-3}b^2+\dots+a^2b^{n-3}+ab^{n-2}+b^{n-1}\right)$$
Better yet, why is $a^n-b^n$ divisible by $a-b$? I would very much appreciate some help on this. Thanks
 A: See what happens when you multiply the second factor with the first one. When you multiply it by $a$ make not of all terms except $a^n$. Then multiply the second factor by $(-b)$. You will not that every element except the last one($b^n$) cancels out. This is why the result is true. 
For the divisibility problem you also need the condition that $a, b \in \Bbb Z$. By definition $r$ divides $s$ iff $s  = kr$ for some integer $k$. As long as $a$ and $b$ are integers the second factor too is an integer and we have that $(a - b)$ times another integer is equal to $a^n - b^n$ and hence divisibility follows. 
Hope I helped. 
A: As to "why" $a - b$ divides $a^n - b^n$, here's one attempt to "convince" you. Let $c = a - b$. Then $$a - b \mid a^n - b^n \iff c \mid (b + c)^n - b^n.$$
Expanding $(b + c)^n$ we get
$$(b + c)^n = b^n + \binom{n}{1} b^{n-1} \color{red}{c} + \binom{n}{2} b^{n-2} \color{red}{c^2} + \dots + \binom{n}{n-1} b \color{red}{c^{n-1}} + \color{red}{c^n}.$$
Since all terms are divisible by $c$, except for possibly the first one (which is cancelled by $-b^n$), it follows that $c \mid (b + c)^n - b^n$ for all $b,c$. 
A: We answer the divisibility question, and not the exact form of the quotient, which has already been dealt with.  Let $b$ be fixed, and consider the polynomial $P(x)=x^n-b^n$. Then there is a polynomial $Q(x)$, and a constant $r$, such that
$$P(x)=(x-b)Q(x)+r.$$
Put $x=b$. Then since $P(b)=0$, and $(b-b)Q(b)=0$, we conclude  that $r=0$. It follows that $x^n-b^n=(x-b)Q(x)$ for all $x$. Now put $x=a$. 
A: $Q=\sum_{i=1}^{n}{a^{n-i}b^{i-1}}=a^{n-1}+a^{n-2}b+\dots+ab^{n-2}+b^{n-1}$
$a^n-b^n=(a-b)Q=(a)Q+Q(-b)$
$\begin{matrix}
(a)Q&=&a^n&+a^{n-1}b&+a^{n-2}b^2&+\dots&+a^2b^{n-2}&+ab^{n-1}&\\
+Q(-b)&=&&-a^{n-1}b&-a^{n-2}b^2&-\dots&-a^2b^{n-2}&-ab^{n-1}&-b^n\\
\end{matrix}$
A: I'm not sure why this never occurred to me before, but looking at your general formula written out in full, I thought, "Where have we seen something like this before?" We can write
$$ a^n \ - \ b^n \ = \ a^n \ \left[ \ 1 \ - \ \left( \frac{b}{a} \right)^n \ \right]  $$
$$ = \ \left[ \ 1 \ - \ \left( \frac{b}{a} \right) \ \right] \ \sum_{k=0}^{n-1} \ a^n  \cdot  \left( \frac{b}{a} \right)^k $$
$$ = \ \left[ \ 1 \ - \ \left( \frac{b}{a} \right) \ \right] \ \cdot \ a \  \cdot \ a^{n-1} \ \cdot \ \left( \ 1 \ + \ \frac{b}{a} \ + \ \frac{b^2}{a^2} \ + \ \ldots \ + \  \frac{b^{n-1}}{a^{n-1}}  \ \right) $$
$$ = \ (a - b) \ ( \ a^{n-1} \ + \ a^{n-2}b \ + \ a^{n-3}b^2 \ + \ \ldots \ + \ b^{n-1} \ ) \ \ . $$
This also suggests a variant proof analogous to the usual one for the "finite geometric series formula":
$$ s \ = \ 1 \ + \ \frac{b}{a} \ + \ \frac{b^2}{a^2} \ + \ \ldots \ + \  \frac{b^{n-1}}{a^{n-1}} $$
$$ \underline{- \ \  \left(\frac{b}{a} \right) \ s \ = \ \frac{b}{a} \ + \ \frac{b^2}{a^2} \ + \ \ldots \ + \  \frac{b^{n-1}}{a^{n-1}}\ + \  \frac{b^n}{a^n} }$$
$$ \left[ \ 1 \ - \ \left(\frac{b}{a} \right) \ \right] \ s \ = \ 1 \ - \ \frac{b^n}{a^n} \ , $$
with multiplication of both sides by $ \ a^n \ $ carried through in the same manner as in the derivation above:
$$ a \ \left[ \ 1 \ - \ \left(\frac{b}{a} \right) \ \right] \ \cdot \ a^{n-1} \ \cdot \  s \ = \ a^n \ - \ b^n \ \ . $$
[This is related to the expression Git Gud uses, but this is a proof without the use of induction.]
