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.
 2 years ago
 2 years ago
PhoenixFire Group Title
Using mathematical induction prove that for \[ {n \ge 1} \in \mathbb{Z} \] \[ 3^{2k}1 \] is divisible by 8.
 2 years ago
 2 years 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
 2 years 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.
 2 years 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.
 2 years 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.
 2 years 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
 2 years ago

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

hash.nuke Group TitleBest ResponseYou've already chosen the best response.0
i don't see short sweet method.
 2 years 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 ...
 2 years 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
 2 years 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
 2 years 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
 2 years 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\)
 2 years 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
 2 years 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\]
 2 years 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\]
 2 years 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\)
 2 years 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.
 2 years ago

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

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

hash.nuke Group TitleBest ResponseYou've already chosen the best response.0
3^(2k) = (3^(2k)  1) + 1 < 8 comes from here
 2 years 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
 2 years 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.