Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

6 Answers 6

up vote 4 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
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
show 1 more comment

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} \, . $$

share|improve this answer
add comment

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.

share|improve this answer
add comment

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!

share|improve this answer
    
Didn't see his post before, but this is exactly what Max Morin suggests. –  Bachmaninoff Oct 8 '12 at 22:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.