# Proving $x^n - y^n = (x-y)(x^{n-1} + x^{n-2} y + … + x y^{n-2} + y^{n-1})$

In Spivak's Calculus 3rd Edition, there is an exercise to prove the following:

$$x^n - y^n = (x-y)(x^{n-1} + x^{n-2} y + ... + x y^{n-2} + y^{n-1})$$

I can't seem to get the answer. Either I've gone wrong somewhere, I'm overlooking something, or both. Here's my (non) proof:

\begin{align*} x^n - y^n &= (x - y)(x^{n-1} + x^{n-2}y +\cdots+ xy^{n-2} + y^{n-1}) \\ &= x \cdot x^{n-1} + x \cdot x^{n-2} \cdot y + \cdots + x \cdot x \cdot y^{n-2} + x \cdot y^{n-1}\\ &\qquad + (-y) \cdot x^{n-1} + (-y) \cdot x^{n-2} \cdot y + \cdots + (-y) \cdot x \cdot y^{n-2} + (-y) \cdot y^{n-1}\\ &= x^n + x^{n-1} y + \cdots + x^2 y^{n-2} + x y^{n-1} - x^{n-1}y - y^2 x^{n-2} - \cdots- x y^{n-1} - y^n \\ &= x^n + x^2 y^{n-2} - x^{n-2} y^2 - y^n \\ &\neq x^n - y^n \end{align*}

Is there something I can do with $x^n + x^2 y^{n-2} - x^{n-2} y^2 - y^n$ that I'm not seeing, or did I make a mistake early on?

EDIT:

I should have pointed out that this exercise is meant to be done using nine of the twelve basic properties of numbers that Spivak outlines in his book:

• Existence of an additive identity
• Associative law for multiplication
• Existence of a multiplicative identity
• Existence of multiplicative inverses
• Commutative law for multiplication
• Distibutive law
-
Write out your expanded expression in two rows multiplying first by $x$ to get the first row and then by $-y$ to get the second row. If you write the second row so that expressions with the same power of $x$ are underneath each other, and do an extra term or two at the beginning and the end, you should detect quite easily what has gone wrong. – Mark Bennet Mar 7 '12 at 20:58
I'll give this a try and let you know how it goes. – jamesbrewr Mar 7 '12 at 21:00
Be carefull the ... from the first and second part are not the same thing ;) So you cannot cancel ... by .... – N. S. Mar 7 '12 at 21:03
Alternatively, you can use induction by writing $x^n-y^n = x(x^{n-1}-y^{n-1}) + (x-y)y^{n-1}$. – marlu Mar 7 '12 at 21:03
Another possibility is to write $x^n-y^n = x^n\left(1-\left(y/x\right)^n\right)$ (the case $x=0$ is trivial) and then use the geometric sum formula. – marlu Mar 7 '12 at 21:08

You have everything right except the last line.

Maybe it is easier to do in this order:

$$(x−y)\left(x^{n−1}+x^{n−2}y+\cdots+xy^{n−2}+y^{n−1}\right)=\\ =x\cdot x^{n-1}-y\cdot x^{n-1} +x\cdot x^{n−2}y- y\cdot x^{n−2}y+x\cdot x^{n−3}y^2-\cdots\\ \cdots -y\cdot x^2y^{n-3} +x\cdot xy^{n-2}-y \cdot y^{n-1}$$

The second term $y\cdot x^{n-1}$ is the same as the third term $x\cdot x^{n−2}y$ except the sign, similarly the 4th and the 5th terms are canceled... So the only terms left are: $x\cdot x^{n-1}$ and $y\cdot y^{n-1}$.

-
This leaves me in the exact same position that I'm in now .. – jamesbrewr Mar 7 '12 at 21:22
In your opening post, you (mistakenly) had two terms in addition to the ones grozhd points out are left – Hurkyl Mar 7 '12 at 21:38
This could have been better explained, although I see what you did now. You added an extra term before the $...$ and multiplied it by $x$. Then you added another term after the $...$ and multiplied it by $(-y)$. Thanks! – jamesbrewr Mar 7 '12 at 21:56

Here is the inductive step, presented more conceptually

$$\rm\frac{x^{n+1}-y^{n+1}}{x-y}\: =\ x^n\: +\ y\ \frac{x^n-y^n}{x-y}$$

So, intuitively, proceeding inductively yields

$$\rm\:x^n + y\: (x^{n-1} + y\: (x^{n-2} +\:\cdots\:))\ =\ x^n + y\: x^{n-1} + y^2\: x^{n-2} + \:\cdots$$

Use this intuition to compose a formal proof by induction.

-
It should be possible to prove this using the basic properties of numbers discussed in Spivak's book: Associative law for addition, Existence of an additive identify, Existence of additive inverses, Commutative law for addition, Associative law for multiplication, Existence of a multiplicative identity, Existence of multiplicative inverses, Commutative law for multiplication, and Distributive law. – jamesbrewr Mar 7 '12 at 21:31

I think it would be easier for you to recall

$$\left(1+x+x^2+\cdots+x^{n-1}\right)(x-1) = x^n-1$$

and put $x=\dfrac{b}{a}$

\eqalign{ & \left( {1 + \frac{b}{a} + \frac{{{b^2}}}{{{a^2}}} + \cdots + \frac{{{b^{n - 1}}}}{{{a^{n - 1}}}}} \right)\left( {\frac{b}{a} - 1} \right) = \frac{{{b^n}}}{{{a^n}}} - 1 \cr & \left( {1 + \frac{b}{a} + \frac{{{b^2}}}{{{a^2}}} + \cdots + \frac{{{b^{n - 1}}}}{{{a^{n - 1}}}}} \right)\left( {\frac{{b - a}}{a}} \right) = \frac{{{b^n} - {a^n}}}{{{a^n}}} \cr & {a^{n - 1}}\left( {1 + \frac{b}{a} + \frac{{{b^2}}}{{{a^2}}} + \cdots + \frac{{{b^{n - 1}}}}{{{a^{n - 1}}}}} \right)\left( {b - a} \right) = {b^n} - {a^n} \cr & \left( {{a^{n - 1}} + b{a^{n - 2}} + {b^2}{a^{n - 3}} + \cdots + {b^{n - 1}}} \right)\left( {b - a} \right) = {b^n} - {a^n} \cr}

A little bit "tidier", so that we know what happens in between the dots...

\eqalign{ & {x^n} - 1 = \left( {x - 1} \right)\sum\limits_{k = 0}^{n - 1} {{x^k}} \cr & \frac{{{b^n}}}{{{a^n}}} - 1 = \left( {\frac{b}{a} - 1} \right)\sum\limits_{k = 0}^{n - 1} {\frac{{{b^k}}}{{{a^k}}}} \cr & \frac{{{b^n} - {a^n}}}{{{a^n}}} = \left( {\frac{{b - a}}{a}} \right)\sum\limits_{k = 0}^{n - 1} {\frac{{{b^k}}}{{{a^k}}}} \cr & {b^n} - {a^n} = \left( {b - a} \right)\sum\limits_{k = 0}^{n - 1} {{b^k}{a^{n - k - 1}}} \cr}

-

The $x^2 y^{n-2}$ term from $x \cdot x y^{n-2}$ is cancelled by the term from $(-y) \cdot x^2 y^{n-3}$. Similarly, the $(-y) \cdot x^{n-2} y$ is cancelled by the $x \cdot x^{n-3} y^2$.

-

Your method is sound, you just made a sort of arithmetic mistake. When cancelling or otherwise combining two sequences, try explicitly lining things up to make sure you do it right:

\begin{align} x^n &+& x^{n-1} y &+& x^{n-2} y^2 &+& \cdots + x y^{n-1} & \\ &-& x^{n-1} y &-& x^{n-2} y^2 &+& \cdots - x y^{n-1} &+& y^n \end{align}

I've found that, when shorthand starts becoming awkward and/or error prone, that it really is helpful to switch to summation notation. So, you are trying to prove

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

and the first stem of your work would be

$$\cdots = \left( \sum_{k=0}^{n-1} x^{k+1} y^{n-1-k} \right) + \left( \sum_{k=0}^{n-1} x^{k} y^{n-k} \right)$$

and now, we can change the index to line things up: I'm substituting k = j-1:

$$\cdots = \left( \sum_{(j-1)=0}^{n-1} x^{(j-1)+1} y^{n-1-(j-1)} \right) + \left( \sum_{k=0}^{n-1} x^{k} y^{n-k} \right)$$ and simplifying

$$\cdots = \left( \sum_{j=1}^{n} x^{j} y^{n-j} \right) + \left( \sum_{k=0}^{n-1} x^{k} y^{n-k} \right)$$

and now replacing $j$ with $k$.

$$\cdots = \left( \sum_{k=1}^{n} x^{k} y^{n-k} \right) + \left( \sum_{k=0}^{n-1} x^{k} y^{n-k} \right)$$

(can you take it from here?)

-

Since powers of x and y is always greater than or equal to zero, You can prove it by mathematical induction.

-