Direct proof starts from the hypothesis and derives the conclusion. Some theorems are easier to prove indirectly. Indirect proof methods for theorems include proof by contraposition and proof by contradiction. These methods are valid because of logical equivalences involving implication and negation. In this lesson, indirect proof methods for theorems are used to prove parity results, product results, square results, and inequalities. :::definition[Direct Proof] A direct proof of an implication starts from the hypothesis and uses definitions, known results, and logical rules to derive the conclusion. For a theorem of the form $p\to q$, a direct proof assumes $p$ and proves $q$. ::: :::definition[Proof by Contraposition] A proof by contraposition proves an implication by proving its contrapositive. Since $p\to q$ is logically equivalent to $\neg q\to\neg p$, to prove $p\to q$, it is enough to prove $\neg q\to\neg p$. ::: :::definition[Proof by Contradiction] A proof by contradiction proves a statement by assuming its negation and deriving a contradiction. To prove an implication $p\to q$, one may assume $p\land\neg q$ and derive a contradiction. ::: :::definition[Contraposition and Contradiction Forms] For a theorem of the form $\forall m[p(m)\to q(m)]$, the two indirect methods have the following forms: $$\begin{equation*} \begin{array}{lll} \text{Contraposition} & \text{Assume }\neg q(m) & \text{derive }\neg p(m),\\ \text{Contradiction} & \text{Assume }p(m)\land\neg q(m) & \text{derive a contradiction.} \end{array} \end{equation*}$$ ::: :::theorem[Even Integer Plus Seven] Let $m$ be an integer. If $m$ is even, then $m+7$ is odd. ::: :::proof Given that $m$ is an integer. Given that $m$ is even. To prove that $m+7$ is odd. Since $m$ is even, there exists an integer $a$ such that $m=2a$. Then $$\begin{align*} m+7&=2a+7\\ &=2a+6+1\\ &=2(a+3)+1. \end{align*}$$ Since $a+3$ is an integer, $m+7$ is odd. Hence the theorem is proved. $\square$ ::: :::solved-problem Prove the theorem “If $m$ is even, then $m+7$ is odd” by contraposition. ::: :::solution Given that $m$ is an integer. To prove that if $m$ is even, then $m+7$ is odd. The contrapositive statement is: if $m+7$ is not odd, then $m$ is not even. Since every integer is either even or odd, this becomes: if $m+7$ is even, then $m$ is odd. Assume that $m+7$ is even. Then there exists an integer $a$ such that $m+7=2a$. Therefore $m=2a-7=2a-8+1=2(a-4)+1$. Since $a-4$ is an integer, $m$ is odd. Hence the original implication is true. ::: :::solved-problem Prove the theorem “If $m$ is even, then $m+7$ is odd” by contradiction. ::: :::solution Given that $m$ is an integer. To prove that if $m$ is even, then $m+7$ is odd. Assume that $m$ is even and $m+7$ is not odd. Since $m+7$ is an integer, not odd means even. Thus there exist integers $a$ and $b$ such that $m=2a$ and $m+7=2b$. Substituting $m=2a$ into $m+7=2b$, we get $2a+7=2b$, so $7=2(b-a)$. This says that $7$ is even, which is false. Therefore the assumption leads to a contradiction. Hence $m+7$ is odd. ::: :::theorem[Positive Product Bound] Let $x$ and $y$ be positive real numbers. If $xy>25$, then $x>5$ or $y>5$. ::: :::proof Given that $x$ and $y$ are positive real numbers. To prove that if $xy>25$, then $x>5$ or $y>5$. We prove the contrapositive. Assume that $x\leq 5$ and $y\leq 5$. Since $x$ and $y$ are positive, multiplying the inequalities gives $xy\leq 25$. Therefore, if $xy>25$, it cannot be true that both $x\leq 5$ and $y\leq 5$. Hence $x>5$ or $y>5$. $\square$ ::: :::theorem[Odd Product Implies Odd Factors] Let $k$ and $l$ be integers. If $kl$ is odd, then $k$ and $l$ are both odd. ::: :::proof Given that $k$ and $l$ are integers. To prove that if $kl$ is odd, then $k$ and $l$ are both odd. We prove the contrapositive. The contrapositive is: if $k$ or $l$ is even, then $kl$ is even. If $k=2a$, then $kl=2(al)$, even. If $l=2b$, then $kl=2(kb)$, even. Therefore, if $k$ or $l$ is even, then $kl$ is even. Hence, by contraposition, if $kl$ is odd, then $k$ and $l$ are both odd. $\square$ ::: :::theorem[Even Sum Parity Classification] Let $k$ and $l$ be integers. If $k+l$ is even, then $k$ and $l$ are both even or both odd. ::: :::proof Given that $k$ and $l$ are integers. To prove that if $k+l$ is even, then $k$ and $l$ are both even or both odd. We prove the contrapositive. If one of $k$ and $l$ is even and the other is odd, then their sum is odd. For example, if $k=2a$ and $l=2b+1$, then $k+l=2(a+b)+1$. The other case is similar. Therefore, if $k+l$ is even, $k$ and $l$ must have the same parity. Hence $k$ and $l$ are both even or both odd. $\square$ ::: :::theorem[Square of an Odd Integer] Let $n$ be an integer. If $n$ is odd, then $n^2$ is odd. ::: :::proof Given that $n$ is an integer. Given that $n$ is odd. To prove that $n^2$ is odd. Since $n=2a+1$ for some integer $a$, we get $$\begin{align*} n^2&=(2a+1)^2\\ &=4a^2+4a+1\\ &=2(2a^2+2a)+1. \end{align*}$$ Since $2a^2+2a$ is an integer, $n^2$ is odd. $\square$ ::: :::theorem[Odd Square Implies Odd Integer] Let $n$ be an integer. If $n^2$ is odd, then $n$ is odd. ::: :::proof Given that $n$ is an integer. To prove that if $n^2$ is odd, then $n$ is odd. We prove the contrapositive. Assume that $n$ is not odd. Since every integer is either even or odd, $n$ is even. Then $n=2a$ for some integer $a$, and $n^2=4a^2=2(2a^2)$, which is even. Therefore, by contraposition, if $n^2$ is odd, then $n$ is odd. $\square$ ::: :::theorem[Even Square Characterization] Let $n$ be an integer. Then $n^2$ is even if and only if $n$ is even. ::: :::proof Given that $n$ is an integer. To prove that $n^2$ is even if and only if $n$ is even. First assume that $n$ is even. Then $n=2a$ for some integer $a$, so $n^2=4a^2=2(2a^2)$, even. Conversely, assume that $n^2$ is even. If $n$ were odd, then by the previous theorem $n^2$ would be odd, a contradiction. Hence $n$ is even. Therefore $n^2$ is even if and only if $n$ is even. $\square$ ::: :::theorem[Odd Integer Plus Eleven] Let $n$ be an integer. If $n$ is odd, then $n+11$ is even. ::: :::proof Given that $n$ is an integer. Given that $n$ is odd. To prove that $n+11$ is even. Since $n=2a+1$ for some integer $a$, we get $n+11=2a+12=2(a+6)$. Since $a+6$ is an integer, $n+11$ is even. $\square$ ::: :::solved-problem Prove that if $n$ is odd, then $n+11$ is even by contraposition. ::: :::solution Given that $n$ is an integer. To prove that if $n$ is odd, then $n+11$ is even. The contrapositive is: if $n+11$ is odd, then $n$ is even. Assume $n+11=2a+1$. Then $n=2a+1-11=2a-10=2(a-5)$. Since $a-5$ is an integer, $n$ is even. Hence the original implication is true. ::: :::solved-problem Prove that if $n$ is odd, then $n+11$ is even by contradiction. ::: :::solution Given that $n$ is an integer. To prove that if $n$ is odd, then $n+11$ is even. Assume that $n$ is odd and $n+11$ is not even. Since $n+11$ is an integer, not even means odd. Thus $n=2a+1$ and $n+11=2b+1$ for integers $a,b$. Substituting gives $2a+12=2b+1$, so $2(b-a)=11$. This says $11$ is even, a contradiction. Hence $n+11$ is even. ::: :::theorem[Product of Perfect Squares] Let $m$ and $n$ be positive integers. If $m$ and $n$ are perfect squares, then $mn$ is a perfect square. ::: :::proof Given that $m$ and $n$ are positive integers. Given that $m$ and $n$ are perfect squares. To prove that $mn$ is a perfect square. Since $m=a^2$ and $n=b^2$ for positive integers $a,b$, we have $mn=a^2b^2=(ab)^2$. Since $ab$ is a positive integer, $mn$ is a perfect square. $\square$ ::: :::solved-problem Prove or disprove: if $m$ and $n$ are positive integers and $m,n$ are perfect squares, then $m+n$ is a perfect square. ::: :::solution The statement is false. Take $m=1$ and $n=4$. Then $m=1=1^2$ and $n=4=2^2$, so $m$ and $n$ are perfect squares. However, $m+n=5$, and $5$ is not a perfect square. Therefore the given statement is disproved by counterexample. ::: :::solved-problem Prove or disprove: there exist positive integers $m$ and $n$ such that $m,n$, and $m+n$ are all perfect squares. ::: :::solution The statement is true. Take $m=9$ and $n=16$. Then $m=9=3^2$, $n=16=4^2$, and $m+n=25=5^2$. Hence such positive integers exist. ::: :::theorem[Consecutive Perfect-Square Condition] Let $m$ and $n$ be nonnegative integers. If $m$, $n$, $m+n$, and $m+n+1$ are all perfect squares, then $m=n=0$. ::: :::proof Given that $m$ and $n$ are nonnegative integers. Given that $m+n$ and $m+n+1$ are both perfect squares. To prove that $m=n=0$. Let $m+n=a^2$ and $m+n+1=b^2$ for nonnegative integers $a,b$. Then $b^2-a^2=1$, so $(b-a)(b+a)=1$. Since $b-a$ and $b+a$ are nonnegative integers, we must have $b-a=1$ and $b+a=1$. Solving gives $a=0$ and $b=1$. Therefore $m+n=0$. Since $m,n$ are nonnegative, $m=0$ and $n=0$. $\square$ ::: :::theorem[Real Number Sum Bound] Let $x$ and $y$ be real numbers. If $x+y\geq 100$, then $x\geq 50$ or $y\geq 50$. ::: :::proof Given that $x$ and $y$ are real numbers. To prove that if $x+y\geq 100$, then $x\geq 50$ or $y\geq 50$. We prove the contrapositive. Assume that $x<50$ and $y<50$. Adding gives $x+y<100$. Therefore, if $x+y\geq 100$, it cannot be true that both $x<50$ and $y<50$. Hence $x\geq 50$ or $y\geq 50$. $\square$ ::: :::exercise Answer the following. (1) Prove by contraposition: if $kl$ is odd, then $k$ and $l$ are both odd. (2) Prove by contradiction: if $m$ is even, then $m+7$ is odd. (3) Disprove that the sum of two positive perfect squares is always a perfect square. (4) Give positive integers $m,n$ such that $m,n$, and $m+n$ are perfect squares. ::: :::answer (1) Prove the contrapositive: if $k$ or $l$ is even, then $kl$ is even. (2) Assume $m=2a$ and $m+7=2b$; then $7=2(b-a)$, contradiction. (3) $1$ and $4$ are perfect squares, but $1+4=5$ is not. (4) $m=9$ and $n=16$ work because $9+16=25$. ::: :::faq[Frequently Asked Questions] Q: When is contraposition useful? A: It is useful when the negation of the conclusion gives stronger algebraic information. Q: What is proof by contradiction? A: It assumes the statement is false and derives an impossibility. Q: Does a counterexample disprove a universal theorem? A: Yes. One valid counterexample disproves a universal statement. ::: :::call-to-action[Review Theorem Proof Methods] subtitle: Compare direct proof, contraposition, contradiction, and counterexample before using these methods in later chapters. button: Review Section | /discrete-mathematics/mathematical-logic/quantifiers-definitions-and-proofs-of-theorems/biconditional-definitions-with-quantifiers button-ghost: Previous Lesson | /discrete-mathematics/mathematical-logic/quantifiers-definitions-and-proofs-of-theorems/integer-parity-definitions-and-direct-proofs :::