Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Proof by contrapositive"

(→‎Solution: oddness)
m (→‎Solution)
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
'''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.
+
'''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.
  
−
==Examples==
+
==Problems==
−
===Parity===
+
===Introductory===
−
====Problem====
+
*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 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.
+
===Solution===
−
====Solution====
 
 
The contrapositive of this is  
 
The contrapositive of this is  
−
If <math>x</math> and <math>y</math> are two integers with opposite parity, then their sum must be odd.  
+
 
 +
:If <math>x</math> and <math>y</math> are two integers with opposite parity, then their sum must be odd.  
 +
 
 
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.  
−
===Odd Squares===
+
 
−
====Problem====
+
*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 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===
 +
===Olympiad===
 +
 
 +
[[Category:Proofs]]

Latest revision as of 16: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 $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.

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

Solution

Suppose $n$ is an even integer. Then there exists an 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.

Intermediate

Olympiad

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Proof_by_contrapositive&oldid=32866"