2
$\begingroup$

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.

  • 1
    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.2012-10-08

6 Answers 6

7

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.

  • 0
    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](http://en.wikipedia.org/wiki/Homogeneous_polynomial) of degree $\rm\:n\:.\ $2012-10-09
5

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.

2

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

  • 0
    @peoplepower If $a=1$ the sum is clearly $n+1$, there is no error there. One can claear that out in the beginning, however.2012-10-08
0

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

0

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.

0

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!

  • 0
    Didn't see his post before, but this is exactly what Max Morin suggests.2012-10-08