4

I am just trying to understand proofs by the contrapositive method. I do know that the contrastive method is taking the negation of the second argument implies the negation of the first argument.

For example: Show that the square of an even number is an even number using contrapositive proofs.

I don't know how to even begin! I know that we have to prove that if a number is odd, then the square of that number is odd.

But how can i put that in a proof form?

Sentrl
  • 311
  • 1
    No, you need to show that if the square of a number is odd, then the number itself is odd also. (This seems like a bad idea to me, proving it directly is more natural.) – fkraiem Feb 09 '14 at 17:53
  • Agree with fkraiem. This example is much better off done directly. A slight tweak should make it more convenient to use a contrapositive argument: Show that if the square of a number is even, the number is even. Then the contrapositive is to show that if a number is odd, the square of it is odd. (Hint: consider the characterization of odd numbers $n=2k+1$) – Kelvin Soh Feb 09 '14 at 18:06

2 Answers2

3

If the original statement is "if $P$, then $Q$," then the contrapositive statement is "If not $Q$, then not $P$." So, in your case, the original claim reads, "If $n$ is even, then $n^2$ is also even." The contrapositive would then read, "If $n^2$ is not even, then $n$ is not even," or equivalently (since if a number is not even, it is odd): "If $n^2$ is odd, then $n$ is odd." Let's prove this. If $n^2$ is odd, then $n^2 = 2m + 1$ for some (nonnegative) integer $m$. Then $2m = n^2 - 1 = (n-1)(n+1)$. But since the LHS is even, so must be the right. But $n-1$ and $n+1$ share the same parity--i.e., they are either both odd or both even. Since an odd number times an odd number is odd, it follows that $n-1$ is even, hence $n$ itself is odd.

It's an unnecessarily complicated proof, of course--for the direct proof is that if $n$ is even, then $n = 2m$ for some integer $m$, hence $n^2 = (2m)^2 = 4m^2$ which is obviously even.

heropup
  • 135,869
  • That's not the question the OP asked. The contrapositive statement he needs to prove is that if a number is odd then its square is odd, as he stated. – Mikhail Katz Feb 09 '14 at 18:17
  • It IS the question the OP asked. I quote: "For example: Show that the square of an even number is an even number using contrapositive proofs." This is EXACTLY what I did. You are doing something based on the OP's incorrect formulation of the contrapositive of the FIRST statement. – heropup Feb 09 '14 at 18:19
  • I think we are in agreement that his question contained a logical error. This is what we should be pointing out to him. – Mikhail Katz Feb 09 '14 at 18:31
0

There is an inaccuracy in your formulation of the problem. The contrapositive of $A\implies B$ is $\text{not}(B)\implies\text{not}(A)$ rather than the other way around. Thus, proving that "if $n$ is odd then $n^2$ is odd" is contrapositive of the statement that "if the square of a number is even then the number itself is even" rather than the statement you cited.

To show the contrapositive, assume $n$ is odd so that $n=2k+1$. Then $n^2=4k^2+2k+1$ and therefore also odd, q.e.d.

Mikhail Katz
  • 42,112
  • 3
  • 66
  • 131
  • No, that is not correct. The original statement is, "if $n$ is even, then $n^2$ is even." The contrapositive is then "if $n^2$ is odd, then $n$ is odd." Your proof is for the statement "if $n$ is odd, then $n^2$ is odd." – heropup Feb 09 '14 at 18:11
  • The statement I proved is the statement Sentrl formulated in his question: "I know that we have to prove that if a number is odd, then the square of that number is odd." This is the contrapositive of "if $n^2$ is even then $n$ is even". – Mikhail Katz Feb 09 '14 at 18:15
  • Read the OP's post again: "For example: Show that the square of an even number is an even number using contrapositive proofs." – heropup Feb 09 '14 at 18:24
  • Right. There is a logical error in his formulation of the question, as I mentioned in my answer. – Mikhail Katz Feb 09 '14 at 18:31