4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ looks fine to me $\endgroup$ – eyeballfrog Oct 31 '19 at 16:30
  • $\begingroup$ I agree. The proof is overall well set and developed. Make sure you write an appropriate conclusion aligned with the inductive reasoning applied. $\endgroup$ – Fede1 Oct 31 '19 at 16:37
  • $\begingroup$ Yep just skipped that cause I'm too lazy $\endgroup$ – Mehul Jangir Oct 31 '19 at 16:38
  • $\begingroup$ 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 $\endgroup$ – J. W. Tanner Oct 31 '19 at 16:40
  • $\begingroup$ 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$. $\endgroup$ – bjorn93 Oct 31 '19 at 16:45
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.