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.
Asked
Active
Viewed 162 times
3
-
Please remember that you can choose an aswer among the given if the OP is solved, more details here https://meta.stackexchange.com/questions/5234/how-does-accepting-an-answer-work – user Mar 12 '18 at 23:33
5 Answers
3
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.
Siong Thye Goh
- 149,520
- 20
- 88
- 149
-
So,
n = 2k+1 n³+1 is odd
(2k+1)³+1 = 2k³+1+1 = 2k³+2 This means that if k is even then the equation n³+1 would be even, right?
– Jacob McCullough Mar 08 '18 at 08:31 -
1
-
-
$(2k+1)^3=(2k)^3+3(2k)^2+33(2k)+1$ by Binomial Theorem. Mauro is right. Somehow I just check that it is even. – Siong Thye Goh Mar 08 '18 at 18:32
2
If n is not even, then $n$ and $n^3$ are odd, and $n^3+1$ is even (odd+odd=even). Contradiction.
alans
- 6,475
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.
Mauro ALLEGRANZA
- 94,169
-
So,
n = 2k+1 n³+1 is odd
(2k+1)³+1 = 2k³+1+1 = 2k³+2 This means that if k is even then the equation n³+1 would be even, right?
– Jacob McCullough Mar 08 '18 at 08:37 -
1@JacobMcCullough - right conclusion with the wrong proof... The cube of the binomial is : $(a+b)^3=(a^3+3a^2b +3ab^2+b^3)$. – Mauro ALLEGRANZA Mar 08 '18 at 08:49
-
So is it (2k+1)³ = (2k³+3k²(1)+3k(1)²+(1)³)+1 = (2k³+3k²+3k)+1 – Jacob McCullough Mar 08 '18 at 08:56
-
It must be: $[(2k)^3+3(2k)^2+3(2k)+1^3]+1=2^3(k^3)+2^2(3k^2)+2(3k)+(1+1)$. All terms have a factor $2$ and thus they are all even. – Mauro ALLEGRANZA Mar 08 '18 at 09:09
-
Ok I see. I was not carrying the 2k over with every term. Thank you for clearing that up. I also now see that every term has a 2 in it, so it is even. – Jacob McCullough Mar 08 '18 at 18:44
1
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.
user
- 154,566
-
So,
n = 2k+1 n³+1 is odd
(2k+1)³+1 = 2k³+1+1 = 2k³+2 This means that if k is even then the equation n³+1 would be even, right?
– Jacob McCullough Mar 08 '18 at 08:39 -
Yes thus the negation is false and then the original statement is true. It is important that you get the logical framework which is a powerful tool for many proofs. – user Mar 08 '18 at 08:42
-
1
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)$.
lhf
- 216,483