(x^k) - 1 = (x - 1)*(x^(k-1) + x^(k-2) + ... + x + 1)


by General_Sax
Tags: 1xk1
General_Sax
General_Sax is offline
#1
Feb9-12, 09:25 PM
P: 450
(x^k) - 1 = (x - 1)*(x^(k-1) + x^(k-2) + ... + x + 1)

Where does this factorization come from? I need to know so I can use it in a proof. Thanks.
Phys.Org News Partner Science news on Phys.org
NASA's space station Robonaut finally getting legs
Free the seed: OSSI nurtures growing plants without patent barriers
Going nuts? Turkey looks to pistachios to heat new eco-city
micromass
micromass is online now
#2
Feb9-12, 10:10 PM
Mentor
micromass's Avatar
P: 16,590
Work out the right side...
Dickfore
Dickfore is offline
#3
Feb9-12, 10:33 PM
P: 3,015
Use mathematical induction:
[tex]
x^{k+1} - 1 = (x^{k+1} - x^k) + (x^k - 1) = (x - 1) x^k +(x^k - 1)
[/tex]

General_Sax
General_Sax is offline
#4
Feb9-12, 11:09 PM
P: 450

(x^k) - 1 = (x - 1)*(x^(k-1) + x^(k-2) + ... + x + 1)


Quote Quote by micromass View Post
Work out the right side...
So, there is no theorem to use?

@Dickfore

I'm confused as to the next step -- yes I've been trying to work it out.

Should I try to factor (x-1) out of the expression?
Dickfore
Dickfore is offline
#5
Feb10-12, 09:07 AM
P: 3,015
Quote Quote by General_Sax View Post
@Dickfore

I'm confused as to the next step -- yes I've been trying to work it out.

Should I try to factor (x-1) out of the expression?
According to P.M.I., you should substitute the expression that you're trying to prove for [itex]n = k[/itex], in this case for [itex]x^k - 1[/itex], factor [itex]x - 1[/itex], and see if you get the corresponding expression for [itex]n = k + 1[/itex]. If you do, then the proof is complete.
epenguin
epenguin is offline
#6
Feb10-12, 10:07 AM
HW Helper
epenguin's Avatar
P: 1,932
Quote Quote by General_Sax View Post
So, there is no theorem to use?
Could almost say this is the theorem.

Multiply your last bracket by x
on the next line multiply that same last bracket by -1.
Compare. Add.

This is a very useful formula.
That last bracket is the geometrical series for example, hence you calculate it equals (xk - 1)/(x - 1). Heard anything like that before?
General_Sax
General_Sax is offline
#7
Feb10-12, 12:55 PM
P: 450
Thanks for the help people. I think I've got it. Just used formula for geometric series and did some algebra -- hope it's good enough.
Fredrik
Fredrik is offline
#8
Feb10-12, 03:50 PM
Emeritus
Sci Advisor
PF Gold
Fredrik's Avatar
P: 8,995
Quote Quote by General_Sax View Post
Thanks for the help people. I think I've got it. Just used formula for geometric series and did some algebra -- hope it's good enough.
Did you really mean that you used the formula for the geometric series? This theorem?
For all real numbers x such that |x|<1, ##\sum_{k=0}^\infty x^k=\frac{1}{1-x}.##
This theorem is much harder to understand than the formula you're trying to prove, because it involves convergence. Its standard proof uses the formula you're trying to prove, which by the way holds for all real numbers x, not just the ones that satisfy |x|<1.

Quote Quote by General_Sax View Post
So, there is no theorem to use?
Only the distributive laws a(b+c)=ab+ac, (a+b)c=ac+bc, and if you want to do a rigorous proof that the result of the multiplication is what you (should) think it is, you have to use induction.

Quote Quote by General_Sax View Post
Should I try to factor (x-1) out of the expression?
Wouldn't that give you two factors of (x-1)? That would only make things worse.
General_Sax
General_Sax is offline
#9
Feb10-12, 08:21 PM
P: 450
Thanks for the additional effort/attention Fredrik, but I've already used the geometric "series" -- perhaps it's more accurate to use the term "sum" -- in a proof.

http://en.wikipedia.org/wiki/Geometric_series#Formula

that's the one I used. Just split it up w/ some algebra. It's for a CMPUT course and we haven't much experience with proofs so I don't think they expect much rigour.
Fredrik
Fredrik is offline
#10
Feb11-12, 05:26 AM
Emeritus
Sci Advisor
PF Gold
Fredrik's Avatar
P: 8,995
So basically you took the formula ##1+x+\cdots+x^{k-1}=\frac{1-x^{k}}{1-x}## (which doesn't hold for x=1 by the way) and just multiplied it by x-1? If I was your teacher, I wouldn't accept that as an answer. (The formula you found is too similar to what you're supposed to prove). Why don't you just do the multiplication on your right-hand side to see what you get? Do you know how to evaluate a(b+c)? How about (a+b)(b+c)? How about (a+b)(b+c+d)?


Register to reply