# Induction Problem

1. Apr 11, 2008

### dtl42

1. The problem statement, all variables and given/known data
Prove by Induction that $$x^{k}-1=(x-1)(x^{k-1}+x^{k-2}+...+1)$$

2. Relevant 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)$$

3. 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.

2. Apr 11, 2008

### HallsofIvy

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

You have xk+1- 1 and you need to use the fact that xk- 1= (x-1)(xk-1+...+ x+ 1). Have you tried dividing xk+1-1 by xk- 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.

3. Apr 11, 2008

### dtl42

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

4. Apr 11, 2008

### dtl42

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

5. Apr 15, 2008

### dtl42

Bump, I could use some help

6. Apr 15, 2008

### Gib Z

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

7. Apr 15, 2008

### 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.

Last edited: Apr 15, 2008
8. Apr 15, 2008

### 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.

9. Apr 16, 2008

### 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? :)

Last edited: Apr 16, 2008
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook