Got Homework?
Connect with other students for help. It's a free community.
Here's the question you clicked on:
 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
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

hash.nuke Group TitleBest ResponseYou've already chosen the best response.0
show it for certain number n ... show it hods for n+1
 one year ago

PhoenixFire Group TitleBest ResponseYou've already chosen the best response.0
Yeah I got the base step. n=1 \[3^21=8k\] where k is some Integer. \[8=8k\] so it's divisible.
 one year ago

PhoenixFire Group TitleBest ResponseYou've already chosen the best response.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

hash.nuke Group TitleBest ResponseYou've already chosen the best response.0
this is difficult. let's try without induction first. you have to show that there is 3 even factors.
 one year ago

hash.nuke Group TitleBest ResponseYou've already chosen the best response.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

PhoenixFire Group TitleBest ResponseYou've already chosen the best response.0
Okay, I understand that. Now what?
 one year ago

hash.nuke Group TitleBest ResponseYou've already chosen the best response.0
i don't see short sweet method.
 one year ago

hash.nuke Group TitleBest ResponseYou've already chosen the best response.0
Prove ... if (3^k  1) is divisible by 2 prove (3^k + 1) is always divisible by 4 using induction. and viceversa ...
 one year ago

satellite73 Group TitleBest ResponseYou've already chosen the best response.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

satellite73 Group TitleBest ResponseYou've already chosen the best response.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

hash.nuke Group TitleBest ResponseYou've already chosen the best response.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

satellite73 Group TitleBest ResponseYou've already chosen the best response.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

hash.nuke Group TitleBest ResponseYou've already chosen the best response.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

Mimi_x3 Group TitleBest ResponseYou've already chosen the best response.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

satellite73 Group TitleBest ResponseYou've already chosen the best response.0
\[3^{2(k+1)}1=3^{2k+2}1=3^{2k}3^21=9\times 3^{2k}1\] \[=(3^{2k}1)\times 9+8\]
 one year ago

satellite73 Group TitleBest ResponseYou've already chosen the best response.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

PhoenixFire Group TitleBest ResponseYou've already chosen the best response.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

RaphaelFilgueiras Group TitleBest ResponseYou've already chosen the best response.2
3²1
 one year ago

PhoenixFire Group TitleBest ResponseYou've already chosen the best response.0
Thanks everyone! I've got it now.
 one year ago

hash.nuke Group TitleBest ResponseYou've already chosen the best response.0
3^(2k) = (3^(2k)  1) + 1 < 8 comes from here
 one year ago

satellite73 Group TitleBest ResponseYou've already chosen the best response.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 91\) and forced \(3^{2k}1\) out of it
 one year ago
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
 Engagement 19 Mad Hatter
 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.