Difference between revisions of "Proof by contrapositive"
(category) |
5849206328x (talk | contribs) m (→Solution) |
||
Line 13: | Line 13: | ||
*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 | + | Suppose <math>n</math> is an even integer. Then there exists an 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=== | ===Intermediate=== | ||
===Olympiad=== | ===Olympiad=== | ||
[[Category:Proofs]] | [[Category:Proofs]] |
Latest revision as of 17:31, 21 October 2009
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.
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 an integer
such that
. Thus
. Since
is an integer,
is even. Therefore
is not odd.