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

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?

• looks fine to me – eyeballfrog Oct 31 '19 at 16:30
• I agree. The proof is overall well set and developed. Make sure you write an appropriate conclusion aligned with the inductive reasoning applied. – Fede1 Oct 31 '19 at 16:37
• Yep just skipped that cause I'm too lazy – Mehul Jangir Oct 31 '19 at 16:38
• Welcome to Mathematics Stack Exchange. You could prove by induction that $2$ divides $2^n$. Then $2$ divides ${{2^n-(-1)^n}\over {3}}$ would imply $2$ divides $2^n-(-1)^n$, which would imply $2$ divides $(-1)^n,$ a contradiction – J. W. Tanner Oct 31 '19 at 16:40
• It's correct but there's just a minor detail: in the second line where you say $[\ldots ]= 2A+1 \text{ where } A\in\mathbb{Z}^+$, it should be $A\in \mathbb{Z}_{\geq 0}$ because $2A+1$ could be one, i.e, $A$ could be $0$. – bjorn93 Oct 31 '19 at 16:45

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}$$

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$$.

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.

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.