1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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
    Staff Emeritus
    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Induction Problem
  1. Induction Problem (Replies: 7)

  2. Induction Problem (Replies: 3)

  3. A problem on Induction (Replies: 29)

Loading...