Proving that $ { {2^n - (-1)^n} \over {3} } $ is an odd number for all $n\ge1$

Question

This is a problem from Mathematics Analyses and Approaches HL (IB). Do note that this is not homework or any sort of submission, I'm doing it merely out of interest. I need to prove the following conjecture using the principle of mathematical induction:

$$ {{2^n-(-1)^n}\over {3}} \; \text{is an odd number for all} \; n \in Z^+ $$

And here is my proof:

$$ \text{If} \; n=1, \; {{2^1-(-1)^1}\over {3}} = 1, \; \therefore P_1 \; \text{is true} $$

$$ \text{If} \; P_k \; \text{is true}, \; {{2^k-(-1)^k}\over {3}} = 2A+1 \; \text{where A} \in Z $$

$$ \text{And now,} \; {{2^{k+1}-(-1)^{k+1}}\over {3}} \implies {2({2^k)+(-1)^k}\over {3}} $$

$$ \text{from} \; P_k, \; 2^k = 6A + 3+(-1)^k $$

$$ \implies {2({6A + 3+(-1)^k)+(-1)^k}\over {3}} $$

$$ \implies {{12A+6+3(-1)^k}\over {3}} $$

$$ \implies 4A+2+(-1)^k $$

$$ \implies 2(2A+1)+(-1)^k $$

Now, my reasoning here is that two times any integer always gives an even number. We know that $2A+1$ is an integer, so $2(2A+1)$ has to be even. Now, any subtracting 1 from or adding 1 to any even number gives an odd number. As $2(2A+1)$ is even, $2(2A+1)+(-1)^k$ has to be odd.

Is this proof correct? Anything I should do differently or elaborate on?

Answer 1

Yes it is absolutely fine, as an alternative by exhaustion we have for $n=2k$

$${{2^n-(-1)^n}\over {3}}={{2^{2k}-1}\over {3}}\implies \frac{2^{2k}-1}{3}+1=\frac{2^{2k}+2}{3}=2\frac{2^{2k-1}+1}{3}$$

and for $n=2k+1$

$${{2^n-(-1)^n}\over {3}}={{2^{2k+1}+1}\over {3}}\implies \frac{2^{2k+1}+1}{3}+1=\frac{2^{2k}+4}{3}=2\frac{2^{2k}+1}{3}$$

Answer 2

I find your proof really good and simple, while my proof is pretty rough - This is what I got so far:

Using this formula (click here)(under difference of odd exponents), you can factorise the top to get -

$((2-(-1))(2^{n-1} +2^{n-2}(-1) +2^{n-3}(-1)^2+2^{n-4}(-1)^3 ...+2^0(-1)^{n-1}))/3$

The first bracket will evaluate to 3, which divided by 3 is 1 (cancelling the 3), while the the other bracket is the sum of even powers of 2 (for k being and integer, which it is).

The final term of that bracket will be either a 1 or -1 and as the rest is even, the whole bracket will be odd (of the form 2a +- 1)

I think this proof is less definitive but simpler to understand (kinda). Tell me what you think of it.

Answer 3

Equivalently, we can prove that $2^n-(-1)^n=3(2m+1)\equiv3\mod6$.

Indeed, $2^n\bmod6=2,4,2,4,2,\cdots$ to which you add or subtract $1$.

Answer 4

Your proof's fine. Interestingly, we don't need induction at all. If $n\ge1$,$$\frac{\frac{2^n-(-1)^n}{3}-1}{2}=\frac{2^n-(-1)^n-3}{6}.$$The numerator is both even (though not if $n=0$) and a multiple of $3$ (since $3|2-(-1)$), so is a multiple of $6$, and so the expression is an integer. (OK, I lied a little: the proof that $m|a-b\implies m|a^n-b^n$ uses induction.) This proves $\frac{2^n-(-1)^n}{3}$ is odd.