Difference between revisions of "Proof by contrapositive"
(link) |
(category) |
||
| Line 1: | Line 1: | ||
'''Proof by contrapositive''' is a method of [[proof writing|proof]] 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. | '''Proof by contrapositive''' is a method of [[proof writing|proof]] 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. | ||
| − | == | + | ==Problems== |
| − | === | + | ===Introductory=== |
| − | + | *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]]. | |
| − | 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 | The contrapositive of this is | ||
| Line 13: | Line 11: | ||
So we assume <math>x</math> and <math>y</math> have opposite parity. Since one of these integers is even and the other odd, there is no loss of generality to suppose <math>x</math> is even and <math>y</math> is odd. Thus, there are integers <math>k</math> and <math>m</math> for which <math>x = 2k</math> and <math>y = 2m+1</math>. Now then, we compute the sum <math>x+y = 2k + 2m + 1 = 2(k+m) + 1</math>, which is an odd integer by definition. | So we assume <math>x</math> and <math>y</math> have opposite parity. Since one of these integers is even and the other odd, there is no loss of generality to suppose <math>x</math> is even and <math>y</math> is odd. Thus, there are integers <math>k</math> and <math>m</math> for which <math>x = 2k</math> and <math>y = 2m+1</math>. Now then, we compute the sum <math>x+y = 2k + 2m + 1 = 2(k+m) + 1</math>, which is an odd integer by definition. | ||
| − | + | *Show that if <math>n^2</math> is an odd integer, then <math>n</math> is odd. | |
| − | |||
| − | Show that if <math>n^2</math> is an odd integer, then <math>n</math> is odd. | ||
====Solution==== | ====Solution==== | ||
Suppose <math>n</math> is an even integer. Then there exists and integer <math>w</math> such that <math>n = 2w</math>. Thus <math>n^2 = (2w)^2 = 4w^2 = 2(2w^2)</math>. Since <math>2w^2</math> is an integer, <math>n^2</math> is even. Therefore <math>n^2</math> is not odd. | Suppose <math>n</math> is an even integer. Then there exists and integer <math>w</math> such that <math>n = 2w</math>. Thus <math>n^2 = (2w)^2 = 4w^2 = 2(2w^2)</math>. Since <math>2w^2</math> is an integer, <math>n^2</math> is even. Therefore <math>n^2</math> is not odd. | ||
| + | ===Intermediate=== | ||
| + | ===Olympiad=== | ||
| + | |||
| + | [[Category:Proofs]] | ||
Revision as of 22:11, 13 December 2007
Proof by contrapositive is a method of proof 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.
Problems
Introductory
- Show that if
and 
are two integers for which 
is even, then and have the same parity.
is even, then Solution
The contrapositive of this is
- If and are two integers with opposite parity, then their sum must be odd.
So we assume 
and 
have opposite parity. Since one of these integers is even and the other odd, there is no loss of generality to suppose is even and is odd. Thus, there are integers 
and 
for which 
and 
. Now then, we compute the sum 
, which is an odd integer by definition.
- Show that if
is an odd integer, then 
is odd.
Solution
Suppose 
is an even integer. Then there exists and integer 
such that 
. Thus 
. Since 
is an integer, 
is even. Therefore is not odd.
