Prove x^{k+1}-1=(x-1)(x^{k}+x^{k-1}+...+1) by Induction

[dtl42]

Homework Statement

Prove by Induction that x^{k}-1=(x-1)(x^{k-1}+x^{k-2}+...+1)

Homework Equations

None? I need to prove x^{k+1}-1=(x-1)(x^{k}+x^{k-1}+...+1) by assuming this is true: x^{k}-1=(x-1)(x^{k-1}+x^{k-2}+...+1)

The Attempt at a Solution

x^{k+1}-1=(x-1)(x^{k}+x^{k-1}+...+1) - I tried substituting in the x^{k} term, and expanding x*x^{k}-1, but it failed.

 

[HallsofIvy]

Homework Statement

Prove by Induction that x^{k}-1=(x-1)(x^{k-1}+x^{k-2}+...+1)

Homework Equations

None? I need to prove x^{k+1}-1=(x-1)(x^{k}+x^{k-1}+...+1) by assuming this is true: x^{k}-1=(x-1)(x^{k-1}+x^{k-2}+...+1)

The Attempt at a Solution

x^{k+1}-1=(x-1)(x^{k}+x^{k-1}+...+1)

You can't use that- that's what you are trying to prove.

- I tried substituting in the x^{k} term, and expanding x*x^{k}-1, but it failed.

You have x^k+1- 1 and you need to use the fact that x^k- 1= (x-1)(x^k-1+...+ x+ 1). Have you tried dividing x^k+1-1 by x^k- 1? It does not divide evenly, you get
x^{k+1}-1= (x^k-1)(x+1)+ \frac{x-1}{x^k-1}
but now you should be able to simplify that fraction.

 

[dtl42]

That fraction would simplify to \frac{1}{x^{k}+x^{k-1}+...+1} right?

 

[dtl42]

That fraction would simplify to \frac{1}{x^{k}+x^{k-1}+...+1} right?

 

[dtl42]

Bump, I could use some help

 

[Gib Z]

Check the power of the leading term in the denominator again.

 

[Kurret]

there is another method without any division. When you have x^{k+1}-1=x \cdot x^k-1, substitute the x part inte another appropriate term that equals x, then use the induction assumption.

 

[dtl42]

What would the other appropriate term be? I can't really work that out in my head, I thought I should substitute for x^{k} because I can separate it more easily.

 

[Kurret]

I can give you an example of what technique I mean.
Prove that 3^{2n+1} + 4^{2n+1} always is divisible by 7.
Indcution. True for n=0, now assume true for n and consider n+1:
a_{n+1}=3^{2(n+1)+1} + 4^{2(n+1)+1}=9\cdot 3^{2n+1}+16 \cdot 4^{2n+1}=
=9\cdot 3^{2n+1}+(9+7) \cdot 4^{2n+1}=9 \cdot a_n + 7 \cdot 4^{2n+1}
which is divisible by 7 if a_n is.
How can you apply this method on your problem? how can the two terms look like, if they should equal x? :)