Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Induction Problem

  1. Apr 11, 2008 #1
    1. The problem statement, all variables and given/known data
    Prove by Induction that [tex]x^{k}-1=(x-1)(x^{k-1}+x^{k-2}+...+1)[/tex]


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


    3. The attempt at a solution
    [tex]x^{k+1}-1=(x-1)(x^{k}+x^{k-1}+...+1)[/tex] - I tried substituting in the [tex]x^{k}[/tex] term, and expanding [tex]x*x^{k}-1[/tex], but it failed.
     
  2. jcsd
  3. Apr 11, 2008 #2

    HallsofIvy

    User Avatar
    Science Advisor

    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
    [tex]x^{k+1}-1= (x^k-1)(x+1)+ \frac{x-1}{x^k-1}[/tex]
    but now you should be able to simplify that fraction.
     
  4. Apr 11, 2008 #3
    That fraction would simplify to [tex]\frac{1}{x^{k}+x^{k-1}+...+1}[/tex] right?
     
  5. Apr 11, 2008 #4
    That fraction would simplify to [tex]\frac{1}{x^{k}+x^{k-1}+...+1}[/tex] right?
     
  6. Apr 15, 2008 #5
    Bump, I could use some help
     
  7. Apr 15, 2008 #6

    Gib Z

    User Avatar
    Homework Helper

    Check the power of the leading term in the denominator again.
     
  8. Apr 15, 2008 #7
    there is another method without any division. When you have [tex]x^{k+1}-1=x \cdot x^k-1[/tex], substitute the x part inte another appropriate term that equals x, then use the induction assumption.
     
    Last edited: Apr 15, 2008
  9. Apr 15, 2008 #8
    What would the other appropriate term be? I can't really work that out in my head, I thought I should substitute for [tex] x^{k} [/tex] because I can separate it more easily.
     
  10. Apr 16, 2008 #9
    I can give you an example of what technique I mean.
    Prove that [tex]3^{2n+1} + 4^{2n+1}[/tex] always is divisible by 7.
    Indcution. True for n=0, now assume true for n and consider n+1:
    [tex]a_{n+1}=3^{2(n+1)+1} + 4^{2(n+1)+1}=9\cdot 3^{2n+1}+16 \cdot 4^{2n+1}=[/tex]
    [tex]=9\cdot 3^{2n+1}+(9+7) \cdot 4^{2n+1}=9 \cdot a_n + 7 \cdot 4^{2n+1}[/tex]
    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook