Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

PhoenixFire Group Title

Using mathematical induction prove that for \[ {n \ge 1} \in \mathbb{Z} \] \[ 3^{2k}-1 \] is divisible by 8.

  • one year ago
  • one year ago

  • This Question is Closed
  1. hash.nuke Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    show it for certain number n ... show it hods for n+1

    • one year ago
  2. PhoenixFire Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Yeah I got the base step. n=1 \[3^2-1=8k\] where k is some Integer. \[8=8k\] so it's divisible.

    • one year ago
  3. PhoenixFire Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Then the inductive hypothesis is: Assume \[3^{2k}-1\] is divisible by 8 when k=n Now to prove it hold for k=n+1, I get confused and don't know what to do.

    • one year ago
  4. hash.nuke Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    this is difficult. let's try without induction first. you have to show that there is 3 even factors.

    • one year ago
  5. hash.nuke Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    3^(2k) - 1 = (3^k)^2 - 1^2 = (3^k - 1)(3^k + 1) <-- one of them is divisible by 4. and both is divisible by 2 ... hence it is divisible by 8

    • one year ago
  6. PhoenixFire Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Okay, I understand that. Now what?

    • one year ago
  7. hash.nuke Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    i don't see short sweet method.

    • one year ago
  8. hash.nuke Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Prove ... if (3^k - 1) is divisible by 2 prove (3^k + 1) is always divisible by 4 using induction. and vice-versa ...

    • one year ago
  9. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    you want to show that give \(3^{2k}-1\) is divisible by \(8\) then \(3^{2(k+1)}-1\) is as well

    • one year ago
  10. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    that is, if it is true for \(n=k\) then it is true for \(k+1\) now some algebra slight of hand

    • one year ago
  11. hash.nuke Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    3^(2(k+1)) - 1 = 9(3^(2k) - 1) + 1) - 1 = 9(x+1) - 1 = 9*8x + 8 which is divisible by 8

    • one year ago
  12. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    and the goal is to get \(3^{2k}-1\) somehow out of the exression \(3^{2(k+1)}-1\) so that you can use the "induction hypothesis" of the term \(3^{2k}-1\)

    • one year ago
  13. hash.nuke Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Ley 8x = 3^(2k) - 1 3^(2(k+1)) - 1 = 9 ( (3^(2k) - 1) + 1) - 1 = 9( 8x + 1 ) - 1 = 9*8x + 8 <-- hence it is divisible by 8

    • one year ago
  14. Mimi_x3 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    \[k = n\] \[3^{2n} - 1 = 8Q (where ~Q~ is~ any~ integer) => 3^{2n} = 8Q+1\] \[k= n+1 \] \[3^{2(n+1)} - 1 => 3^{2n+1} - 1 => 3^{2n} *3 - 1 => \left(8Q+1\right) *3 -1\]

    • one year ago
  15. RaphaelFilgueiras Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    • one year ago
    1 Attachment
  16. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    \[3^{2(k+1)}-1=3^{2k+2}-1=3^{2k}3^2-1=9\times 3^{2k}-1\] \[=(3^{2k}-1)\times 9+8\]

    • one year ago
  17. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    by induction, the terms \(3^{2k}-1\) is divisible by \(8\) and clearly \(9\times 8\) is divisible by \(8\) so the sum is divisible by \(8\)

    • one year ago
  18. PhoenixFire Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Okay, I now understand, however I have one question... Where the heck did the +8 come from? You have \[(9)3^{2k}-1\] how did that become \[9(3^{2k}-1)+8\] Actually, I understand @RaphaelFilgueiras Is it much different? @satellite73 or am I just missing something in the working.

    • one year ago
  19. RaphaelFilgueiras Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    3²-1

    • one year ago
  20. PhoenixFire Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks everyone! I've got it now.

    • one year ago
  21. hash.nuke Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    3^(2k) = (3^(2k) - 1) + 1 <--- 8 comes from here

    • one year ago
  22. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    it is a trick of algebra, and the reason to use the trick is to make sure you can get \(3^{2k}-1\) out of \(3^{2k+2}-1\) so you can use the induction hypothesis that is how i arrived at it to being with i just wrote \(3^{2k}\times 9-1\) and forced \(3^{2k}-1\) out of it

    • one year ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.