/sci/ - Science & Math

>>9951907
What have you tried?
Do you even know what induction is?

>>9951915
yes i do. But so far ive only done it for questions that involve one side equaling another. So i dont know where to start when the criteria is that it must be divisible by 2

>>9951907
>Prove by induction
Found your problem senpai

Base case:
3^1-1=2, which is divisible by itself

Induction step:
Assume for some n, 2|3^n-1
Show that 2|3^(n+1)-1
3^(n+1)-1 can be rewritten as 3*(3^n)-1, or alternatively as (3^n-1)+3^n+3^n.
Since it is established that 3^n-1 is divisible by 2, it can be rewritten as 2a, for some integer a.

Case 1: 3^n is even
If this is the case, 3^n can be rewritten as 2b, for some integer b. 3^n+3^n is therefore equivalent to 2b+2b, which is equal to 2(2b). Since 2b is an integer, 2 divides 3^n+3^n. Rewriting the entire expression, 2a+2b+2b = 2(a+b^2), and is therefore divisible by 2.

Case 2: 3^n is odd.
3^n+3^n can therefore be rewritten as 2c+1+2c+1, for some integer c. This can be rewritten as 4c+2, or as 2(2c+1), and is therefore divisible by 2. Rewriting the entire expression, 2a+2(2c+1) = 2(a+2c+1), and is therefore divisible by 2.

>>9951932
>3^n is even
Did you think this case thoroughly? Looks good save for this

>>9951932
Why did you complicate the inductive step so much? Why can't it just be:
Assume 3^n - 1 is even.
3^(n+1)-1 = 3*(3^n) - 1
3^n - 1 = 2k for some k >= 0 => 3^n = 2k + 1
3*(3^n) - 1 = 3*(2k+1) - 1 = 6k + 3 - 1 = 6k + 2 = 2*(3k + 1)

>>9951936
Shit, I'm retarded. The initial induction and Case 2 still seem valid though.

>>9951939
This one is prettier.
[eqn] 2 | 3^{k} - 1 \implies 2 | 3^{k+1} - 3 \implies 2 | 3^{k+1} - 3 + 2 = 3^{k+1} - 1 [/eqn]

You guys know that 3^n is always odd right?

>>9952676
Yes. We also now 3^n-1 is always even but "it's a know fact that this is true" doesn't count as a proof.

Derpy. You can't even prove basic theorems on odd and even integers? I guess you would choose induction.

>>9953040
You can prove 3^n is always odd
Therefore 3^n-1 is even.

That would be a legitimate proof (but not by induction)

>>9953128
>That would be a legitimate proof (but not by induction)
Then why even bring this up?

>>9953192
Because I wasnt answering op, I was responding to anon.

Also, havent seen a proof for op that would result in full credit by my uni yet.

>>9953128
You'd have to use induction anyway to prove 3^n is always odd, but that might not be good enough for the teacher.

>>9953377
Why not prove that odd numbers are closed under products?

>>9953128
let n =2
3^2-1 = 3
contradiction

>>9953463
Shitty bait

>>9951907
1. Can you do the base case?
2. Can you figure out what you have to assume in the inductive case?

Assume 3^n = 2N where N is an integer
3^(n+1)-1
3*3^n-3+2
3(3^n-1)+2
3(2N)+2
2(3N+1)