Difference between revisions of "Proof by contrapositive"

Revision as of 20:49, 22 October 2007

Proof by contrapositive is a method of prove in which the contrapositive of the desired statement is proven, and thus it follows that the original statement is true. Generally, this form is only used when it is impossible to prove the original statement directly.

Examples

Parity

Problem

Show that if $x$ and $y$ are two integers for which $x+y$ is even, then $x$ and $y$ have the same parity.

Solution

The contrapositive of this is

If $x$ and $y$ are two integers with opposite parity, then their sum must be odd.

So we assume $x$ and $y$ have opposite parity. Since one of these integers is even and the other odd, there is no loss of generality to suppose $x$ is even and $y$ is odd. Thus, there are integers $k$ and $m$ for which $x = 2k$ and $y = 2m+1$ . Now then, we compute the sum $x+y = 2k + 2m + 1 = 2(k+m) + 1$ , which is an odd integer by definition.

Odd Squares

Problem

Show that if $n^2$ is an odd integer, then $n$ is odd.

Solution

Suppose $n$ is an even integer. Then there exists and integer $w$ such that $n = 2w$ . Thus $n^2 = (2w)^2 = 4w^2 = 2(2w^2)$ . Since $2w^2$ is an integer, $n^2$ is even. Therefore $n^2$ is not odd.

@@ Line 4: / Line 4: @@
 ===Parity===
 ====Problem====
-Show that tf <math>x</math> and <math>y</math> are two integers for which <math>x+y</math> is even, then <math>x</math> and <math>y</math> have the same [[parity]].
+Show that if <math>x</math> and <math>y</math> are two integers for which <math>x+y</math> is even, then <math>x</math> and <math>y</math> have the same [[parity]].
 ====Solution====
 The contrapositive of this is

Page

Toolbox

Search

Difference between revisions of "Proof by contrapositive"

Revision as of 20:49, 22 October 2007

Contents

Examples

Parity

Problem

Solution

Odd Squares

Problem

Solution