## PhoenixFire 3 years ago Using mathematical induction prove that for ${n \ge 1} \in \mathbb{Z}$ $3^{2k}-1$ is divisible by 8.

1. hash.nuke

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

2. PhoenixFire

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

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

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

5. hash.nuke

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

Okay, I understand that. Now what?

7. hash.nuke

i don't see short sweet method.

8. hash.nuke

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

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

10. satellite73

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^(2(k+1)) - 1 = 9(3^(2k) - 1) + 1) - 1 = 9(x+1) - 1 = 9*8x + 8 which is divisible by 8

12. satellite73

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

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

$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

16. satellite73

$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

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

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²-1

20. PhoenixFire

Thanks everyone! I've got it now.

21. hash.nuke

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

22. satellite73

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