# Identity proof $(x^{n}-y^{n})/(x-y) = \sum_{k=1}^{n} x^{n-k}y^{k-1}$

In a proof from a textbook they use the following identity (without proof):

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

Is there an easy way to prove the above? I suppose maybe an induction proof will be appropriate, but I would really like to find a more intuitive proof.

-
Start with $n=2$ and $n=3,$ carefully write out the right-hand side, then multiply it by $(x-y).$ There is cancellation. This way is pretty intuitive. –  Will Jagy Oct 8 '12 at 21:04

It's basically a homogeneous version of the geometric sum formula. Assume w.l.o.g. that $y \neq 0$. Then \begin{align*} \frac{x^n-y^n}{x-y} &= y^{n-1}\frac{(\frac{x}{y})^n-1}{\frac{x}{y}-1} = y^{n-1}\left( \left(\frac{x}{y}\right)^{n-1} + \left(\frac{x}{y}\right)^{n-2} + \ldots + 1 \right) \\ &=x^{n-1} + x^{n-2}y + \ldots + xy^{n-2} + y^{n-1} \end{align*}

More generally, for a polynomial $f = f_0 + f_1+\ldots +f_d$ of degree $d$ where $f_i$ is the term of degree $i$, denote by $f^*$ the homogenization $f^* = y^d f_0 + y^{d-1}f_1 + \ldots + f_d$, i.e. multiply everything by a suitable power of $y$ such that all terms have degree $d$. Then it is easily checked that $(fg)^* = f^* g^*$. Apply this to the geometric sum formula $$x^n - 1 = (x-1)(x^{n-1} + \ldots + x + 1)$$ and you get the desired identity.

-
Just to be pedantic, the degenerate case $y = 0$ can be easily verified too :) –  Alexei Averchenko Oct 8 '12 at 21:17
The homogenization of a polynomial $\rm\,f(x)\,$ is $\rm\ f^*(x,y) \,=\, y^d f(x/y)\$ where $\rm\: d = deg\ f.\$ This maps $\rm\ x^{k}\ \to\ x^{k}\ y^{n-k}\$ so the result is a homogeneous polynomial of degree $\rm\:n\:.\$ –  Bill Dubuque Oct 9 '12 at 0:40

Multiply by $(x-y)$ to get that $x^n-y^n$ should equal $(x-y)\sum_{k=1}^n x^{n-k}y^{k-1}=\sum_{k=1}^n x^{n-k+1}y^{k-1}-x^{n-k}y^{k}$. Now most terms in the right hand side sum will cancel out, leaving only $x^n$ and $-y^n$. This is a so called telescoping sum.

-

Let

$$S=\sum_{k=0}^n a^k$$

Then

$$aS=\sum_{k=0}^n a^{k+1}\\=\sum_{k=1}^{n+1} a^{k}\\=\sum_{k=0}^n a^k-1+a^{n+1}\\=S-1+a^{n+1}$$

Thus

$$aS=S+a^{n+1}-1$$

$$(a-1)S=a^{n+1}-1$$

$$S=\frac{a^{n+1}-1}{a-1}$$

$$\sum_{k=0}^n a^k=\frac{a^{n+1}-1}{a-1}$$

Now, let $a=\dfrac x y$

$$\sum\limits_{k = 0}^n {\frac{{{x^k}}}{{{y^k}}}} = \frac{{\frac{{{x^{n + 1}}}}{{{y^{n + 1}}}} - 1}}{{\frac{x}{y} - 1}}$$ $$\sum\limits_{k = 0}^n {{x^k}{y^{ - k}}} = \frac{y}{{{y^{n + 1}}}}\frac{{{x^{n + 1}} - {y^{n + 1}}}}{{x - y}}$$ $$\sum\limits_{k = 0}^n {{x^k}{y^{ - k}}} = \frac{1}{{{y^n}}}\frac{{{x^{n + 1}} - {y^{n + 1}}}}{{x - y}}$$ $$\sum\limits_{k = 0}^n {{x^k}{y^{n - k}}} = \frac{{{x^{n + 1}} - {y^{n + 1}}}}{{x - y}}$$

-
What's with the downvote? –  Pedro Tamaroff Oct 8 '12 at 21:56
Maybe the downvoter thought you were overgeneralizing. Personally, I didn't. –  000 Oct 8 '12 at 21:57
"overgeneralizing"? In what sense? –  Pedro Tamaroff Oct 8 '12 at 21:58
You started with the geometric sequence in its general form and manipulated it at a particular instance. I am just speculating, but do you see what I mean? Someone may have thought the derivation of the geometric sum formula was not necessary. I don't mind it myself. –  000 Oct 8 '12 at 22:00
Only error I can see is that you left out the condition that $|a|\ne 1$. I don't think doing too much work warrants a downvote. –  peoplepower Oct 8 '12 at 22:49

Yes there is. First let's look at the series:

$$x^{n-1} + x^{n-2}y + x^{n-3}y^2 + \cdots + x^2y^{n-3} + xy^{n-2} + y^{n-1} \, .$$

This is a geometric series with $n$-terms, whose first term is $x^{n-1}$ and whose common ratio is $y/x$. Applying the standard formula we obtain:

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

Simplifying the numerator and denominator and then cancelling common factors gives:

$$x^{n-1} + x^{n-2}y + x^{n-3}y^2 + \cdots + x^2y^{n-3} + xy^{n-2} + y^{n-1} = \frac{x^n-y^n}{x-y} \, .$$

-

I see no one likes induction.

For $n=0$, $$\frac{x^0-y^0}{x-y}=\sum_{1 \le i \le 0}x^{0-i}y^{i-1}=0.$$

Assume for $n=j$ that the identity is true.

Then, for $n=j+1$,

\begin{align} \sum_{1 \le i \le j+1}x^{j+1-i}y^{i-1}&=\left(\sum_{1 \le i \le j}x^{j+1-i}y^{i-1}\right)+y^j\\ &=\left(x\sum_{1 \le i \le j}x^{j-i}y^{i-1} \right)+y^{j}\\ &=x\frac{x^{j}-y^{j}}{x-y}+y^{j}\\ &=\frac{x(x^j-y^j)+y^j(x-y)}{x-y}\\ &=\frac{x^{j+1}-xy^j+y^jx-y^{j+1}}{x-y}\\ &=\frac{x^{j+1}-y^{j+1}}{x-y}. \end{align}

Hence, it is as we sought.

-

My pre-calc instructor showed me this way (it's essentially the same as some of the answers above, but the details are a little bit different):

Define $S_n:= x^{n-1} + yx^{n-2} + y^2x^{n-3}+...+ \ y^{n-3}x^2 + y^{n-2}x + y^{n-1}$

Note that $S_n$ as you've defined it is the same as I've defined it, i.e. $S_n=\sum_{k=1}^{n} x^{n-k}y^{k-1}$. Then consider the following difference:

$(x-y)S_n = \ xS_n - y\ S_n$ = $(x^{n} + yx^{n-1} + y^2x^{n-2}+...+ \ y^{n-3}x^3 + y^{n-2}x^2 + xy^{n-1})-(x^{n-1}y + y^2x^{n-2} + y^3x^{n-3}+...+ \ y^{n-2}x^2 + y^{n-1}x + y^{n})$

This term on the right telescopes - everything in that large term on the right hand side cancels except for $x^n-y^n$. So we can write

$(x-y)S_n = x^n-y^n$

or

$S_n=\frac{x^n-y^n}{x-y}$, and you're done!

-
Didn't see his post before, but this is exactly what Max Morin suggests. –  Bachmaninoff Oct 8 '12 at 22:33