Quantcast

A community for students. Sign up today!

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

PhoenixFire

  • 2 years ago

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

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

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

  2. PhoenixFire
    • 2 years ago
    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.

  3. PhoenixFire
    • 2 years ago
    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.

  4. hash.nuke
    • 2 years ago
    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.

  5. hash.nuke
    • 2 years ago
    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

  6. PhoenixFire
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Okay, I understand that. Now what?

  7. hash.nuke
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i don't see short sweet method.

  8. hash.nuke
    • 2 years ago
    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 ...

  9. satellite73
    • 2 years ago
    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

  10. satellite73
    • 2 years ago
    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

  11. hash.nuke
    • 2 years ago
    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

  12. satellite73
    • 2 years ago
    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\)

  13. hash.nuke
    • 2 years ago
    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

  14. Mimi_x3
    • 2 years ago
    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\]

  15. RaphaelFilgueiras
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    1 Attachment
  16. satellite73
    • 2 years ago
    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\]

  17. satellite73
    • 2 years ago
    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\)

  18. PhoenixFire
    • 2 years ago
    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.

  19. RaphaelFilgueiras
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    3²-1

  20. PhoenixFire
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks everyone! I've got it now.

  21. hash.nuke
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  22. satellite73
    • 2 years ago
    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

  23. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Ask a Question
Find more explanations on OpenStudy

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.