3
$\begingroup$

I am investigating a problem from George E. Andrews Number Theory (Dover, 1971), discussed previously here:

Induction Proof that $x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1})$

I was led astray for a bit, because I misunderstood the rhs to be the difference of $x$ and $y$ times the binomial expansion $(x+y)^{n-1}$.

But this is wrong... the rhs is actually the difference of $x$ and $y$ times the binomial expansion $(x+y)^{n-1}$ "without the coeffients", i.e.,

$$\sum_{i=0}^{n-1}x^{n-1-i}y^i$$

(also briefly discussed here: Binomial summation without coefficient)

Is there a name for this summation?

$\endgroup$
4
  • $\begingroup$ It is closely linked to formula for the sum of the $n$ first terms of a geometric progression: $\;1+u+u^2+\dotsm+u^{n-1}=\dfrac{1-x^n}{1-x} $. It has nothing to a do with the binomial expansion, since it is a factorisation formula, not an expansion formula. Unless you consider any sum with $n$ terms is some kind of binomial expansion… $\endgroup$
    – Bernard
    Dec 20, 2015 at 19:11
  • $\begingroup$ I was once tricked into binomially expanding 1/(1+0) $\endgroup$
    – Alec Teal
    Dec 20, 2015 at 19:23
  • $\begingroup$ It's kind of like a Cauchy product or discrete convolution. $\endgroup$
    – Cameron Williams
    Dec 20, 2015 at 22:24
  • $\begingroup$ Yes I'm on the same idea as Cameron. This fact(orization) is used in discrete convolutions when calculating mean values of many pixels. If instead calculate cumulative sum then we can get any sub-length mean value as a simple difference of two values in the table of cumulative sum. Called "summed area table" or "integral image" in image processing but those are 2D images so it is 2D convolution and a little bit more involving, but same idea. $\endgroup$
    – mathreadler
    Dec 20, 2015 at 22:45

2 Answers 2

Reset to default
2
$\begingroup$

There is no specific name for the bivariate polynomial \begin{align*} x^{n-1}+x^{n-2}y+x^{n-3}y^2+\cdots+x^2y^{n-3}+xy^{n-2}+y^{n-1} \end{align*}

but the nice expression \begin{align*} (x-&y)(x^{n-1}+x^{n-2}y+x^{n-3}y^2+\cdots+x^2y^{n-3}+xy^{n-2}+y^{n-1})\\ \end{align*}

is called a telescoping sum since all terms besides the first and the last cancel out.

\begin{align*} (x-&y)(x^{n-1}+x^{n-2}y+x^{n-3}y^2+\cdots+x^2y^{n-3}+xy^{n-2}+y^{n-1})\\ &=x(x^{n-1}+x^{n-2}y+x^{n-3}y^2+\cdots+x^2y^{n-3}+xy^{n-2}+y^{n-1})\\ &\qquad-y(x^{n-1}+x^{n-2}y+x^{n-3}y^2+\cdots+x^2y^{n-3}+xy^{n-2}+y^{n-1})\\ &=\color{blue}{x^{n}}+x^{n-1}y+x^{n-2}y^2+\cdots+x^3y^{n-3}+x^2y^{n-2}+xy^{n-1}\\ &\qquad\ \;-x^{n-1}y-x^{n-2}y^2-\cdots-x^3y^{n-3}-x^2y^{n-2}-xy^{n-1}\color{blue}{-y^{n}}\\ &=\color{blue}{x^n-y^n}\\ \end{align*}

$\endgroup$
2
  • $\begingroup$ Thanks Marcus (@ElliotG as well). So I guess my "telescoping sum" would best be described as the explicit formula for "the difference of like powers, scaled down by the difference of the bases", i.e. $\frac{x^n-y^n}{x-y}$. To Bernard's point ... yeah, I didn't mean to imply the sum is an expansion per se, just that the way the powers run from $n-1$ to $0$ for $x$, and $0$ to $n-1$ for $y$ has a superficial resemblance to the powers that crop up in the binomial expansion. $\endgroup$
    – billc
    Dec 21, 2015 at 4:47
  • $\begingroup$ @billc: There is also a strong connection with cyclotomic polynomials. $\endgroup$
    – epi163sqrt
    Dec 21, 2015 at 10:10
1
$\begingroup$

I'm not sure if I'm answering your question here, but this is what I usually think:

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

Of course, this uses induction implicitly, but its not hard to see why it works from the standpoint of distributing and everything canceling out.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .