Proof of (x^n - 1) / (x - 1) = x^n-1 + x^n-2 + .... + x + 1

  • Thread starter Thread starter Stefk
  • Start date Start date
  • Tags Tags
    Proof
AI Thread Summary
The discussion revolves around proving the equation (x^n - 1) / (x - 1) = x^(n-1) + x^(n-2) + ... + x + 1, as presented in Lang's Basic Mathematics. Participants express confusion over specific steps in the solution, particularly regarding the omission of certain terms and the use of ellipses to represent sequences. Clarifications highlight that the ellipsis indicates a continuation of terms, and that terms can be included or excluded based on context. Induction is suggested as a method for a more general proof, and the conversation emphasizes the equivalence of different representations of the polynomial. Understanding these concepts is deemed essential for grasping the underlying mathematical reasoning.
Stefk

Homework Statement



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

Homework Equations



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

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]
Thanks in advance for your help!
 
Physics news on Phys.org
Stefk said:

Homework Statement



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

Homework Equations



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

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]
Thanks in advance for your help!
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##.
 
Stefk said:

Homework Statement



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

Homework Equations



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

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]
Thanks in advance for your help!

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.##
 
Mark44 said:
To give you better intuition on what is going on, try this formula with, say, x4−1x−1=x3+x2+x+1x4−1x−1=x3+x2+x+1\frac{x^4 - 1}{x - 1} = x^3 + x^2 + x + 1

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!
 
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.
 
Stefk said:
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!

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.
 
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
 
Stefk said:
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
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.
Stefk said:
and that the terms denoted by the ellipsis could be expanded or collapsed freely as long as the pattern was followed.
 
I don't know if this would count as a proof, but you could do long hand polynomial division:

Code: 
                  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:
  • #10
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 learned 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.
.
Stefk said:
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!
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 realized 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
@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.
 

Similar threads

Induction: x+1/x is an int. Prove that x^n+1/x^n is an int...
Replies
6
Views
9K
My proof that the square root of 2 multiplied by r is irrational
Replies
2
Views
3K
Coefficients in the expansion of (1+x)n in A.P, find n
Replies
6
Views
2K
MHB (e^ix)-1=(2ie^(ix/2))x(sin (x/2))
Replies
1
Views
3K
Prove that ## \sum_{n\leq x}\frac{\phi(n)}{\sqrt{n}}=Cx^{3/2}+.... ##.
Replies
4
Views
2K
Prove that ## g(x)=f(x)\log {x}-\int_{2}^{x}t^{-1}f(t)dt ##.
Replies
7
Views
1K
B How can hyperreal numbers make infinitesimals logically sound in calculus?
Replies
24
Views
6K
Where Did ##(n−r+1)^{th}## Come From in Binomial Expansion?
Replies
3
Views
1K
A question about Monte Carlo calculations
Replies
11
Views
2K
Polynomial Function Homework: Find Function of Degree n-1
Replies
15
Views
6K

Hot Threads

Recent Insights

Back
Top