3 Constructing and Writing Proofs in Mathematics

3.6 Review of Proof Methods

This section is different from others in the text. It is meant primarily as a review of the proof methods studied in Chapter 3. So the first part of the section will be a description of some of the main proof techniques introduced in Chapter 3. The most important part of this section is the set of exercises since these exercises will provide an opportunity to use the proof techniques that we have studied so far.

We will now give descriptions of three of the most common methods used to prove a conditional statement.

3.6.1 Direct Proof of a Conditional Statement $(P\to Q)$

• When is it indicated? This type of proof is often used when the hypothesis and the conclusion are both stated in a "positive" manner. That is, no negations are evident in the hypothesis and conclusion.

• Description of the process. Assume that $P$ is true and use this to conclude that $Q$ is true. That is, we use the forward-backward method and work forward from $P$ and backward from $Q$.

• Why the process makes sense. We know that the conditional statement $P\to Q$ is automatically true when the hypothesis is false. Therefore, because our goal is to prove that $P\to Q$ is true, there is nothing to do in the case that $P$ is false. Consequently, we may assume that $P$ is true. Then, in order for $P\to Q$ to be true, the conclusion $Q$ must also be true. (When $P$ is true, but $Q$ is false, $P\to Q$ is false.) Thus, we must use our assumption that $P$ is true to show that $Q$ is also true.

3.6.2 Proof of a Conditional Statement $(P\to Q)$ Using the Contrapositive

• When is it indicated? This type of proof is often used when both the hypothesis and the conclusion are stated in the form of negations. This often works well if the conclusion contains the operator "or"; that is, if the conclusion is in the form of a disjunction. In this case, the negation will be a conjunction.

• Description of the process. We prove the logically equivalent statement $\neg Q\to \neg P$. The forward-backward method is used to prove $\neg Q\to \neg P$. That is, we work forward from $\neg Q$ and backward from $\neg P$.

• Why the process makes sense. When we prove $\neg Q\to \neg P$, we are also proving $P\to Q$ because these two statements are logically equivalent. When we prove the contrapositive of $P\to Q$, we are doing a direct proof of $\neg Q\to \neg P$. So we assume $\neg Q$ because, when doing a direct proof, we assume the hypothesis, and $\neg Q$ is the hypothesis of the contrapositive. We must show $\neg P$ because it is the conclusion of the contrapositive.

3.6.3 Proof of $(P\to Q)$ Using a Proof by Contradiction

• When is it indicated? This type of proof is often used when the conclusion is stated in the form of a negation, but the hypothesis is not. This often works well if the conclusion contains the operator "or"; that is, if the conclusion is in the form of a disjunction. In this case, the negation will be a conjunction.

• Description of the process. Assume $P$ and $\neg Q$ and work forward from these two assumptions until a contradiction is obtained.

• Why the process makes sense. The statement $P\to Q$ is either true or false. In a proof by contradiction, we show that it is true by eliminating the only other possibility (that it is false). We show that $P\to Q$ cannot be false by assuming it is false and reaching a contradiction. Since we assume that $P\to Q$ is false, and the only way for a conditional statement to be false is for its hypothesis to be true and its conclusion to be false, we assume that $P$ is true and that $Q$ is false (or, equivalently, that $\neg Q$ is true). When we reach a contradiction, we know that our original assumption that $P\to Q$ is false is incorrect. Hence, $P\to Q$ cannot be false, and so it must be true.

3.6.4 Other Methods of Proof

The methods of proof that were just described are three of the most common types of proof. However, we have seen other methods of proof and these are described below.

3.6.5 Proofs that Use a Logical Equivalency

As was indicated in Section 3.2, we can sometimes use a logical equivalency to help prove a statement. For example, in order to prove a statement of the form

$$P\to (Q\vee R)$$ (1)

it is sometimes possible to use the logical equivalency

$$[P\to (Q\vee R)]\equiv [(P\wedge \neg Q)\to R]$$

We would then prove the statement

$$(P\wedge \neg Q)\to R$$ (2)

Most often, this would use a direct proof for statement (2) but other methods could also be used. Because of the logical equivalency, by proving statement (2), we have also proven the statement (1).

3.6.6 Proofs that Use Cases

When we are trying to prove a proposition or a theorem, we often run into the problem that there does not seem to be enough information to proceed. In this situation, we will sometimes use cases to provide additional assumptions for the forward process of the proof. When this is done, the original proposition is divided into a number of separate cases that are proven independently of each other. The cases must be chosen so that they exhaust all possibilities for the hypothesis of the original proposition. This method of case analysis is justified by the logical equivalency

$$(P\vee Q)\to R\equiv (P\to R)\wedge (Q\to R)$$

which was established in Beginning Activity 1 in Section 3.4.

3.6.7 Constructive Proof

This is a technique that is often used to prove a so-called existence theorem. The objective of an existence theorem is to prove that a certain mathematical object exists. That is, the goal is usually to prove a statement of the form

There exists an $x$ such that $P(x)$.

For a constructive proof of such a proposition, we actually name, describe, or explain how to construct some object in the universe that makes $P(x)$ true.

3.6.8 Nonconstructive Proof

Another type of proof that is often used to prove an existence theorem is the so-called nonconstructive proof. For this type of proof, we make an argument that an object in the universal set that makes $P(x)$ true must exist but we never construct or name the object that makes $P(x)$ true.

3.6.9 Exercises for Section 3.6

1. Let $h$ and $k$ be real numbers and let $r$ be a positive number. The equation for a circle whose center is at the point $(h,k)$ and whose radius is $r$ is

   $${(x-h)}^2+{(y-k)}^2=r^2$$

   We also know that if $a$ and $b$ are real numbers, then

   • The point $(a,b)$ is inside the circle if .

   • The point $(a,b)$ is on the circle if ${(a-h)}^2+{(b-k)}^2=r^2$.

   • The point $(a,b)$ is outside the circle if ${(a-h)}^2+{(b-k)}^2>r^2$.

   Prove that all points on or inside the circle whose equation is ${(x-1)}^2+{(y-2)}^2=4$ are inside the circle whose equation is $x^2+y^2=26$.

2. (Exercise (15), Section 3.1) Let $r$ be a positive real number. The equation for a circle of radius $r$ whose center is the origin is $x^2+y^2=r^2$.

   1. Use implicit differentiation to determine $\frac{dy}{dx}$.

   2. (Exercise (17), Section 3.2) Let $(a,b)$ be a point on the circle with $a\ne 0$ and $b\ne 0$. Determine the slope of the line tangent to the circle at the point $(a,b)$.

   3. Prove that the radius of the circle to the point $(a,b)$ is perpendicular to the line tangent to the circle at the point $(a,b)$. Hint: Two lines (neither of which is horizontal) are perpendicular if and only if the products of their slopes is equal to -1.

3. Are the following statements true or false? Justify your conclusions.

   1. For each integer $a$, if 3 does not divide $a$, then 3 divides $2a^2+1$.

   2. For each integer $a$, if 3 divides $2a^2+1$, then 3 does not divide $a$.

   3. For each integer $a,3$ does not divide $a$ if and only if 3 divides $2a^2+1$.

4. Prove that for each real number $x$ and each irrational number $q$, $(x+q)$ is irrational or $(x-q)$ is irrational.

5. Prove that there exist irrational numbers $u$ and $v$ such that $u^v$ is a rational number. Hint: We have proved that $\sqrt{2}$ is irrational. For the real number $q={\sqrt{2}}^{\sqrt{2}}$, either $q$ is rational or $q$ is irrational. Use this disjunction to set up two cases.

6. (Exercise (17), Section 3.2) Let $a$ and $b$ be natural numbers such that $a^2=b^3$. Prove each of the propositions in Parts (6a) through (6d). (The results of Exercise (1) and Theorem 3.10 from Section 3.2 may be helpful.)

   1. If $a$ is even, then 4 divides $a$.

   2. If 4 divides $a$, then 4 divides $b$.

   3. If 4 divides $b$, then 8 divides $a$.

   4. If $a$ is even, then 8 divides $a$.

   5. Give an example of natural numbers $a$ and $b$ such that $a$ is even and $a^2=b^3$, but $b$ is not divisible by 8.

7. (Exercise (18), Section 3.2) Prove the following proposition:

   Let $a$ and $b$ be integers with $a\ne 0$. If $a$ does not divide $b$, then the equation $a{x}^3+bx+(b+a)=0$ does not have a solution that is a natural number.

   Hint: It may be necessary to factor a sum of cubes. Recall that

   $$u^3+v^3=(u+v)\left(u^2-uv+v^2\right)$$

8. Recall that a Pythagorean triple consists of three natural numbers $a,b$, and $c$ such that and $a^2+b^2=c^2$. Are the following propositions true or false? Justify your conclusions.

   1. For all $a,b,c\in \mathbb{N}$ such that , if $a,b$, and $c$ form a Pythagorean triple, then 3 divides $a$ or 3 divides $b$.

   2. For all $a,b,c\in \mathbb{N}$ such that , if $a,b$, and $c$ form a Pythagorean triple, then 5 divides $a$ or 5 divides $b$ or 5 divides $c$.

9. 1. Prove that there exists a Pythagorean triple $a,b$, and $c$, where $a=5$ and $b$ and $c$ are consecutive natural numbers.

   2. Prove that there exists a Pythagorean triple $a,b$, and $c$, where $a=7$ and $b$ and $c$ are consecutive natural numbers.

   3. Let $m$ be an odd natural number that is greater than 1. Prove that there exists a Pythagorean triple $a,b$, and $c$, where $a=m$ and $b$ and $c$ are consecutive natural numbers.

10. One of the most famous unsolved problems in mathematics is a conjecture made by Christian Goldbach in a letter to Leonhard Euler in 1742. The conjecture made in this letter is now known as Goldbach’s Conjecture. The conjecture is as follows:

    Every even integer greater than 2 can be expressed as the sum of two (not necessarily distinct) prime numbers.

    Currently, it is not known if this conjecture is true or false.

    1. Write 50, 142, and 150 as a sum of two prime numbers.

    2. Prove the following:

       If Goldbach’s Conjecture is true, then every integer greater than 5 can be written as a sum of three prime numbers.

    3. Prove the following:

       If Goldbach’s Conjecture is true, then every odd integer greater than 7 can be written as a sum of three odd prime numbers.

11. Two prime numbers that differ by 2 are called twin primes. For example, 3 and 5 are twin primes, 5 and 7 are twin primes, and 11 and 13 are twin primes. Determine at least two other pairs of twin primes. Is the following proposition true or false? Justify your conclusion.

    For all natural numbers $p$ and $q$ if $p$ and $q$ are twin primes other than 3 and 5, then $pq+1$ is a perfect square and 36 divides $pq+1$.

12. Are the following statements true or false? Justify your conclusions.

    1. For all integers $a$ and $b,{(a+b)}^2\equiv \left(a^2+b^2\right)(mod2)$.

    2. For all integers $a$ and $b,{(a+b)}^3\equiv \left(a^3+b^3\right)(mod3)$.

    3. For all integers $a$ and $b,{(a+b)}^4\equiv \left(a^4+b^4\right)(mod4)$.

    4. For all integers $a$ and $b,{(a+b)}^5\equiv \left(a^5+b^5\right)(mod5)$.

    If any of the statements above are false, write a new statement of the following form that is true (and prove that it is true):

    For all integers $a$ and $b,{(a+b)}^n\equiv (a^n+$ something $+b^n)(modn)$.

13. Let $a,b,c$, and $d$ be real numbers with $a\ne 0$ and let $f(x)=a{x}^3+b{x}^2+cx+d$.

    1. Determine the derivative and second derivative of the cubic function $f$.

    2. Prove that the cubic function $f$ has at most two critical points and has exactly one inflection point.

3.6.10 Explorations and Activities

1. A Special Case of Fermat’s Last Theorem. We have already seen examples of Pythagorean triples, which are natural numbers $a,b$, and $c$ where $a^2+b^2=c^2$. For example, 3, 4, and 5 form a Pythagorean triple as do 5, 12, and 13. One of the famous mathematicians of the 17th century was Pierre de Fermat (1601-1665). Fermat made an assertion that for each natural number $n$ with $n\ge 3$, there are no positive integers $a,b$, and $c$ for which $a^n+b^n=c^n$. This assertion was discovered in a margin of one of Fermat’s books after his death, but Fermat provided no proof. He did, however, state that he had discovered a truly remarkable proof but the margin did not contain enough room for the proof.

   This assertion became known as Fermat’s Last Theorem but it more properly should have been called Fermat’s Last Conjecture. Despite the efforts of mathematicians, this "theorem" remained unproved until Andrew Wiles, a British mathematician, first announced a proof in June of 1993. However, it was soon recognized that this proof had a serious gap, but a widely accepted version of the proof was published by Wiles in 1995. Wiles’ proof uses many concepts and techniques that were unknown at the time of Fermat. We
   cannot discuss the proof here, but we will explore and prove the following proposition, which is a (very) special case of Fermat’s Last Theorem.

   Proposition. There do not exist prime numbers $a,b$, and $c$ such that $a^3+b^3=c^3$.

   Although Fermat’s Last Theorem implies this proposition is true, we will use a proof by contradiction to prove this proposition. For a proof by contradiction, we assume that
   there exist prime numbers $a,b$, and $c$ such that $a^3+b^3=c^3$.
   Since 2 is the only even prime number, we will use the following cases: (1) $a=b=2$; (2) $a$ and $b$ are both odd; and (3) one of $a$ and $b$ is odd and the other one is 2.

   1. Show that the case where $a=b=2$ leads to a contradiction and hence, this case is not possible.

   2. Show that the case where $a$ and $b$ are both odd leads to a contradiction and hence, this case is not possible.

   3. We now know that one of $a$ or $b$ must be equal to 2. So we assume that $b=2$ and that $a$ is an odd prime. Substitute $b=2$ into the equation $b^3=c^3-a^3$ and then factor the expression $c^3-a^3$. Use this to obtain a contradiction.

   4. Write a complete proof of the proposition.

2. The purpose of this exploration is to investigate the possibilities for which integers cannot be the sum of the cubes of two or three integers.

   1. If $x$ is an integer, what are the possible values (between 0 and 8, inclusive) for $x^3$ modulo 9?

   2. If $x$ and $y$ are integers, what are the possible values for $x^3+y^3$ (between 0 and 8, inclusive) modulo 9?

   3. If $k$ is an integer and $k\equiv 3(mod9)$, can $k$ be equal to the sum of the cubes of two integers? Explain.

   4. If $k$ is an integer and $k\equiv 4(mod9)$, can $k$ be equal to the sum of the cubes of two integers? Explain.

   5. State and prove a theorem of the following form: For each integer $k$, if (conditions on $k$), then $k$ cannot be written as the sum of the cubes of two integers. Be as complete with the conditions on $k$ as possible based on the explorations in Part (b).

   6. If $x,y$, and $z$ are integers, what are the possible values (between 0 and 8, inclusive) for $x^3+y^3+z^3$ modulo 9?

   7. If $k$ is an integer and $k\equiv 4(mod9)$, can $k$ be equal to the sum of the cubes of three integers? Explain.

   8. State and prove a theorem of the following form: For each integer $k$, if (conditions on $k$), then $k$ cannot be written as the sum of the cubes of three integers. Be as complete with the conditions on $k$ as possible based on the explorations in Part (f).

Note: Andrew Booker, a mathematician at the University of Bristol in the United Kingdom, recently discovered that 33 can be written as the sum of the cubes of three integers. Booker used a trio of 16-digit integers, two of which were negative.

3.7 Chapter 3 Summary

3.7.1 Important Definitions

• Divides, divisor, Section 3.1

• Factor, multiple, Section 3.1

• Proof, Section 3.1

• Undefined term, Section 3.1

• Axiom, Section 3.1

• Definition, Section 3.1

• Conjecture, Section 3.1

• Theorem, Section 3.1

• Proposition, Section 3.1

• Lemma, Section 3.1

• Corollary, Section 3.1

• Congruence modulo $n$, Section 3.2

• Tautology, Section 2.1

• Contradiction, Section 2.1

• Absolute value, Section 3.1

3.7.2 Important Theorems and Results about Even and Odd Integers

• Exercise (1), Section 1.2.

If $m$ is an even integer, then $m+1$ is an odd integer.
If $m$ is an odd integer, then $m+1$ is an even integer.

• Exercise (2), Section 1.2.

If $x$ is an even integer and $y$ is an even integer, then $x+y$ is an even integer.
If $x$ is an even integer and $y$ is an odd integer, then $x+y$ is an odd integer.
If $x$ is an odd integer and $y$ is an odd integer, then $x+y$ is an even integer.

• Exercise (3), Section 1.2. If $x$ is an even integer and $y$ is an integer, then $x\cdot y$ is an even integer.

• Theorem 1.8. If $x$ is an odd integer and $y$ is an odd integer, then $x\cdot y$ is an odd integer.

• Theorem 3.7. The integer $n$ is an even integer if and only if $n^2$ is an even integer.
  Beginning Activity 2 in Section 3.2. The integer $n$ is an odd integer if and only if $n^2$ is an odd integer.

3.7.3 Important Theorems and Results about Divisors

• Theorem 3.1. For all integers $a,b$, and $c$ with $a\ne 0$, if $a\mid b$ and $b\mid c$, then $a\mid c$.

• Exercise (3), Section 3.1. For all integers $a$, $b$, and $c$ with $a\ne 0$,

If $a\mid b$ and $a\mid c$, then $a\mid (b+c)$.
If $a\mid b$ and $a\mid c$, then $a\mid (b-c)$.

• Exercise (3a), Section 3.1. For all integers $a,b$, and $c$ with $a\ne 0$, if $a\mid b$, then $a\mid (bc)$.

• Exercise (4), Section 3.1. For all nonzero integers $a$ and $b$, if $a\mid b$ and $b\mid a$, then $a=\pm b$.

3.7.4 The Division Algorithm

Let $a$ and $b$ be integers with $b>0$. Then there exist unique integers $q$ and $r$ such that