Discrete Math Induction Proof Prove that 2^n + (-1)^(n+1) is divisible by 3 for n>0

[RighteousRhino]

Discrete Math Induction Proof Prove that 2^n + (-1)^(n+1) is divisible by 3 for n>0

Prove that 2^n + (-1)^(n+1) is divisible by 3 for all positive integers (n>0) using induction or strong induction.

My attempt using induction:

Base case: n = 1: 2^1 + (-1)^(1+1) = 2 +1 = 3 and 3 is divisible by 3.

inductive step: Assume that for any k > 0 2^k + (-1)^(k+1) is divisible by 3, we must prove that 2^(k+1) + (-1)^(k+1+1) is divisible by 3.

2^(k+1) + (-1)^(k+1+1) = 2*2^k + (-1)^(1) * (-1)^(k+1) = 2*2^k - (-1)^(k+1)

This is where i get stuck... if it wasn't for that 2 and the minus sign I could relate it to the initial assumption.

Any help would be greatly appreciated.

 

[ksdhart]

Umm, Denis, what you said is not true. The function is 2^n + (-1)^(n+1). If I plug in n = 2, I get 2^2 + (-1)^3 = 4 - 1 = 3. And n=3: 2^3 + (-1)^4 = 8 + 1 = 9. And both of those are divisible by 3.

As for the proof, this is how I'd begin. The goal is to prove that 2^(k+1) + (-1)^([k+1]+1) is divisible by 3. So I'll rewrite the equation:

2^(k+1) + (-1)^(k+2)

Now I'm going to apply a special property of powers of negative one. Can you see why this is always true, no matter the value of k?

(-1)^(k+2) = (-1)^k

Try continuing on from there. I believe you are very close to the proof after this step.

 

[Ishuda]

Prove that 2^n + (-1)^(n+1) is divisible by 3 for all positive integers (n>0) using induction or strong induction.

My attempt using induction:

Base case: n = 1: 2^1 + (-1)^(1+1) = 2 +1 = 3 and 3 is divisible by 3.

inductive step: Assume that for any k > 0 2^k + (-1)^(k+1) is divisible by 3, we must prove that 2^(k+1) + (-1)^(k+1+1) is divisible by 3.

2^(k+1) + (-1)^(k+1+1) = 2*2^k + (-1)^(1) * (-1)^(k+1) = 2*2^k - (-1)^(k+1)

This is where i get stuck... if it wasn't for that 2 and the minus sign I could relate it to the initial assumption.

Any help would be greatly appreciated.

What would happen if you added and subtracted 2(-1)^k+1 and rearranged terms?