6
$\begingroup$

Prove the following statement by proving its contrapositive:

“If $n^3 + 2n + 1$ is odd then n is even”

Therefore: $\lnot q \rightarrow \lnot p =$ "if $n^3 + 2n + 1$ is even then $n$ is odd.

So for this I began assuming that: $n=2k+1$

$(2k+1)^3 +2(2k+1)+1 = 8k^3+12k^2 +10k+4 = 2k(4k^2 +6k+5)+4$

The last statement: $2k$ is even, therefore $2k(4k^2 -6k+5)$ is also even and 4 is $2\cdot 2$ which is also even.

Now, my question is, when proving the contrapositive, what's your final conclusion? If it works for the contrapositive, then your theorem holds? Or is there something else?

$\endgroup$

3 Answers 3

2
$\begingroup$

Let p be the boolean value for the statement "$n^3+2^n+1$ is odd", q be the boolean value for "n is even". $$p \rightarrow q$$ $$1 \rightarrow 1$$ $$0 \rightarrow 1$$ $$0 \rightarrow 0$$ (as you can see, only $1 \rightarrow 0$ will indicate $p \rightarrow q$ is false)

The contrapositive of $p \rightarrow q$ is $\lnot q \rightarrow \lnot p$, which is "if n is not even, $n^3+2^n+1$ is not odd."

The statement "if $n^3+2n+1$ is even then n is odd" is implying $\lnot p \rightarrow \lnot q$ and it is not equivalent to $p → q$. $$¬p → ¬q$$ $$¬0 → ¬0$$ $$¬1 → ¬0$$ $$¬1 → ¬1$$

($\lnot p \rightarrow \lnot q$ will still be valid when $p=1$ and $q=0$, which is not the case in $p \rightarrow q$)


If it works for the contrapositive, your statement definitely holds.

The statements $p \rightarrow q$ and $\lnot q \rightarrow \lnot p$ are logically equivalent.

$\endgroup$
1
  • $\begingroup$ Interesting. I wonder why I get downvoted. $\endgroup$ Oct 16, 2014 at 8:55
1
$\begingroup$

You don't have the contrapositive correct: It should be "If $n$ is odd, then $n^3 + 2n + 1$ is even." You seem to have argued, however, from the assumption that $n$ is odd.

Now the conclusion of your argument is that $n^3 + 2n + 1$ is even; hence, what you've proven can be summarized as

$$n \text{ odd} \implies n^3 + 2n + 1 \text{ even}$$

By contraposition, this is logically equivalent to

$$n^3 + 2n + 1 \text{ odd} \implies n \text{ even}$$

and you're finished.

$\endgroup$
3
  • $\begingroup$ So apart from the contrapositive statement being incorrect, were the steps I took to prove the statement correct? $\endgroup$
    – Dimitri
    Sep 8, 2013 at 0:49
  • $\begingroup$ @Dimitri Yes, it's fine, albeit a bit convoluted. It's easier to just factor a $2$ out of the given expression, rather than break it up into multiple pieces. $\endgroup$
    – user61527
    Sep 8, 2013 at 0:57
  • $\begingroup$ You're absolutely right. I seem to have done that in previous proofs as well... Thanks!! $\endgroup$
    – Dimitri
    Sep 8, 2013 at 1:02
0
$\begingroup$

$\displaystyle n^3+2n+1=n^3-n^2+n^2+n+n+1$

$=n^2(n-1)+n(n+1)+n+1\equiv n+1\pmod2$ as the product of any two consecutive integer is divisible by $2$

$\implies n^3+2n+1$ and $n$ has opposite parity

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .