I know this is trivial with direct proofs, but how would one go about proving:
For every integer n, n^3 + n is even
using contraposition? I'm a little rusty on how to properly use contrapositive proofs. I know that if given $P \Longrightarrow Q$, the contrapositive is $\neg Q\Longrightarrow \neg P$.
So to prove via contraposition, assume $\neg Q$ is true and if $\neg P$ logically follows, then we have shown $P \Longrightarrow Q$.
$Q$ or $\neg Q$ is trivial, however, what is $P$ in this case?
Edit:
This was just out of curiosity in trying to figure out ways to prove this indirectly.
Best Answer
Over-View :
I have given a way to generate the Contra-Positive , then I have suggested a way to Prove that.
That Proof is long & Cumbersome , hence I have suggested a variation with a slight alteration , which gives a Simple Proof By Contra-Positive.
Statement given is like this ( With $Z$ = Integral Numbers ) :
$P_1$ : $\forall n \in Z : Even(n^3+n)$
It has no Implication , hence Contra-Positive will not arise.
We have to make it with Implication to get a Contra-Positive. Doing that requires using a larger Universal Set ( Eg With $Q$ = Rational Numbers & With $R$ = Real Numbers ) .
These 2 will work :
$P_2$ : $\forall n \in Q : Integer(n) \implies Even(n^3+n)$
$P_3$ : $\forall n \in R : Integer(n) \implies Even(n^3+n)$
Then the Contra-Positives are :
$P_4$ : $\forall n \in Q : \lnot Even(n^3+n) \implies \lnot Integer(n)$
$P_5$ : $\forall n \in R : \lnot Even(n^3+n) \implies \lnot Integer(n)$
Proof By Contra-Positive :
When $n^3+n$ is not Even , we have $n^3+n=2m+1$ which has the Unique Solution (real) given by Wolfram :
Problem now becomes showing that $N$ is not Integer , no matter what Integer $M$ is.
That can be done , though it require too much unnecessary work.
Thus Proof By Contra-Positive is too Cumbersome here.
Direct Proof is much Easier !
Now , it is your Curiosity to try this type of Proof , hence we can make it easier to go forward by considering this :
$P_6$ : $\forall n \in R : Integer(n) \implies Even(n^2+n)$
The Contra-Positive is :
$P_7$ : $\forall n \in R : \lnot Even(n^2+n) \implies \lnot Integer(n)$
When $n^2+n$ is not Even , we have $n^2+n=2m+1$ , which gives :
$n=\frac{-1 \pm \sqrt{1+4(2m+1)}}{2}$
$n=\frac{-1 \pm \sqrt{1+8m+4}}{2}$
$n=\frac{-1 \pm \sqrt{8m+5}}{2}$
No matter what $m$ is , $8m+5$ is not a Square ( It is easy to check that $S^2 \equiv 1 \mod 8$ & $S^2 \not \equiv 5 \mod 8$ ) , hence $n$ is irrational , not Integer !
We have the Proof By Contra-Positive here !
Direct Proof will work Easier too.