Using Proof by Contradiction

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

If n is not even, then $n$ and $n^3$ are odd, and $n^3+1$ is even (odd+odd=even). Contradiction.

Answer 4

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.

Answer 5

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