6

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?

Dimitri
  • 1,287

3 Answers3

2

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.

Archy Will He 何魏奇
  • 883
1

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.

  • So apart from the contrapositive statement being incorrect, were the steps I took to prove the statement correct? – Dimitri Sep 08 '13 at 00:49
  • @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. –  Sep 08 '13 at 00:57
  • You're absolutely right. I seem to have done that in previous proofs as well... Thanks!! – Dimitri Sep 08 '13 at 01:02
0

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

lab bhattacharjee
  • 274,582