# Homework Help: Proof of (x^n - 1) / (x - 1) = x^n-1 + x^n-2 + ... + x + 1

1. Sep 18, 2017

### Stefk

1. The problem statement, all variables and given/known data

The problem comes from Lang's Basic Mathematics, chapter 1, paragraph 6 (multiplicative inverses) and simply asks to prove the relation:

(xn - 1) / (x - 1) = xn - 1 + xn - 2 + ... + x + 1

2. Relevant equations

a-1a = aa-1 = 1
Cross-multiplication rule
Cancellation law for multiplication

3. The attempt at a solution

The solution is actually given at the back of the book, but there's a couple of simplifications I have trouble understanding:

(x - 1) (xn-1 + xn-2 + ... + x + 1)
= x(xn-1 + xn-2 + ... + x + 1) - (xn-1 + xn-2 + ... + x + 1)
= xn + xn-1 + ... + x - xn-1 - xn-2 - ... - x - 1
= xn - 1

The two things I don't understand are:

1. Shouldn't the result of x(xn-1 + xn-2 + ... + x + 1) include x2? [line 2]
2. How is xn-2 excluded from the final result? [line 3]

2. Sep 18, 2017

### Staff: Mentor

1. Yes, but it's not shown. The ellipsis (...) indicates that a number of terms in the middle aren't shown.
2. In the first multiplication you have x * xn - 3 = xn - 2, but in the second multiplication you have -1 * xn - 2 = -xn - 2, so the terms in xn - 2 drop out.

To give you better intuition on what is going on, try this formula with, say, $\frac{x^4 - 1}{x - 1} = x^3 + x^2 + x + 1$. Multiply the third-degree polynomial on the right by x - 1 and verify that you end up with $x^4 - 1$.

3. Sep 19, 2017

### Ray Vickson

You could also prove the result by induction, using the fact that $x^{n+1}-1 = x^{n+1}-x^n + x^n - 1 = x^n (x-1) + x^n-1.$

4. Sep 19, 2017

### Stefk

The two previous exercises in Lang's book do exactly that (with $x^3-1$ then $x⁴-1$) and I understand the exercise mentioned above is a kind of generalization, but the mechanism of the proof seems a little arbitrary to me.

What allows us to make an explicit term ($x²$) a part of the ellipsis and exclude it from the computation and on the other hand, extract a term hidden in that ellipsis ($x^{n-3}$) and use it to simplify the expression? And how comes the second ellipsis isn't affected by these operations, given it represents the same thing, that was simply distributed in the first place?

I guess I need to get acquainted with that sort of reasoning, and also with induction techniques as mentioned by @Ray Vickson, that I don't completely follow either. I planned to read a book later on the different kind of proofs ("How to prove it", Velleman), maybe should I read it sooner? Anyway, thank you both for your answers, I'm far beyond the objective of Lang's chapter and I'll definitely get back at this discussion when I'm ready!

5. Sep 19, 2017

### Staff: Mentor

Addressing your question about the $x^2$ term...
$(x - 1)(x^{n - 1} + x^{n - 2} + x^{n - 3} + \dots + x^2 + x + 1)$
$= x^n - x^{n - 1} + x^{n - 1} - x^{n - 2} + x^{n - 2} + \dots - x^3 + x^3 - x^2 + x^2 - x + x - 1$
Here I'm doing the multiplications with x first then with -1. All of the terms vanish, except for the first and last. Regarding the ellipsis, you can add as many terms as you like before the ellipsis, as well as after it.

The best way to see what is going on in the general case is to use mathematical induction, as was already mentioned.

6. Sep 20, 2017

### Ray Vickson

You ask "What allows us to make an explicit term ($x²$) a part of the ellipsis and exclude it from the computation... ?" If you have an explicit example like $(x^5-1)/(x-1)$ you can write out all of the terms and so do not need an ellipsis. If you have $(x^{150}-1)/(x-1)$ you can still write out all of the terms, although it will start to be painful. For any given value of $n$ you can write out all of the terms of $(x^n-1)/(x-1)$. However, what happens if you do not have a given value of $n$? Then you cannot write out all of the terms because you do not know how many of them to write. In that case, "..." comes in handy; it is shorthand for "continue in the same way" or "continue that pattern". Then, whether you want to write $x^{n-1} + x^{n-2} + \cdots + x^2 + x + 1$ or $x^{n-1} + x^{n-2} + \cdots +x+1$ or even $x^{n-1} + x^{n-2} + \cdots + 1$ is largely a matter of personal taste (although the last one is probably not the best choice). Personally, I would go with the middle one, having two terms at the start (to show how the pattern begins) and two at the end (to show how the pattern terminates).

Anyway, to get back to your question: the $x^2$ is not omitted from the computation, it is just not "shown"----but it is understood to be there, lurking in the background.

7. Sep 20, 2017

### Stefk

I think I finally got it :) It wasn't immediately clear to me that expressions like these:

$x^{n-1} + x^{n-1} + \cdots + 1$
$x^{n-1} + x^{n-2} + \cdots + x + 1$
$x^{n-1} + x^{n-2} + x^{n-3} + \cdots + x + 1$
$x^{n-1} + x^{n-2} + x^{n-3} + x^{n-4} + \cdots + x^3 + x^2 + x + 1$
$etc.$

were essentially equivalent and that the terms denoted by the ellipsis could be expanded or collapsed freely as long as the pattern was followed. Given that, I can see there's not one but multiple (in fact, infinite) ways to prove the original relation. As I've had real trouble at first with the implicit character of some operations in Lang's solution and examples in this thread, I'll write two dumbly explicit versions in case someone encounters the same difficulty.

The first one deploys terms hidden in the ellipsis as @Mark44 suggested initially:

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

The second is I think closer to the solution provided by Lang and collapses terms on each side instead:

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

Many thanks again @Mark44 and @Ray Vickson for your explanations and also your patience!

Have a nice day,

Stéphane

8. Sep 20, 2017

### Staff: Mentor

Actually, they are equal. Equations or inequalities can be equivalent. All of the above are just different representations (expressions) of the same thing.
Correction to the above:
$x^{n-1} + x^{n-2} + \cdots + x + 1$
$= x^{n-1} + x^{n-2} + x^{n-3} + \cdots + x + 1$
$= x^{n-1} + x^{n-2} + x^{n-3} + x^{n-4} + \cdots + x^3 + x^2 + x + 1$
$etc.$

In what you wrote you had $x^{n - 1}$ listed twice in the first line.

9. Sep 20, 2017

### rcgldr

I don't know if this would count as a proof, but you could do long hand polynomial division:

Code (Text):

x^{n-1} + x^{n-2} +  ...   + 1
------------------------------------------------------
x - 1 | x^{n  } -                              1
x^{n  } - x^{n-1}
--------------------
x^{n-1}
x^{n-1} - x^{n-2}
-------------------
x^{n-2}
...
-----
x - 1
x - 1

Last edited: Sep 21, 2017
10. Sep 29, 2017

### epenguin

At school I like you met, first for n=2 then 3 then n generally this factorization of $\left(x^n-1\right)$
$$\left( x^{n}-1\right) =\left( x-1\right) \left( x^{n-1}+x^{n-2}+...+x+1\right)$$
Quite separately I had earlier learnt how to sum a geometric series. Till much after school and having almost forgotten both I never made any relation between the two - have you? Of course the expression in the last bracket above is just the geometric series, for n terms starting at 1, common ratio $x$ and up to the nth term $\sum ^{n-1}_{r=0}x^{r}$. If we were giving a formula for the sum of the geometric series we might prefer it up to the $x^n$ term; the formula would then be
$$\sum ^{n}_{r=0}x^{r}=\dfrac {x^{n+1}-1}{x-1}$$

Particularly useful is the case $0<x<1, n= \infty$
$$\sum ^{\infty }_{r=0}x^{r}=\dfrac {1}{1-x}$$
You may meet this in not-served-on-a-plate contexts, e.g in statistical mechanics you wil meet things like
$$\sum ^{\infty }_{n=1}e^{-(nh\nu /kT)}$$
(where the letters h, ν, k, T, are physical constants or parameters) which, duly alerted, I hope you can now sum.
.
I don't know that there is really such a thing as "induction techniques". What I notice from questions here is that students' questions indicate them frequently stumbling over two things: induction and limits. I even wondered whether the difficulty with limits should be avoided from teaching by avoiding limits, as some people suggest; however then I realised the difficulty in both cases was mainly not with the induction or limits concepts, but just in doing the ordinary algebra that the excercises in them require. There are usualLy pretty clear pointers, you start with some equation f(n) = 0 that you consider true, you then know you have, using this last fact, to prove f(n+1) = 0. A couple of examples help, but maybe, as in your case, some of the wording or symbolic representation wrapped around these two things fails at first to mean a lot to the unpracticed.

I don't know it but Velleman sounds like a good book; I have often recommended 'How to solve it' by Polya, but focus probably different.

11. Oct 22, 2017

### Stefk

@epenguin I've only had a superficial encounter with geometric series many years ago, so I'll come back to your explanation when the material is fresh again ;). Thanks for the reference to Polya's book by the way. I'm definitely putting it in my reading list.