Using Proof by Contradiction Use a proof by contradiction to show that if $n^3 + 1$ is odd, then $n$ is even for all integer $n$.
Given: $n^3 + 1$ is odd
Assume: $n$ is not even
I'm not sure where to go from here to prove this by contradiction.
 A: Guide:
Suppose $n$ is not even, then it is odd. So you can express it as $n=2k+1$, now substitute this into $n^3+1$ to look for a contradiction.
If you know modulo arithmetic, the proof can be shorter.
A: If n is not even, then $n$ and $n^3$ are odd, and $n^3+1$ is even (odd+odd=even). Contradiction.
A: The proof by contradiction works this way.
Assume the negation of the sought conclusion; in your case, assume: 

$n$ is not even,

and derive a contradiction, i.e. derive a consequence contradicting the premise, in your case: $n^3+1$ is odd, or some other known fact.
A brute force check is: $n$ not even, i.e. odd, means $n=2k+1$, for some $k$.
Now compute $n^3+1=(2k+1)^3+1$ and find the contradiction with the premise.
A: Some detail more to better understand, not only intuitivelly why it works in general.
Note that from the logical point of view we are given


*

*$n^3+1$ odd $\implies n$ even


which is equivalent to


*

*$n^3+1$ even $\lor \, n$ even


thus the negation is


*

*$n^3+1$ odd $\land \, n$ odd


The proof by contradiction is made on the last showing that it is false from which follows that the original statement is true.
A: Why use contradiction, when using the contrapositive is so clear?
We want to prove

If $n^3+1$ is odd, then $n$ is even

The contrapositive is

If $n$ is not even, then $n^3+1$ is not odd

or, equivalently, 

If $n$ is odd, then $n^3+1$ is even

And this is clear because $n=2m+1$ implies $n^3+1=8 m^3 + 12 m^2 + 6 m + 2
$, an even number.
Nevertheless, a direct proof is also easy and can be based on $n^3+1 = (n+1)(n^2-n+1)$. 
