Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

PhoenixFire

  • 3 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
    • 3 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
    • 3 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
    • 3 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
    • 3 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
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Okay, I understand that. Now what?

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

    i don't see short sweet method.

  8. hash.nuke
    • 3 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. anonymous
    • 3 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. anonymous
    • 3 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
    • 3 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. anonymous
    • 3 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
    • 3 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
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    1 Attachment
  16. anonymous
    • 3 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. anonymous
    • 3 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
    • 3 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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    3²-1

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

    Thanks everyone! I've got it now.

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

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

  22. anonymous
    • 3 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

Sign Up
Find more explanations on OpenStudy
Privacy Policy