Mathematical Proof/Methods of Proof

There are many different ways to prove things in mathematics. This chapter will introduce some of those methods.

Introduction

In this chapter, for every method of proof introduced, we will discuss it in this manner:

1. Explaining why the method works, by considering its underlying logic.
2. Introducing how to use the method.
3. Giving examples of using the method (and possibly also some previous method introduced) to prove some results.

Before introducing the first proof method, let us go through the meanings of some frequently used terms in mathematics books (some are already used in previous chapters actually), which are used more frequently starting from this chapter.

• Definition: an explanation of meaning of a term.
• Theorem: an important and interesting true mathematical statement.

• Proposition: a (relatively) less important theorem.

• Lemma: a true mathematical statement that is useful in establishing the truth of other true statements, and is less important than a theorem.
• Corollary: a true mathematical statement that can be deduced from a theorem (or proposition) simply.
• Proof: an explanation of why a statement is true.
• Axiom: a true mathematical statement whose truth is accepted without proof.
• Conjecture: a statement that is believed to be true, but is not proven to be true.

Direct proof

Many mathematical theorems can be expressed in the form of "$\forall x\in S,P(x)\implies Q(x)$, in which $P(x)$ and $Q(x)$ are open statements about elements $x$ in a set $S$ . This expression means "If $P(x)$ then $Q(x)$" is true for every $x\in S$. However, in practice, we rarely include the phrase "is true", and usually just write the theorem in the form of "For every $x\in S$, if $P(x)$, then $Q(x)$." Sometimes, we write instead "Let $x\in S$. If $P(x)$, then $Q(x)$.", which has the same meaning.

In some situations, the statement is not stated in such a form directly, but can be expressed in such a form. For example, the statement "The square of an even integer is even." can be expressed as "For every $x\in \mathbb {Z}$, $x$ is even $\implies$ $x^{2}$ is even.", or "For every $x\in \mathbb {Z}$, if $x$ is even, then $x^{2}$ is even.", or "Let $x\in \mathbb {Z}$. If $x$ is even, then $x^{2}$ is even.", etc.

Now, we will introduce the first proof method to prove statements in such a form, which is known as direct proof. As suggested by its name, this method is quite "direct", and is probably the simplest method among all methods discussed in this chapter.

Consider the statement "$\forall x\in S,P(x)\to Q(x)$". We would like to prove that it is true. Suppose $P(x_{0})$ is false for some $x_{0}\in S$. Then, the conditional $P(x_{0})\to Q(x_{0})$ must be true for this $x_{0}$ by definition, regardless of the truth value of $Q(x_{0})$. Hence, in the proof, we do not need to consider those $x\in S$ for which the hypothesis $P(x)$ is false.

Because of this, to give a direct proof of "$\forall x\in S,P(x)\implies Q(x)$", we first assume $P(x)$ is true (So, we are considering every $x\in S$ for which $P(x)$ is true.), and then proceed to show that $Q(x)$ is true for every such $x$ (or else the conditional $P(x)\to Q(x)$ will be false).

This shows that $P(x)\to Q(x)$ is true for those $x\in S$ for which $P(x)$ is true, and this is enough to prove $P(x)\to Q(x)$ is true for every $x\in S$ (for which $P(x)$ may or may not be true), since we have mentioned that the conditional $P(x)\to Q(x)$ must be true for those $x\in S$ for which $P(x)$ is false.

Example. Prove that for every $n\in \mathbb {Z}$, if $n$ is odd, then $3n+1$ is even.

Proof. Assume $n$ is odd. Then, by definition we have $n=2k+1$ for some $k\in \mathbb {Z}$. Thus, $$3n+1=3(2k+1)+1=6k+4=2(3k+2)=2k',$$ where $k'=3k+2\in \mathbb {Z}$ (this follows from the definition of integers). This means $3n+1$ can be written as $2k'$ for some $k'\in \mathbb {Z}$, and hence $3n+1$ is even.

$\Box$

In the previous proof, we have used the definitions of odd and even integers:

• an integer $n$ is even if $n=2k$ for some integer $k$.
• an integer $n$ is odd if $n=2k+1$ for some integer $k$.

We can write the proof more concisely using logical notations, as follows:

Proof. $${\begin{aligned}&&&n{\text{ is odd}}\\&\Rightarrow &&n=2k+1{\text{ for some }}k\in \mathbb {Z} \\&\Rightarrow &&3n+1=2(3k+2)&(3k+2\in \mathbb {Z} )\\&\Rightarrow &&3n+1{\text{ is even.}}\end{aligned}}$$

$\Box$

Both styles of proofs are acceptable, but for beginners, it is recommended to use the first type. Also, the first type can let the readers understand the proof easier.

Remark.

• The property of an integer of whether it is even or odd is called parity.
• When we use "$n$" in the proof, it is implicitly assumed it follows the same meaning as in the given statement, i.e., $n$ is an integer. We can also let $n$ to be an integer explicitly in the proof to be more clear.
• In some other places, the first line "Assume ..." is simply omitted for convenience, but the assumptions are still used in the proof.

Exercise. Consider the statement "For every $a,b\in \mathbb {Z}$, if $a$ is odd and $b$ is even, then $4a+5b$ is even.". A student provides the following proof to the statement:

Proof. Assume $a$ is odd and $b$ is even. That is, $a=2k+1$ and $b=2k$ for some $k\in \mathbb {Z}$. It follows that $4a+5b=8k+4+10k=2(9k+2)$, and thus $4a+5b$ is even.

$\Box$

Is the proof correct? If not, point out the mistake, and write a correct proof.

Solution

The proof is incorrect. The mistake is that one should not use the same $k$ for both $a$ and $b$, since using the same $k$ implies that $a=b+1$, which is not necessarily the case from the assumptions. The following proof is a correct one:

Proof. Assume $a$ is odd and $b$ is even. That is, $a=2{\color {blue}k_{1}}+1$ and $b=2{\color {blue}k_{2}}$ for some $k_{1},k_{2}\in \mathbb {Z}$. It follows that $4a+5b=8k_{1}+4+10k_{2}=2(4k_{1}+5k_{2}+2)$, and thus $4a+5b$ is even.

$\Box$

Exercise. Prove that for every $n\in \mathbb {Z}$, if $n$ is even, then $n^{2}+n+1$ is odd.

Proof

Proof. Assume $n$ is even. Then, $n=2k$ for some $k\in \mathbb {Z}$. Thus, $$n^{2}+n+1=4k^{2}+2k+1=2(2k^{2}+k)+1.$$ Since $k^{2}+k\in \mathbb {Z}$, $n^{2}+n+1$ is odd.

$\Box$

Exercise. Prove every of the following statements.

(a) The sum of two arbitrary even integers is even.

(b) The sum of two arbitrary odd integers is even.

(c) The sum of an arbitrary even integer and an arbitrary odd integer is odd.

(d) The product of two arbitrary even integers is even.

(e) The product of two arbitrary odd integers is odd.

(f) The product of an arbitrary even integer and an arbitrary odd integer is even.

(Hint: rewrite the statements in the form of "$\forall x,y\in S,P(x,y)\implies Q(x,y)$" first.)

Solution

(a) First, rewrite the statement as "For every $x,y\in \mathbb {Z}$, if $x$ and $y$ are even, then $x+y$ is even."

Proof. Assume $x$ and $y$ are even. Then, $x=2k_{1}$ and $y=2k_{2}$ for some $k_{1},k_{2}\in \mathbb {Z}$ (notice that we should not use the same $k$ for both $x$ and $y$, since $x$ may be different from $y$.). Thus, $x+y=2(k_{1}+k_{2})$, and hence $x+y$ is even since $k_{1}+k_{2}\in \mathbb {Z}$.

$\Box$

(b) First, rewrite the statement as "For every $x,y\in \mathbb {Z}$, if $x$ and $y$ are odd, then $x+y$ is even."

Proof. Assume $x$ and $y$ are odd. Then, $x=2k_{1}+1$ and $y=2k_{2}+1$ for some $k_{1},k_{2}\in \mathbb {Z}$. Thus, $x+y=2(k_{1}+k_{2}+1)$, and hence $x+y$ is even since $k_{1}+k_{2}+1\in \mathbb {Z}$.

$\Box$

(c) First, rewrite the statement as "For every $x,y\in \mathbb {Z}$, if $x$ is odd and $y$ is even, then $x+y$ is odd."

Proof. Assume $x$ is odd and $y$ is even. Then, $x=2k_{1}+1$ and $y=2k_{2}$ for some $k_{1},k_{2}\in \mathbb {Z}$. Thus, $x+y=2(k_{1}+k_{2})+1$, and hence $x+y$ is odd since $k_{1}+k_{2}\in \mathbb {Z}$.

$\Box$

(d) First, rewrite the statement as "For every $x,y\in \mathbb {Z}$, if $x$ is even and $y$ is even, then $xy$ is even."

Proof. Assume $x$ and $y$ are even. Then, $x=2k_{1}$ and $y=2k_{2}$ for some $k_{1},k_{2}\in \mathbb {Z}$. Thus, $xy=2(2k_{1}k_{2})$, and hence $xy$ is even since $2k_{1}k_{2}\in \mathbb {Z}$.

$\Box$

(e) First, rewrite the statement as "For every $x,y\in \mathbb {Z}$, if $x$ is odd and $y$ is odd, then $xy$ is odd."

Proof. Assume $x$ and $y$ are odd. Then, $x=2k_{1}+1$ and $y=2k_{2}+1$ for some $k_{1},k_{2}\in \mathbb {Z}$. Thus, $xy=(2k_{1}+1)(2k_{2}+1)=4k_{1}k_{2}+2k_{1}+2k_{2}+1=2(2k_{1}k_{2}+k_{1}+k_{2})+1$, and hence $xy$ is odd since $2k_{1}k_{2}+k_{1}+k_{2}\in \mathbb {Z}$.

$\Box$

(f) First, rewrite the statement as "For every $x,y\in \mathbb {Z}$, if $x$ is odd and $y$ is even, then $xy$ is even."

Proof. Assume $x$ is odd and $y$ is even. Then, $x=2k_{1}+1$ and $y=2k_{2}$ for some $k_{1},k_{2}\in \mathbb {Z}$. Thus, $xy=(2k_{1}+1)(2k_{2})=4k_{1}k_{2}+2k_{2}=2(2k_{1}k_{2}+k_{2})$, and hence $xy$ is even since $2k_{1}k_{2}+k_{2}\in \mathbb {Z}$.

$\Box$

Exercise. A real number $x$ is defined to be rational if there exist integers $p,q$ with $q\neq 0$ such that $x={\frac {p}{q}}$. Prove every of the following statements.

(a) The sum of two arbitrary rational numbers is rational.

(b) The difference of two arbitrary rational numbers is rational.

(c) The product of two arbitrary rational numbers is rational.

(d) The quotient of an arbitrary rational number by an arbitrary nonzero rational number is rational.

Solution

(a) First, rewrite the statement as "For every $x,y\in \mathbb {R}$, if $x,y\in \mathbb {Q}$, then $x+y\in \mathbb {Q}$.

Proof. Assume $x,y\in \mathbb {Q}$. Then, $x={\frac {p_{1}}{q_{1}}}$ and $y={\frac {p_{2}}{q_{2}}}$ for some $p_{1},p_{2},q_{1},q_{2}\in \mathbb {Z}$ with $q_{1}\neq 0$ and $q_{2}\neq 0$. Thus, $$x+y={\frac {p_{1}}{q_{1}}}+{\frac {p_{2}}{q_{2}}}={\frac {p_{1}q_{2}+p_{2}q_{1}}{q_{1}q_{2}}}.$$ Since $p_{1}q_{2}+p_{2}q_{1},q_{1}q_{2}\in \mathbb {Z}$ with $q_{1}q_{2}\neq 0$, $x+y\in \mathbb {Q}$.

$\Box$

(b) First, rewrite the statement as "For every $x,y\in \mathbb {R}$, if $x,y\in \mathbb {Q}$, then $x-y\in \mathbb {Q}$.

Proof. Assume $x,y\in \mathbb {Q}$. Then, $y={\frac {p}{q}}$ for some $p,q\in \mathbb {Z}$ with $q\neq 0$. So, $-q={\frac {-p}{q}}$ is rational since $-p,q\in \mathbb {Z}$ and $q\neq 0$. Thus, by (a), we have $x-y=x+(-y)\in \mathbb {Q}$.

$\Box$

(c) First, rewrite the statement as "For every $x,y\in \mathbb {R}$, if $x,y\in \mathbb {Q}$, then $xy\in \mathbb {Q}$.

Proof. Assume $x,y\in \mathbb {Q}$. Then, $x={\frac {p_{1}}{q_{1}}}$ and $y={\frac {p_{2}}{q_{2}}}$ for some $p_{1},p_{2},q_{1},q_{2}\in \mathbb {Z}$ with $q_{1}\neq 0$ and $q_{2}\neq 0$. Thus, $$xy={\frac {p_{1}p_{2}}{q_{1}q_{2}}}.$$ Since $p_{1}p_{2},q_{1}q_{2}\in \mathbb {Z}$ with $q_{1}q_{2}\neq 0$, $xy\in \mathbb {Q}$.

$\Box$

(d) First, rewrite the statement as "For every $x,y\in \mathbb {R}$, if $x,y\in \mathbb {Q}$ and $y\neq 0$ then ${\frac {x}{y}}\in \mathbb {Q}$.

Proof. Assume $x,y\in \mathbb {Q}$ and $y\neq 0$. Then, $x={\frac {p_{1}}{q_{1}}}$ and $y={\frac {p_{2}}{q_{2}}}$ for some $p_{1},p_{2},q_{1},q_{2}\in \mathbb {Z}$ with $p_{2}\neq 0$, $q_{1}\neq 0$, and $q_{2}\neq 0$. Thus, $${\frac {x}{y}}={\frac {p_{1}q_{2}}{p_{2}q_{1}}}.$$ Since $p_{1}q_{2},p_{2}q_{1}\in \mathbb {Z}$ with $p_{2}q_{1}\neq 0$, ${\frac {x}{y}}\in \mathbb {Q}$.

$\Box$

Example. Prove that for every $x\in \mathbb {R}$, if $x^{2}-2x+1<0$, then $(x-2)^{3}\geq 8$.

Proof. For every $x\in \mathbb {R}$, $x^{2}-2x+1=(x-1)^{2}\geq 0$. Thus, the hypothesis is false, and hence the statement must be true.

$\Box$

Remark.

• Notice that we do not use direct proof here, since the false hypothesis makes the statement true. In this case, we call the proof as vacuous proof, and say that the result follows vacuously (the statement says nothing at all).

Example. Prove that for every $x\in \mathbb {R}$, if $0<x<1$, then $x^{2}-x-2<-2$.

Proof. Assume $0<x<1$. Then, $$x^{2}-x=x(x-1).$$ Since $x$ is positive and $x-1$ is negative by assumption, we have $x^{2}-x<0$, and thus $$x^{2}-x-2<0-2=-2.$$

$\Box$

Remark.

• Graphically, the function $f(x)=x^{2}-x-2$ (we will discuss the concept of function in later chapter) looks like:

Exercise. Prove that for every $x\in \mathbb {R}$, if $x^{2}-x-2<-2$, then $0<x<1$ (this statement is the converse of the statement in above example). (Hint: The following property may be useful: for every $a,b\in \mathbb {R}$, if $ab<0$, then either ($a<0$ and $b>0$) or ($a>0$ and $b<0$).) (This statement seems to be true by inspecting the above graph, but inspecting graph is not a valid way of proving this statement.)

Proof

Proof. Assume $x^{2}-x-2<-2$. Then, $x^{2}-x<0\implies x(x-1)<0$ ("$\implies$" is read "which implies" in this context). It follows that we have either

• $x<0$ and $x-1>0$, or
• $x>0$ and $x-1<0$.

Since no real number $x$ satisfies the first one, we must have the second one, which gives $0<x<1$.

$\Box$

Combining the two results in the previous example and exercise, we get an "if and only if" result:

For every $x\in \mathbb {R}$, we have $x^{2}-x-2<-2$ if and only if $0<x<1$.

In other words, using set language, $$\{x\in \mathbb {R} :0<x<1\}=\{x\in \mathbb {R} :(x-1)^{2}<1\}.$$ (Both sets represent the curve (strictly) under the horizontal line $y=-2$ in the above graph.)

Letting $P(x)$ and $Q(x)$ be the open statement "$x^{2}-x-2<-2$" and "$0<x<1$" respectively, we can express the above result symbolically: $$\forall x\in \mathbb {R} ,P(x)\iff Q(x).$$ Recall that "$P(x)\iff Q(x)$" means "$P(x)\implies Q(x)$" and "$Q(x)\implies P(x)$". So, to give a direct proof to the statement in the form of "$\forall x\in S,P(x)\iff Q(x)$", a usual way is to break the proof into two parts:

1. proving that $\forall x\in S,P(x)\implies Q(x)$ (known as the "only if" part, or "$\Rightarrow$" direction)
2. proving that $\forall x\in S,Q(x)\implies P(x)$ (known as the "if" part, or "$\Leftarrow$" direction)

Example. Prove that for every $n\in \mathbb {N}$, $n+{\frac {1}{n}}\geq 2$. (Hint: this inequality is equivalent to the inequality $n^{2}+1\geq 2n$, obtained by multiplying both side by $n$, which is a positive integer.)

Proof. Using the hint, it suffices to prove that for every $n\in \mathbb {N}$, $n^{2}+1\geq 2n$. But it follows from the fact that $n^{2}-2n+1=(n-1)^{2}\geq 0$.

$\Box$

Exercise.

We can strengthen the statement (i.e., make the statement stronger (recall the meaning of "stronger" in previous chapter)) in the example, by changing $\mathbb {N}$ to a larger set. Determine which of the following (may be more than one) can be the larger set.

	$\mathbb {Z}$
	$\mathbb {Q}$
	$\mathbb {R}$
	None of the above.

A student provides the following proof to the above statement:

Proof. Since $n$ is a positive integer, multiplying $n$ to both sides of the inequality yields $n^{2}+1\geq 2n$. After rearranging, we get $n^{2}-2n+1=(n-1)^{2}\geq 0$, which is always true.

$\Box$

Point out the mistake in the proof.

Solution

The mistake is that the student implicitly assumes $n+{\frac {1}{n}}\geq 2$, which is what we want to prove, at the beginning of the proof. Thus, this proof does not prove the result. (Notice that in the proof in the example, we do not assume $n+{\frac {1}{n}}\geq 2$. Instead, we start from the fact that $(n-1)^{2}\geq 0$.)

Example. Let $S=\{3,5,7,9,11\}$. Prove that for every $n\in S$, if $n$ is prime, then $n$ is odd.

Proof. Assume $n$ is prime. Since the only primes in the set $S$ are 3,5,7 and 11, this means $n=3,5,7{\text{ or }}11$. Hence, $n$ is odd.

$\Box$

Exercise. Prove that for every $n\in S$, if $n$ is even, then $n$ is prime.

Proof

Proof. Since the set $S$ only contains odd numbers, the hypothesis is false, and therefore the result follows vacuously.

$\Box$

Example. (A special case of AM-GM inequality) Prove that for every $x,y\in \mathbb {R}$, if $x$ and $y$ are positive, then $${\sqrt {xy}}\leq {\frac {x+y}{2}}.$$

Proof. Assume $x$ and $y$ are positive. Then, $$(x-y)^{2}\geq 0\implies (x+y)^{2}-4xy\geq 0\implies {\sqrt {(x+y)^{2}}}\geq {\sqrt {4xy}}\implies x+y\geq 2{\sqrt {xy}}\implies {\sqrt {xy}}\leq {\frac {x+y}{2}}.$$

$\Box$

Exercise. Suggest a condition where the equality holds, i.e., ${\sqrt {xy}}={\frac {x+y}{2}}$.

Solution

The condition is $x=y$.

Proofs related to congruence of integers

After introducing the method of direct proof, let us apply this method on proving some results relating to congruence of integers. Before this, let us introduce the concept of congruence of integers. We begin by a motivation for the definition of congruence of integers.

We know that an integer $x$ is either even or odd, i.e., can be expressed as $2k$ or $2k+1$ for some integer $k$, according to whether the remainder is 0 or 1 when $x$ is divided by 2. Thus, if two integers $x$ and $y$ have the same remainder when divided by 2 (i.e., have the same parity), then the difference $x-y$ can be proved to be a multiple of 2 (it can be proved that the converse is also true). Similarly, an integer can be expressed as $3k,3k+1$ or $3k+2$ for some integer $k$, according to whether remainder is 0, 1 or 2 when $x$ is divided by 3. Hence, if two integers $x$ and $y$ have the same remainder when divided by 3, then the difference $x-y$ can be proved to be a multiple of 3 (the converse is also true).

Hence, "two integers have the same remainder when divided by some integer $k$" is equivalent to "their difference is a multiple of $k$". This leads us to the following definition.

Definition. (Congruence of integers) Let $a,b\in \mathbb {Z}$ and $n\in \mathbb {N}$ with $n\geq 2$. Then, the integer $a$ is congruent to $b$ modulo $n$, denoted by $a\equiv b{\pmod {n}}$, if $a-b$ is a multiple of $n$, i.e., $a-b=nk$ for some $k\in \mathbb {Z}$.

Remark.

• Instead of "$a-b$ is a multiple of $n$", we can also say $a-b$ is divisible by $n$, or $n$ divides $a-b$, denoted by $n|(a-b)$ (in general, the notation $x|y$ means "$x$ divides $y$" (and $x\nmid y$ means "$x$ does not divide $y$").

Example. We have $13\equiv 1{\pmod {12}}$ since $12|(13-1)$, and $-23\equiv -13{\pmod {12}}$ since $12|(-23-13)$. But, $5\not \equiv 10{\pmod {4}}$ since $4\nmid (5-10)$.

Exercise.

1 Choose the integers that are congruent modulo 3.

	5,8
	-9,7
	-9,18
	0,37
	None of the above.

2 Choose the integers that are congruent modulo 6.

	5,8
	-9,7
	-9,18
	0,37
	None of the above.

3 Choose the integers that are congruent modulo 9.

	5,8
	-9,7
	-9,18
	0,37
	None of the above.

Example. (Clock arithmetic) A familiar application of the concept of congruence of integers is clock arithmetic. For instance, when we want to know adding 5 hours to 8 o'clock gives what time, we first calculate $8+5=13$. But $13>12$. So, we now think about 13 is congruent to which integer between 1 and 12. The integer is 1. Hence, the time is 1 o'clock.

In general, we can get the resulting time by performing the modulo operation, which gives the remainder when dividing the sum of the two numbers by 12 (called modulus). The notation for "$a$ modulo $n$" is $a{\text{ mod }}n$, which gives the remainder when $a$ is divided by $n$ ($a$ and $n$ are positive integers).

Now, let us apply direct proof to prove some results related to the congruence of integers.

Theorem. For every $a,b,c,d,k\in \mathbb {Z}$ and for every $n\in \mathbb {N}$ with $n\geq 2$, if $a\equiv b{\pmod {n}}$ and $c\equiv d{\pmod {n}}$, then

• (compatibility with addition) $a+c\equiv b+d{\pmod {n}}$.
• (compatibility with translation) $a+k\equiv b+k{\pmod {n}}$.
• (compatibility with scaling) $ka\equiv kb{\pmod {n}}$.
• (compatibility with multiplication) $ac\equiv bd{\pmod {n}}$.

(For the compatibility with translation and scaling, the assumption that $c\equiv d{\pmod {n}}$ is not needed.)

Proof. We will only prove the compatibility with addition and multiplication. The proof of other two compatibilities is left to the following exercise.

Compatibility with addition: Assume that $a\equiv b{\pmod {n}}$ and $c\equiv d{\pmod {n}}$. Then, $a-b=nk_{1}$ and $c-d=nk_{2}$ for some $k_{1},k_{2}\in \mathbb {Z}$. Thus, $$(a+c)-(b+d)=(a-b)+(c-d)=nk_{1}+nk_{2}=n(k_{1}+k_{2}).$$ Since $k_{1}+k_{2}\in \mathbb {Z}$, we have $a+c\equiv b+d{\pmod {n}}$.

Compatibility with multiplication: Assume that $a\equiv b{\pmod {n}}$ and $c\equiv d{\pmod {n}}$. Then, $a-b=nk_{1}$ and $c-d=nk_{2}$ for some $k_{1},k_{2}\in \mathbb {Z}$. Thus, $$ac-bd=ac{\color {darkgreen}-bc+bc}-bd=c(a-b)+b(c-d)=cnk_{1}+bnk_{2}=n(ck_{1}+bk_{2}).$$ Since $ck_{1}+bk_{2}\in \mathbb {Z}$, we have $ac\equiv bd{\pmod {n}}$.

$\Box$

Remark.

• We have applied the trick $ac-bd=ac{\color {darkgreen}-bc+bc}-bd$ in the proof of compatibility with multiplication. One can also prove it without using this trick. The details are left to the following exercise.

Exercise. Prove the compatibility with multiplication in the above theorem, without using the trick used in the above proof. (Hint: You may express $a$ in terms of $b$ and $c$ in terms of $d$ first.)

Proof

Assume that $a\equiv b{\pmod {n}}$ and $c\equiv d{\pmod {n}}$. Then, $a-b=nk_{1}$ and $c-d=nk_{2}$ for some $k_{1},k_{2}\in \mathbb {Z}$. That is, $a=b+nk_{1}$ and $c=d+nk_{2}$. Hence, $$ac-bd=(b+nk_{1})(d+nk_{2})-bd=bd+bnk_{2}+dnk_{1}+n^{2}k_{1}k_{2}-bd=n(bk_{2}+dk_{1}+nk_{1}k_{2}).$$ Since $bk_{2}+dk_{1}+nk_{1}k_{2}\in \mathbb {Z}$, we have $ac\equiv bd{\pmod {n}}$.

Exercise. Prove the compatibility with translation and scaling in the above theorem.

Proof

One can of course use direct proof and the definition of congruence of integers to prove them, but we will just apply the compatibility with addition and multiplication (which are proven) to prove them (they can be regarded as corollaries of the compatibility with addition and multiplication).

Proof. Assume $a\equiv b{\pmod {n}}$. Since $k-k=0(n)$, we have $k\equiv k{\pmod {n}}$. Hence, by the compatibility with addition, we have $a+k\equiv b+k{\pmod {n}}$. Also, by the compatibility with multiplication, we have $ka\equiv kb{\pmod {n}}$.

$\Box$

In the above result, everything is with the same "modulo $n$". It is then natural to ask whether there are any results for different "modulo". The answer is yes, and to discuss a result, we need the concept of relatively prime integers.

Definition. (Relatively prime integers) Two integers are relatively prime if their greatest common divisor is 1.

Remark.

• The integers are also called coprime or mutually prime.

Example.

• 2 and 3 are relatively prime.
• 4 and 12 are not relatively prime since their greatest common divisor is 4.
• 9 and 66 are not relatively prime since their greatest common divisor is 3.

Theorem. Two integers $a$ and $b$ are relatively prime if and only if there exist integers $x$ and $y$ such that $ax+by=1$.

Proof. Omitted.

$\Box$

Using this result, we can deduce the following result:

Theorem. For every $a,b,m,n\in \mathbb {Z}$ with $m,n\geq 2$, if $a\equiv b{\pmod {m}}$, $a\equiv b{\pmod {n}}$ and $m,n$ are relatively prime, then $a\equiv b{\pmod {mn}}$.

Proof. Assume $a\equiv b{\pmod {m}}$, $a\equiv b{\pmod {n}}$, and $m,n$ are relatively prime. Then, we have $a-b=k_{1}m$ and $a-b=k_{2}n$ for some $k_{1},k_{2}\in \mathbb {Z}$. This means $k_{1}m=k_{2}n$. Also, $mx+ny=1$ for some $x,y\in \mathbb {Z}$. Multiplying both sides by the integer $k_{1}$, we get $$xmk_{1}+ynk_{1}=k_{1}.$$ Putting $m={\frac {k_{2}n}{k_{1}}}$, we get $$xk_{2}n+ynk_{1}=k_{1}\implies n(xk_{2}+yk_{1})=k_{1}.$$ Putting this into $a-b=k_{1}m$, we get $$a-b=mn(xk_{2}+yk_{1}).$$ Since $xk_{2}+yk_{1}\in \mathbb {Z}$, we have $a\equiv b{\pmod {mn}}$.

$\Box$

Remark.

• This theorem says in particular if an integer is a multiple of $m$, and also a multiple of $n$, and $n$ and $n$ are relatively prime, then the integer is a multiple of $mn$.
• For example, if an inteeger is a multiple of 3 and also a multiple of 7, then the integer is a multiple of 21 since 3 and 7 are relatively prime.

Exercise. Give an example of integers $a,b,m,n$ such that $a\equiv b{\pmod {m}}$, $a\equiv b{\pmod {n}}$, $m$ and $n$ are not relatively prime, and $a\not \equiv b{\pmod {mn}}$.

Solution

Take $a=4,b=8,m=2,n=4$. Then, $4\equiv 8{\pmod {2}}$ and $4\equiv 8{\pmod {4}}$. However, $4\not \equiv 8{\pmod {8}}$.

Example. (Reflexivity, symmetry, and transitivity of the congruence of integers) Prove that for every $n\in \mathbb {N}$ with $n\geq 2$,

• (reflexivity) for every $a\in \mathbb {Z}$, $a\equiv a{\pmod {n}}$.
• (symmetry) for every $a,b\in \mathbb {Z}$, if $a\equiv b{\pmod {n}}$, then $b\equiv a{\pmod {n}}$.
• (transitivity) for every $a,b,c\in \mathbb {Z}$, if $a\equiv b{\pmod {n}}$ and $b\equiv c{\pmod {n}}$, then $a\equiv c{\pmod {n}}$.

(Since the congruence of integers satisfies these three properties, it is said to be an equivalence relation. We will discuss the concept of (equivalence) relation in a later chapter.)

Proof.

Reflexivity:

Since $a-a=0(n)$, we have $a\equiv a{\pmod {n}}$.

Symmetry:

Assume $a\equiv b{\pmod {n}}$. Then, $a-b=kn$ for some $k\in \mathbb {Z}$. Thus, $b-a=-kn$, and hence $b\equiv a{\pmod {n}}$ since $-k\in \mathbb {Z}$.

Transitivity:

Assume $a\equiv b{\pmod {n}}$ and $b\equiv c{\pmod {n}}$. Then, $a-b=k_{1}n$ and $b-c=k_{2}n$ for some $k_{1},k_{2}\in \mathbb {Z}$. Hence, $a-c=(a-b)-(b-c)=(k_{1}-k_{2})n$. Thus, $a\equiv c{\pmod {n}}$ since $k_{1}-k-2\in \mathbb {Z}$.

$\Box$

Remark.

• Notice that not all relations satisfy all these three properties. For instance, "$\neq$" does not satisfy the reflexivity and transitivity, "$<$" does not satisfy the reflexivity and symmetry.

Example. Applying the compatibility with multiplication in the above theorem, we can get the following result:

Let $a$ be an integer, $m$ be a nonnegative integer, and $n\in \mathbb {N}$ with $n\geq 2$. If $a\equiv 1{\pmod {n}}$, then $a^{m}\equiv 1{\pmod {n}}$.

We can prove it (a bit informally) as follows:

Proof. Assume $a\equiv 1{\pmod {n}}$. First, $a^{0}=1\equiv 1{\pmod {n}}$. Second, we have $a\cdot a\equiv 1\cdot 1{\pmod {n}}\implies a^{2}\equiv 1{\pmod {n}}$. Applying this argument again, we get $a^{2}\cdot a\equiv 1\cdot 1{\pmod {n}}\implies a^{3}\equiv 1{\pmod {n}}$. Thus, we have $a^{m}\equiv 1{\pmod {n}}$ for every nonnegative integer $m$ by applying the argument "again and again".

$\Box$

To prove the result formally, we need to use proof by mathematical induction, which will be discussed later.

Example.

(a) Consider the remainder of $3^{n}$ when divided by 4 (i.e., $3^{n}{\text{ mod }}4$) for $n=0,1,2,3,4,5$. Do you observe any pattern? Hence, suggest a conjecture.

(b) Prove the conjecture.

Solution.

(a) We have $${\begin{array}{c|cccccc}n&0&1&2&3&4&5\\\hline 3^{n}{\text{ mod }}4&1&3&1&3&1&3\\\end{array}}$$ Notice that the remainder is 1 for $n=0,2,4$, and 3 for $n=1,3,5$. It is thus natural to expect that the same pattern continue for all other larger integers. Thus, a conjecture is

Let $n$ be a nonnegative integer. If $n$ is even, then $3^{n}\equiv 1{\pmod {4}}$. Also, if $n$ is odd, then $3^{n}\equiv 3{\pmod {4}}$.

(b) We will just prove "If $n$ is even, then $3^{n}\equiv 1{\pmod {4}}$.". The proof of the second part is left to the following exercise.

Proof. Assume $n$ is even. Then, $n=2k$ for some nonnegative integer $k$ ($n$ is a nonnegative integer). It follows that $3^{n}=3^{2k}=9^{k}$. Since $9\equiv 1{\pmod {4}}$, it follows that $9^{k}\equiv 1{\pmod {4}}$ by the result in previous example. Hence, $3^{n}\equiv 1{\pmod {4}}$.

$\Box$

Exercise. Prove the second part in the above conjecture.

Proof

Proof. Assume $n$ is odd. Then, $n=2k+1$ for some nonnegative integer $k$. It follows that $3^{n}=3^{2k+1}=3\cdot 9^{k}$. From the prove above, we have $9^{k}\equiv 1{\pmod {4}}$. Thus, we get $3\cdot 9^{k}\equiv 3\cdot 1{\pmod {4}}\implies 3^{n}\equiv 3{\pmod {4}}$.

$\Box$

The following lemma is quite useful for proving results about congruence of integers.

Lemma. (Euclid's division lemma) For every integer $a$ and $b$ with $b\neq 0$, there exists a unique pair of integers $q$ and $r$ such that $$a=bq+r{\text{ and }}0\leq r<|b|.$$

Proof. We separate the proof into existence part and uniqueness part.

Existence part:

Case 1: $b<0$.

Then, we set $b'=-b>0$ and $q'=-q$. After that, the equation $a=bq+r$ can be rewritten equivalently as $a=b'q'+r$, and also the inequality $0\leq r\leq |b'|$ can be rewritten equivalently as $0\leq r\leq |b'|$. Through this, we transform this case to case 2.

Case 2: $b>0$.

Subcase 1: $a<0$ and $b>0$.

Then, we set $a'=-a$, $q'=-q-1$, and $r'=b-r$. After that, the equation $a=bq+r$ can be rewritten equivalently as $a'=bq'+r'$ (this is equivalent to $-a=-bq-r$). Also, the inequality $0\leq r\leq |b'|$ can be rewritten equivalently as $0\leq r'<|b|$. Through this, we transform this case to the subcase 2.

Subcase 2: $a\geq 0$ and $b>0$.

Set $q_{1}=0$ and $r_{1}=a\geq 0$. Then, we have $a=bq_{1}+r_{1}$.

Subsubcase 1: $r_{1}<b=|b|$. Take $q=q_{1}$ and $r=r_{1}$. Then, we have $$a=bq+r{\text{ and }}0\leq r<|b|,$$ and we are done.

Subsubcase 2: $r_{1}\geq b$.

Set $q_{2}=q_{1}+1$ and $0\leq r_{2}=r_{1}-b<r_{1}$. Then, we have $a=bq_{2}+r_{2}$ with $0\leq r_{2}<r_{1}$. Since there are exactly $r_{1}$ nonnegative integers less than $r_{1}$, we need to repeat this process at most $r_{1}$ times ($b\geq 1$, so $r_{2}$ is at most the preceding integer of $r_{1}$) to get a $r_{k}$ such that $0\leq r_{k}<|b|$ (and also a $q_{k}$).

So, we take $q=q_{k}$ and $r=r_{k}$. Then, we have $$a=bq+r{\text{ and }}0\leq r<|b|,$$ and we are done.

Uniqueness part:

Assume there exists another pair of integers $q^{*}$ and $r^{*}$ (in addition to the pair of integers $q$ and $r$) such that $$a=bq^{*}+r^{*}{\text{ and }}0\leq r^{*}<|b|.$$ Since we have also $$a=bq+r{\text{ and }}0\leq r<|b|,$$ we get, by subtracting the two equations, $$0=b(q-q^{*})+r-r^{*}\implies b(q-q^{*})=r^{*}-r.$$

Also, by considering the above two inequalities, we get $${\begin{aligned}&&0\leq &|r^{*}-r|<|b|\\&\Rightarrow &0\leq &|b(q-q^{*})|<|b|\\&\Rightarrow &0\leq &|b||q-q^{*}|<|b|\\&\Rightarrow &0\leq &|q-q^{*}|<1&(b\neq 0)\\&\Rightarrow &&|q-q^{*}|=0\\&\Rightarrow &&q=q^{*}.\\\end{aligned}}$$ Putting it in the above equation, we get $0=r^{*}-r\implies r=r^{*}$.

Thus, we have $q=q^{*}$ and $r=r^{*}$.

$\Box$

Remark.

• This lemma is the basis of Euclidean division, as known as division with remainder.
• $a$ is called the dividend, $b$ is called the divisor, $q$ is called the quotient, and $r$ is called the remainder.
• We employ the method of proof by cases in the proof, which is not a "new" way of proof strictly speaking. We just consider different cases in the proof. However, when we use this method, we need to ensure that the cases covers all possibilities for the "for every", so that we actually prove the statement.
• From this lemma, we know that every integer has remainder either 0 or 1 or 2 or ... or $n-1$ (from the inequality $0\leq r<|n|$) when divided by an integer $n$ with $n\geq 2$. In other words, for every integer $x$, we have either $x\equiv 0{\pmod {n}}$ or $x\equiv 1{\pmod {n}}$ or ... or $x\equiv n-1{\pmod {n}}$. For brevity, we can also write $x\equiv 0{\text{ or }}1{\text{ or }}\cdots {\text{ or }}n-1{\pmod {n}}$.

Example. Prove that for every integer $n$, $n^{2}\equiv 0{\text{ or }}1{\pmod {4}}$.

Proof. By Euclid's division lemma, we have $n\equiv 0{\text{ or }}1{\text{ or }}2{\text{ or }}3{\pmod {4}}$. Thus, we have $n^{2}\equiv 0{\text{ or }}1{\text{ or }}4{\text{ or }}9{\pmod {4}}$. But $4\equiv 0{\pmod {4}}$ and $9\equiv 1{\pmod {4}}$. So, the result follows by the transitivity of the congruence of integers.

$\Box$

Exercise. Propose a similar result for the congruence modulo 5, and prove it.

Solution

Proposition: For every integer $n$, $n^{2}\equiv 0{\text{ or }}1{\text{ or }}4{\pmod {5}}$.

Proof. By Euclid's division lemma, we have $n\equiv 0{\text{ or }}1{\text{ or }}2{\text{ or }}3{\text{ or }}4{\pmod {5}}$. Thus, we have $n^{2}\equiv 0{\text{ or }}1{\text{ or }}4{\text{ or }}9{\text{ or }}16{\pmod {5}}$. But $9\equiv 4{\pmod {5}}$ and $16\equiv 1{\pmod {5}}$. So, the result follows.

$\Box$

Proofs related to sets

The proofs related to sets are often in the form of

1. A set is a subset of another set.
2. A set equals another set.

To prove that a set is a subset of another set, we use the definition of subset:

A set $X$ is a subset of another set $Y$ if for every element $x$, if $x\in X$, then $x\in Y$.

Thus, we can employ direct proof to prove that a set is a subset of another set.

For the equality of two sets, recall that:

A set $X$ equals another set $Y$ if and only if $X\subseteq Y$ and $Y\subseteq X$.

Thus, to prove the equality of two sets, we often need to separate the proof into two parts: (i) proving that $X\subseteq Y$; (ii) proving that $Y\subseteq X$.

Example. (Transitivity of "$\subseteq$") Prove that for every set $A,B$ and $C$, if $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$.

Proof. Assume $A\subseteq B$ and $B\subseteq C$. Then, for every $x$, $$x\in A{\overset {A\subseteq B}{\implies }}x\in B{\overset {B\subseteq C}{\implies }}x\in C,$$ and hence $A\subseteq C$.

$\Box$

Example. (Associative law) Prove that for every set $A,B$ and $C$, $A\cup (B\cup C)=(A\cup B)\cup C$.

Proof. First, we prove that $A\cup (B\cup C)\subseteq (A\cup B)\cup C$. For every $x$, $${\begin{aligned}x\in A\cup (B\cup C)&\implies (x\in A){\text{ or }}(x\in B{\text{ or }}x\in C)\\&\implies (x\in A{\text{ or }}x\in B){\text{ or }}x\in C&({\text{Associative law of disjunction}})\\&\implies x\in (A\cup B)\cup C.\end{aligned}}$$ Thus, we have $A\cup (B\cup C)\subseteq (A\cup B)\cup C$.

Now, we prove the reverse subset inclusion, i.e., $(A\cup B)\cup C\subseteq A\cup (B\cup C)$. For every $x$, $${\begin{aligned}x\in (A\cup B)\cup C&\implies (x\in A{\text{ or }}x\in B){\text{ or }}x\in C\\&\implies x\in A{\text{ or }}(x\in B{\text{ or }}x\in C)&({\text{Associative law of disjunction}})\\&\implies x\in A\cup (B\cup C).\end{aligned}}$$ Thus, we have $(A\cup B)\cup C\subseteq A\cup (B\cup C)$.

$\Box$

Notice that the proof for reverse subset inclusion is very similar to the proof for the first part. Indeed, it is just a reverse of the proof for the first part. Hence, we can actually simplify the proof as follows:

Proof. For every $x$, $${\begin{aligned}x\in A\cup (B\cup C)&\iff (x\in A){\text{ or }}(x\in B{\text{ or }}x\in C)\\&\iff (x\in A{\text{ or }}x\in B){\text{ or }}x\in C&({\text{associative law of disjunction}})\\&\iff x\in (A\cup B)\cup C.\end{aligned}}$$ Thus, we have $A\cup (B\cup C)=(A\cup B)\cup C$.

$\Box$

Using this proof, we can prove the set equality directly (set $A$ equals set $B$ if for every $x$, $x\in A\iff x\in B$). (However, we should be careful about whether we really have "$\iff$".) But, in many cases, the proof for reverse subset inclusion is not just simply obtained by reversing the proof for the first part, and we have to separate the proof into proofs for two subset inclusions.

We can observe that to prove different laws for the sets, we just simply use the corresponding laws in logic to prove them. Hence, the proofs for other laws, e.g., commutative law and distributive law, are similar.

Exercise. (De Morgan's law) Let $A$ and $B$ subsets of a universal set $U$. Prove that $(A\cup B)^{c}=A^{c}\cap B^{c}$.

Proof

Proof. For every $x$, $${\begin{aligned}x\in (A\cup B)^{c}&\iff x\in U{\text{ and }}(x\notin A\cup B)\\&\iff x\in U{\text{ and }}{\big (}\sim (x\in A{\text{ or }}x\in B){\big )}\\&\iff x\in U{\text{ and }}{\big (}\sim (x\in A){\text{ and }}\sim (x\in B){\big )}&({\text{De Morgan's law in logic}})\\&\iff x\in U{\text{ and }}{\big (}x\notin A{\text{ and }}x\notin B{\big )}\\&\iff {\big (}x\in U{\text{ and }}{\big (}x\notin A{\big )}{\text{ and }}{\big (}x\in U{\text{ and }}x\notin B{\big )}\\&\iff x\in A^{c}{\text{ and }}x\in B^{c}\\&\iff x\in A^{c}\cap B^{c}.\end{aligned}}$$

$\Box$

Example. Let $A$ and $B$ be subsets of a universal set $U$. Prove that $A\setminus B=A\cap B^{c}$.

Proof. For every $x$, $$x\in A\setminus B\iff (x\in A{\text{ and }}x\notin B)\iff (x\in A{\text{ and }}x\in B^{c})\iff x\in A\cap B^{c}.$$

$\Box$

Exercise. Using this result, prove that $(A\cup B)\setminus (A\cap B)=(A\setminus B)\cup (B\setminus A)$. (Hint: you may use the laws in set theory in the proof.)

Proof

Here, we just use the laws of in set theory to prove the equality of sets: $${\begin{aligned}(A\cup B)\setminus (A\cap B)&=(A\cup B)\cap (A\cap B)^{c}\\&=(A\cup B)\cap (A^{c}\cup B^{c})&({\text{De Morgan's law}})\\&={\big (}(A\cup B)\cap A^{c}{\big )}\cup {\big (}(A\cup B)\cap B^{c}{\big )}&({\text{Distributive law}})\\&={\big (}(A\cap A^{c})\cup (B\cap A^{c}){\big )}\cup {\big (}(A\cap B^{c})\cup (B\cap B^{c}){\big )}&({\text{Distributive law}})\\&={\big (}\varnothing \cup (B\cap A^{c}){\big )}\cup {\big (}(A\cap B^{c})\cup \varnothing {\big )}\\&=(B\cap A^{c})\cup (A\cup B^{c})\\&=(B\setminus A)\cup (A\setminus B).&({\text{above result}})\end{aligned}}$$

Example. Prove that for every set $A$ and $B$, $A\subseteq A\cup B$ and $A\cap B\subseteq A$.

Proof. For the first one, for every $x$, $$x\in A\implies x\in A{\text{ or }}x\in B\implies x\in A\cup B.$$ (no matter $x\in B$ is true or false, we always have the first implication.)

For the second one, for every $x$, $$x\in A\cap B\implies x\in A{\text{ and }}x\in B\implies x\in A.$$

$\Box$

Exercise.

(a) Propose an assumption on the sets $A$ and $B$ such that we have both reverse subset inclusions, i.e., $A\cup B\subseteq A$ and $A\subseteq A\cap B$. Prove them under this assumption.

(b) Propose an assumption on the sets $A$ and $B$ such that we have $A\cup B\subseteq A$ (the another reverse subset inclusion may or may not hold). Prove it under this assumption.

(c) Propose an assumption on the sets $A$ and $B$ such that we have $A\subseteq A\cap B$ (the another reverse subset inclusion may or may not hold). Prove it under this assumption.

(The assumptions proposed should be as weak (recall the meaning of weak in logic) as possible, so that the result can apply in more contexts.)

Solution

(a) Assumption: $A=B$.

Proof. Assume $A=B$. For the first one, for every $x$, $$x\in A\cup B\implies x\in A{\text{ or }}x\in B\implies x\in A{\text{ or }}x\in A\implies x\in A.$$ For the second one, for every $x$, $$x\in A\implies x\in A{\text{ and }}x\in A\implies x\in A{\text{ and }}x\in B\implies x\in A\cap B.$$

$\Box$

(One can also use the some results in set theory (e.g. $A\cup A=A$, $A\cap A=A$, etc.) in the proof.)

(b) Assumption: $B\subseteq A$.

Proof. Assume $B\subseteq A$. Then, for every $x$, $$x\in A\cup B\implies x\in A{\text{ or }}x\in B\implies x\in A{\text{ or }}x\in A\implies x\in A.$$

$\Box$

(c) Assumption: $A\subseteq B$.

Proof. Assume $A\subseteq B$. Then, for every $x$, $$x\in A\implies x\in A{\text{ and }}x\in B\implies x\in A\cap B.$$ (We have the first implication, since if $x\in A$, then we have $x\in A$, and also $x\in B$ since $A\subseteq B$)

$\Box$

Exercise. Consider the statement: for every set $A,B$ and $C$, $A\setminus (B\setminus C)=(A\setminus C)\setminus (B\setminus C)$. A student gives the following proof:

Proof. For every $x$, $${\begin{aligned}x\in (A\setminus B)\setminus C&\iff x\in A\setminus B{\text{ and }}x\notin C\\&\iff x\in A{\text{ and }}x\notin B{\text{ and }}x\notin C\\&\iff (x\in A{\text{ and }}x\notin C){\text{ and }}x\notin B\\&\iff (x\in A{\text{ and }}x\notin C){\text{ and }}x\notin B\setminus C&(B\setminus C\subseteq B,{\text{ and consider contrapositive}})\\&\iff x\in A\setminus C{\text{ and }}x\notin B\setminus C\\&\iff x\in (A\setminus C)\setminus (B\setminus C).\\\end{aligned}}$$

$\Box$

Is the proof correct? If not, point out the mistake and give a correct proof.

Solution

The mistake is in this step: $$(x\in A{\text{ and }}x\notin C){\text{ and }}x\notin B\iff (x\in A{\text{ and }}x\notin C){\text{ and }}x\notin B\setminus C\quad (B\setminus C\subseteq B,{\text{ and consider contrapositive}}).$$ We have "$\Longrightarrow$", but do not necessarily have "$\Longleftarrow$", since we generally do not have $B\subseteq B\setminus C$, and thus we cannot show "$\Longleftarrow$" by contrapositive.

The following is a correct proof:

Proof. For every $x$, $${\begin{aligned}x\in (A\setminus B)\setminus C&\implies x\in A\setminus B{\text{ and }}x\notin C\\&\implies x\in A{\text{ and }}x\notin B{\text{ and }}x\notin C\\&\implies (x\in A{\text{ and }}x\notin C){\text{ and }}x\notin B\\&\implies (x\in A{\text{ and }}x\notin C){\text{ and }}x\notin B\setminus C&(B\setminus C\subseteq B,{\text{ and consider contrapositive}})\\&\implies x\in A\setminus C{\text{ and }}x\notin B\setminus C\\&\implies x\in (A\setminus C)\setminus (B\setminus C).\\\end{aligned}}$$ On the other hand, for every $x$, $${\begin{aligned}x\in (A\setminus C)\setminus (B\setminus C)&\implies x\in A\setminus C{\text{ and }}x\notin B\setminus C\\&\implies (x\in A{\text{ and }}x\notin C){\text{ and }}x\notin B\setminus C\\&\implies (x\in A{\text{ and }}x\notin C){\text{ and }}(x\notin B{\text{ or }}x\in C)&({\text{De Morgan's law}})\\&\implies (x\in A{\text{ and }}x\notin C){\text{ and }}x\notin B){\text{ or }}(x\in A{\text{ and }}x\notin C{\text{ and }}x\in C)&({\text{De Morgan's law}})\\&\implies (x\in A{\text{ and }}x\notin B{\text{ and }}x\notin C){\text{ or }}\mathbf {F} \\&\implies x\in A{\text{ and }}x\notin B{\text{ and }}x\notin C\\&\implies x\in A\setminus B{\text{ and }}x\notin C\\&\implies x\in (A\setminus B)\setminus C.\end{aligned}}$$

$\Box$

Example. Prove that for every set $A,B,C$ and $D$, if $A\subseteq C$ and $B\subseteq D$, then $A\times B\subseteq C\times D$.

Proof. For every $(x,y)$, $${\begin{aligned}(x,y)\in A\times B&\implies x\in A{\text{ and }}y\in B\\&\implies x\in C{\text{ and }}y\in D&(A\subseteq C{\text{ and }}B\subseteq D)\\&\implies (x,y)\in C\times D.\end{aligned}}$$

$\Box$

Example. Prove that for every set $A,B$ and $C$, $A\times (B\cup C)=(A\times B)\cup (A\times C)$.

Proof. For every $(x,y)$, $${\begin{aligned}(x,y)\in A\times (B\cup C)&\implies x\in A{\text{ and }}y\in B\cup C\\&\implies x\in A{\text{ and }}(y\in B{\text{ or }}y\in C)\\&\implies (x\in A{\text{ and }}y\in B){\text{ or }}(x\in A{\text{ and }}y\in C)&({\text{Distributive law}})\\&\implies (x,y)\in A\times B{\text{ or }}(x,y)\in A\times C\\&\implies (x,y)\in (A\times B)\cup (A\times C).\end{aligned}}$$

$\Box$

Exercise. Prove that for every set $A,B$ and $C$,

(a) $A\times (B\setminus C)=(A\times B)\setminus (A\times C)$.

(b) $A\times (B\cap C)=(A\times B)\cap (A\times C)$.

Solution

(a)

Proof. For every $(x,y)$, $${\begin{aligned}(x,y)\in A\times (B\setminus C)&\implies x\in A{\text{ and }}y\in B\setminus C\\&\implies x\in A{\text{ and }}y\in B{\text{ and }}y\notin C\\&\implies (x,y)\in A\times B{\text{ and }}(x,y)\notin A\times C&(y\notin C)\\&\implies (x,y)\in (A\times B)\setminus (A\times C).\end{aligned}}$$ (Notice that for the third "$\implies$", we cannot change it to "$\iff$" since $(x,y)\notin A\times C\not \implies y\notin C$.)

On the other hand, for every $(x,y)$, $${\begin{aligned}(x,y)\in (A\times B)\setminus (A\times C)&\implies (x\in A{\text{ and }}y\in B){\text{ and }}(x\notin A{\text{ or }}y\notin C)&({\text{De Morgan's law}})\\&\implies (x\in A{\text{ and }}y\in B{\text{ and }}x\notin A){\text{ or }}(x\in A{\text{ and }}y\in B{\text{ and }}y\notin C)&({\text{Distributive law}})\\&\implies \mathbf {F} {\text{ or }}(x\in A{\text{ and }}y\in B\setminus C)\\&\implies (x,y)\in A\times (B\setminus C).\end{aligned}}$$

$\Box$

(b)

Proof. For every $(x,y)$, $${\begin{aligned}(x,y)\in A\times (B\cap C)&\iff x\in A{\text{ and }}y\in B\cap C\\&\iff x\in A{\text{ and }}y\in B{\text{ and }}y\in C\\&\iff (x\in A{\text{ and }}y\in B){\text{ and }}(x\in A{\text{ and }}y\in C)\\&\iff (x,y)\in A\times B{\text{ and }}(x,y)\in A\times C\\&\iff (x,y)\in (A\times B)\cap (A\times C).\end{aligned}}$$

$\Box$

Exercise. Consider the statement:

For every set $A,B$ and $C$, if $A\times C=B\times C$ and $C\neq \varnothing$, then $A=B$.

A student provides the following proof:

Proof. Assume $A\times C=B\times C$ and $C\neq \varnothing$. For every $a$, $${\begin{aligned}a\in A&\iff (a,c)\in A\times C&(C\neq \varnothing ,{\text{ so we can pick }}c\in C)\\&\iff (a,c)\in B\times C&(A\times C=B\times C)\\&\iff a\in B.\end{aligned}}$$

$\Box$

Is the proof correct? If not, point out the mistake and give a correct proof.

Solution

The proof is correct.

Example. Prove that $(A\times B)\cap (C\times D)=(A\cap C)\times (B\cap D)$ for every set $A,B,C$ and $D$.

Proof. For every $(x,y)$, $${\begin{aligned}(x,y)\in (A\times B)\cap (C\times D)&\iff (x,y)\in A\times B{\text{ and }}(x,y)\in C\times D\\&\iff (x\in A{\text{ and }}y\in B){\text{ and }}(x\in C{\text{ and }}y\in D)\\&\iff (x\in A{\text{ and }}x\in C){\text{ and }}(y\in B{\text{ and }}y\in D)\\&\iff x\in A\cap C{\text{ and }}y\in B\cap D\\&\iff (x,y)\in (A\cap C)\times (B\cap D).\\\end{aligned}}$$

$\Box$

Exercise. Prove that $(A\times B)\cup (C\times D)\subseteq (A\cup C)\times (B\cup D)$ for every set $A,B,C$ and $D$. (Hint: you may find the property $P{\text{ or }}Q\implies P$ useful.)

Proof

Proof. For every $(x,y)$, $${\begin{aligned}(x,y)\in (A\times B)\cup (C\times D)&\implies (x,y)\in A\times B{\text{ or }}(x,y)\in C\times D\\&\implies (x,y)\in A\times B\\&\implies x\in A{\text{ and }}y\in B\\&\implies x\in A\cup C{\text{ and }}y\in B\cup D\\&\implies (x,y)\in (A\cup C)\times (B\cup D).\end{aligned}}$$

$\Box$

Remark.

• The reverse subset inclusion does not hold. For instance, take $A=\{1\},B=\{2\},C=\{3\}$ and $D=\{4\}$. Then, $(A\times B)\cup (C\times D)=\{(1,2),(3,4)\}$ and $(A\cup C)\times (B\cup D)=\{1,3\}\times \{2,4\}=\{(1,2),(1,4),(3,2),(3,4)\}$. We can see that there is not reverse subset inclusion in this case.

Example. Let $A$ and $B$ be sets. Prove that $A\subseteq B$ if and only if ${\mathcal {P}}(A)\subseteq {\mathcal {P}}(B)$.

Proof. "$\Rightarrow$" direction: Assume $A\subseteq B$. Then, for every set $X$, $${\begin{aligned}X\in {\mathcal {P}}(A)&\implies X\subseteq A\\&\implies X\subseteq B&(A\subseteq B,{\text{ and transitivity of }}\subseteq )\\&\implies X\in {\mathcal {P}}(B).\end{aligned}}$$ Thus, we have ${\mathcal {P}}(A)\subseteq {\mathcal {P}}(B)$.

"$\Leftarrow$" direction: Assume ${\mathcal {P}}(A)\subseteq {\mathcal {P}}(B)$. Then, for every $x$, $${\begin{aligned}x\in A&\implies \{x\}\subseteq A&({\text{trick}})\\&\implies \{x\}\in {\mathcal {P}}(A)\\&\implies \{x\}\in {\mathcal {P}}(B)&({\mathcal {P}}(A)\subseteq {\mathcal {P}}(B))\\&\implies \{x\}\subseteq B\\&\implies x\in B.\end{aligned}}$$ Thus, $A\subseteq B$.

$\Box$

We can also prove the "$\Leftarrow$" direction more simply:

Assume ${\mathcal {P}}(A)\subseteq {\mathcal {P}}(B)$. Since for every set $X$, $X\subseteq X$, and thus $X\in {\mathcal {P}}(X)$, we have $${\begin{aligned}A\in {\mathcal {P}}(A)&\implies A\in {\mathcal {P}}(B)&({\mathcal {P}}(A)\subseteq {\mathcal {P}}(B))\\&\implies A\subseteq B.&({\text{transitivity of }}\subseteq )\end{aligned}}$$

Exercise. Let $A$ and $B$ be sets.

(a) Prove that ${\mathcal {P}}(A)\cap {\mathcal {P}}(B)={\mathcal {P}}(A\cap B)$.

(b) Give an example of $A$ and $B$ such that ${\mathcal {P}}(A)\cup {\mathcal {P}}(B)\neq {\mathcal {P}}(A\cup B)$.

(c) We will have ${\mathcal {P}}(A)\cup {\mathcal {P}}(B)={\mathcal {P}}(A\cup B)$ under an assumption. Propose an assumption, and prove the equality under the assumption. (Hint: construct some simple examples to observe whether there are any patterns.)

Solution

(a)

Proof. Claim: $X\subseteq A{\text{ and }}X\subseteq B\iff X\subseteq A\cap B$.

Proof. "$\Rightarrow$" direction: Assume $X\subseteq A{\text{ and }}X\subseteq B$. Then, for every $x$, $x\in X\implies x\in A{\text{ and }}x\in B\implies x\in A\cap B$. So, $X\subseteq A\cap B$.

"$\Leftarrow$" direction: Assume $X\subseteq A\cap B$. Then, for every $x$, $x\in X\implies x\in A\cap B\implies x\in A$. Also, $x\in X\implies x\in A\cap B\implies x\in B$. Hence, $X\subseteq A$ and $X\subseteq B$.

$\Box$

For every set $X$, $${\begin{aligned}X\in {\mathcal {P}}(A)\cap {\mathcal {P}}(B)&\iff X\in {\mathcal {P}}(A){\text{ and }}X\in {\mathcal {P}}(B)\\&\iff X\subseteq A{\text{ and }}X\subseteq B\\&\iff X\subseteq A\cap B\\&\iff X\in {\mathcal {P}}(A\cap B).\\\end{aligned}}$$

$\Box$

(b) Take $A=\{1\}$ and $B=\{2\}$. Then, ${\mathcal {P}}(A)\cup {\mathcal {P}}(B)=\{\varnothing ,\{1\},\{2\}\}$, while ${\mathcal {P}}(A\cup B)={\mathcal {P}}(\{1,2\})=\{\varnothing ,\{1\},\{2\},\{1,2\}\}$.

(c) An assumption is "$A\subseteq B$ or $B\subseteq A$".

Proof. Assume $A\subseteq B$ or $B\subseteq A$.

Case 1: $A\subseteq B$.

Then, $A\cup B=B$. Hence, ${\mathcal {P}}(A\cup B)={\color {blue}{\mathcal {P}}(B)}$. On the other hand, by the above example, we have $A\subseteq B\implies {\mathcal {P}}(A)\subseteq {\mathcal {P}}(B)$, and thus ${\mathcal {P}}(A)\cup {\mathcal {P}}(B)={\color {blue}{\mathcal {P}}(B)}$. Therefore, ${\mathcal {P}}(A)\cup {\mathcal {P}}(B)={\mathcal {P}}(A\cup B)$.

Case 2: $B\subseteq A$.

The proof is similar (just interchange "$A$" and "$B$").

$\Box$

Proof by contrapositive

Recall that the contrapositive of a conditional $P\to Q$ is the statement $\sim Q\to \;\sim P$, which is logically equivalent to the original conditional $P\to Q$. Hence, if we can show that $\sim Q\implies \sim P$, then it follows that $P\implies Q$. This gives us another method of proof, namely proof by contrapositive.

A proof by contrapositive of the statement $\forall x\in S,P(x)\implies Q(x)$ is a direct proof of $\forall x\in S,\sim Q(x)\implies \sim P(x)$. That is, we first assume that $\sim Q(x)$ is true, and proceed to show that $\sim P(x)$ is true. In other words, we first assume that $Q(x)$ is false, and proceed to show that $P(x)$ is false.

Generally, when we encounter a statement $\forall x\in S,P(x)\implies Q(x)$, and observe that the consequent $Q(x)$ is "simpler" than the hypothesis $P(x)$, using proof by contrapositive is usually more preferable.

Example. Prove that for every $n\in \mathbb {Z}$, if $3n+1$ is even, then $n$ is odd.

Proof. Here, we use proof by contrapositive, that is we will prove that "for every $n\in \mathbb {Z}$, if $n$ is even, then $3n+1$ is odd."

Assume $n$ is even. Then, $n=2k$ for some $k\in \mathbb {Z}$. Thus, $3n+1=6k+1=2(3k)+1$, and hence $3n+1$ is odd since $3k\in \mathbb {Z}$.

$\Box$

Remark.

• Using proof by contrapositive here allows us to work with with $n$ initially, instead of the more complicated expression $3n+1$.

Example. Prove that for every $n\in \mathbb {Z}$, $n$ is even if and only if $n^{2}$ is even.

Proof. "$\Rightarrow$" direction (or "only if" part):

Assume $n$ is even. Then, $n=2k$ for some $k\in \mathbb {Z}$. Thus, $n^{2}=4k^{2}=2(2k^{2})$. Hence, $n^{2}$ is even since $k^{2}\in \mathbb {Z}$.

"$\Leftarrow$" direction (or "if" part):

We use proof by contrapositive, i.e., we will prove that "for every $n\in \mathbb {Z}$, if $n$ is odd, then $n^{2}$ is odd." Now, assume $n$ is odd. Then, $n=2k'+1$ for some $k'\in \mathbb {Z}$. Hence, $n^{2}=4k'^{2}+4k'+1=2(2k'^{2}+2k')+1$, and so $n^{2}$ is odd since $2k'^{2}+2k'\in \mathbb {Z}$.

$\Box$

Remark.

• Using proof by contrapositive for the "$\Leftarrow$" direction allows us to work with $n$, instead of $n^{2}$, initially.
• The statement is logically equivalent to "for every $n\in \mathbb {Z}$, $n$ is odd if and only if $n^{2}$ is odd." (since $P\leftrightarrow Q\iff \sim P\leftrightarrow \;\sim Q$).

Example. Prove that for every $n\in \mathbb {Z}$, $n^{2}\equiv 0{\pmod {4}}$ if and only if $n\equiv 0{\text{ or }}2{\pmod {4}}$.

Proof.

"$\Rightarrow$" direction:

We use proof by contrapositive. First, assume $n\not \equiv 0{\pmod {4}}{\text{ and }}n\not \equiv 2{\pmod {4}}$. Since $n\equiv 0{\text{ or }}1{\text{ or }}2{\text{ or }}3{\pmod {4}}$ by Euclid's division lemma, we have $n\equiv 1{\text{ or }}3{\pmod {4}}$. Hence, $n^{2}\equiv 1{\text{ or }}9{\pmod {4}}$. But $9\equiv 1{\pmod {4}}$. It follows that $n^{2}\equiv 1{\pmod {4}}$, and hence $n^{2}\not \equiv 0{\pmod {4}}$.

"$\Leftarrow$" direction:

Assume $n\equiv 0{\text{ or }}2{\pmod {4}}$. Then, we have $n^{2}\equiv 0{\text{ or }}4{\pmod {4}}$. But $4\equiv 0{\pmod {4}}$. So, we have $n^{2}\equiv 0{\pmod {4}}$.

$\Box$

Exercise. Prove that $n^{2}\equiv 1{\pmod {4}}$ if and only if $n\equiv 1{\text{ or }}3{\pmod {4}}$.

Proof

Proof.

"$\Rightarrow$" direction:

We use proof by contrapositive. First, assume $n\not \equiv 1{\pmod {4}}{\text{ and }}n\not \equiv 3{\pmod {4}}$. Since $n\equiv 0{\text{ or }}1{\text{ or }}2{\text{ or }}3{\pmod {4}}$ by Euclid's division lemma, we have $n\equiv 0{\text{ or }}2{\pmod {4}}$. Hence, $n^{2}\equiv 0{\text{ or }}4{\pmod {4}}$. But $4\equiv 0{\pmod {4}}$. It follows that $n^{2}\equiv 0{\pmod {4}}$, and hence $n^{2}\not \equiv 1{\pmod {4}}$.

"$\Leftarrow$" direction:

Assume $n\equiv 1{\text{ or }}3{\pmod {4}}$. Then, we have $n^{2}\equiv 1{\text{ or }}9{\pmod {4}}$. But $9\equiv 1{\pmod {4}}$. So, we have $n^{2}\equiv 1{\pmod {4}}$.

$\Box$

Notice that we can also apply the fact that $n^{2}\equiv 0{\text{ or }}1{\pmod {4}}$ (proved before) to conclude that $n^{2}\not \equiv 1{\pmod {4}}\iff n^{2}\equiv 0{\pmod {4}}$. Then, we can see that this statement is just logically equivalent to the above statement (since $P\leftrightarrow Q\iff \sim P\leftrightarrow \;\sim Q$).

Example. Let $A$ and $B$ be sets. Prove that $A\cup B=B$ if and only if $A\subseteq B$.

Proof.

"$\Rightarrow$" direction:

We use proof by contrapositive. Assume $A\not \subseteq B$, i.e., there exists an element $a\in A$ such that $a\notin B$. Since $a\in A$, it follows that $a\in A\cup B$. But $a\notin B$. So, $A\cup B\neq B$.

"$\Leftarrow$" direction:

Assume $A\subseteq B$. Since $B\subseteq A\cup B$ holds for every set $A$ and $B$, it suffices to show that $A\cup B\subseteq B$:

For every $x$, $${\begin{aligned}x\in A\cup B&\implies x\in A{\text{ or }}x\in B\\&\implies x\in B{\text{ or }}x\in B.&(A\subseteq B)\\&\implies x\in B.\end{aligned}}$$ So, $A\cup B\subseteq B$.

$\Box$

Exercise. Prove that for every set $A$ and $B$, if $(A\times B)\cap (B\times A)=\varnothing$, then $A\cap B=\varnothing$. (Hint: $A\cap B\neq \varnothing$ means that there exists an element $x$ such that $x\in A$ and $x\in B$.)

Proof

Proof. "$\Rightarrow$" direction:

We use proof by contrapositive. Assume $A\cap B\neq \varnothing$. Then, there exists an element $x$ such that $x\in A$ and $x\in B$. So, we have $(x,x)\in A\times B$ and $(x,x)\in B\times A$. This means $(x,x)\in (A\times B)\cap (B\times A)$. Thus, $(A\times B)\cap (B\times A)\neq \varnothing$.

"$\Leftarrow$" direction:

We use proof by contrapositive. Assume $(A\times B)\cap (B\times A)\neq \varnothing$. Then, there exists $(x,y)$ such that $(x,y)\in A\times B$ and $(x,y)\in B\times A$. It follows that $x\in A$ and $x\in B$, meaning that $x\in A\cap B$, and hence $A\cap B\neq \varnothing$.

$\Box$

Example. Prove that for every nonnegative real number $a$, if $a<x$ for every positive real number $x$, then $a=0$.

Proof. We use proof by contrapositive, i.e., we will prove that "if $a\neq 0$, then $a\geq x$ for some positive real number $x$."

Assume $a\neq 0$. This means $a>0$ since $a$ is nonnegative. Then, we pick $x=a$ which is a positive real number, and we have $a\geq x$.

$\Box$

Exercise. Prove that for every $x,y\in \mathbb {R}$, if $xy\leq 9$, then $x\leq 3$ or $y\leq 3$.

Proof

Proof. We use proof by contrapositive. Assume $x>3$ and $y>3$. Then, we have $xy>9$ (by the property of "$>$").

$\Box$

Exercise. An integer $n$ is defined to be a perfect square if $n=k^{2}$ for some $k\in \mathbb {Z}$. Prove that for every $a,b\in \mathbb {Z}$, if $a^{2}+b^{2}$ is a perfect square, then $a$ is even or $b$ is even. (Hint: consider a previous result about congruence of integers, that is related to perfect square.)

Proof

We use proof by contrapositive. Assume $a$ is odd and $b$ is odd. Then, $a=2k_{1}+1$ and $b=2k_{2}+1$ for some $k_{1},k_{2}\in \mathbb {Z}$. Hence, $$a^{2}+b^{2}=4k_{1}^{2}+4k_{1}+1+4k_{2}^{2}+4k_{2}+1=4(k_{1}^{2}+k_{2}^{2}+k_{1}+k_{2})+2.$$ This means $a^{2}+b^{2}\equiv 2{\pmod {4}}$ since $k_{1}^{2}+k_{2}^{2}+k_{1}+k_{2}\in \mathbb {Z}$. However, no perfect square is congruent to 2 modulo 4 (recall that we have proved that for every integer $m$, $m^{2}\equiv 0{\text{ or }}1{\pmod {4}}$). Thus, $a^{2}+b^{2}$ is not a perfect square.

Proof by cases

In the previous sections, we have actually employed the method of proof by cases already. It is natural to use this method when we need to break down a problem into several cases, and then tackle every case individually ("divide and conquer"). Sometimes, we may even need to further divide a case into several subcases. The following are some typical cases:

1. an integer is even or odd;
2. a real number is less than 0, equal to 0, or greater than 0;
3. for two nonzero real numbers $x$ and $y$, either $xy>0$ or $xy<0$.

• For every of the cases, it can be divided into two subcases:

1. $xy>0$: ($x>0$ and $y>0$) or ($x<0$ and $y<0$)
2. $xy<0$: ($x>0$ and $y<0$) or ($x<0$ and $y>0$)

But, we should be aware that when we use proof by cases to prove that "$\forall x\in S,\dotsc$", the cases should cover all possibilities, i.e., all $x\in S$.

Example. Prove that for every $n\in \mathbb {Z}$, $n^{2}+3n+4$ is even.

Proof. We divide the proof into two cases: $n$ is even and $n$ is odd.

Case 1: $n$ is even.

Then, $n=2k$ for some $k\in \mathbb {Z}$. Thus, $$n^{2}+3n+4=4k^{2}+6k+4=2(2k^{2}+3k+2).$$ Since $2k^{2}+3k+2\in \mathbb {Z}$, $n^{2}+3n+4$ is even.

Case 2: $n$ is odd. Then, $n=2k'+1$ for some $k'\in \mathbb {Z}$. Thus, $$n^{2}+3n+4=4k'^{2}+4k'+1+6k'+3+4=2(2k'^{2}+5k'+4).$$ Since $2k'^{2}+5k'+4\in \mathbb {Z}$, $n^{2}+3n+4$ is even.

It follows that $n^{2}+3n+4$ is even for every $n\in \mathbb {Z}$.

$\Box$

Example. (Comparing parity) Prove that for every $m,n\in \mathbb {Z}$, $m$ and $n$ are of the same parity (i.e., both even or both odd) if and only if $m+n$ is even.

Proof. "$\Rightarrow$" direction: Assume $m$ and $n$ are of the same parity.

Case 1: $m$ and $n$ are both even.

Then, $m=2k_{1}$ and $n=2k_{2}$ for some $k_{1},k_{2}\in \mathbb {Z}$. Thus, $m+n=2(k_{1}+k_{2})$, and hence $m+n$ is even since $k_{1}+k_{2}\in \mathbb {Z}$.

Case 2: $m$ and $n$ are both odd.

Then, $m=2k_{3}+1$ and $n=2k_{4}+1$ for some $k_{3},k_{4}\in \mathbb {Z}$. Thus, $m+n=2(k_{3}+k_{4}+1)$, and hence $m+n$ is even since $k_{3}+k_{4}+1\in \mathbb {Z}$.

"$\Leftarrow$" direction: We use proof by contrapositive. Assume $m$ and $n$ are of different parity.

Case 1: $m$ is odd and $n$ is even.

Then, $m=2k_{5}+1$ and $n=2k_{6}$ for some $k_{5},k_{6}\in \mathbb {Z}$. Thus, $m+n=2k_{5}+1+2k_{6}=2(k_{5}+k_{6})+1$. Hence, $m+n$ is odd since $k_{5}+k_{6}\in \mathbb {Z}$.

Case 2: $m$ is even and $n$ is odd.

The proof is similar to case 1 (just exchange the role of $m$ and $n$).

$\Box$

Remark.

• We sometimes use the phrase without loss of generality (WLOG) to indicate that the proofs of the two situations are similar, and thus the proof of only one of these situations is needed. For instance, for the "$\Leftarrow$" direction in the above proof, we may write "Assume $m$ and $n$ are of different parity. WLOG, assume $m$ is odd and $n$ is even. ...".

Exercise. Let $a$ and $b$ be integers. Prove that $ab$ is even if and only if $a$ is even or $b$ is even.

Proof

Proof. "$\Rightarrow$" direction: We use proof by contrapositive. Assume $a$ is odd and $b$ is odd. Then, $a=2k_{1}+1$ and $b=2k_{2}+1$ for some $k_{1},k_{2}\in \mathbb {Z}$. Hence, $$ab=4k_{1}k_{2}+2k_{1}+2k_{1}+1=2(2k_{1}k_{2}+k_{1}+k_{2})+1,$$ and so $ab$ is odd since $2k_{1}k_{2}+k_{1}+k_{2}\in \mathbb {Z}$.

"$\Leftarrow$" direction: Assume $a$ is even or $b$ is even. WLOG, assume $a$ is even. Then, $a=2k$ for some $k\in \mathbb {Z}$. Thus, $ab=2kb=2(kb)$. Since $kb\in \mathbb {Z}$, $ab$ is even.

$\Box$

The following inequality is quite important in mathematics.

Theorem. (Triangle inequality) For every $x,y\in \mathbb {R}$, $|x+y|\leq |x|+|y|$.

Proof.

Case 1: $x\geq 0$ and $y\geq 0$.

Then, $x+y\geq 0$, and so $$|x+y|=x+y=|x|+|y|.$$

Case 2: $x<0$ and $y<0$.

Then, $x+y<0$, and so $$|x+y|=(-x)+(-y)=|x|+|y|.$$

Case 3: one of $x$ and $y$ is nonnegative, and the other is negative.

WLOG, assume $x\geq 0$ and $y<0$.

Subcase 1: $x+y\geq 0$.

Then, $${\begin{aligned}|x+y|&=x+y\\&<x+(-y)&(y<0<-y)\\&=|x|+|y|.\end{aligned}}$$

Subcase 2: $x+y<0$.

Then, $${\begin{aligned}|x+y|&=-(x+y)\\&=(-x)+(-y)\\&\leq x+(-y)&(-x\leq 0\leq x)\\&=|x|+|y|.\end{aligned}}$$

So, we have the desired inequality for every $x,y\in \mathbb {R}$.

$\Box$

Proof by contradiction

Another important method of proof is proof by contradiction.

Let $P$ be a statement. Now, suppose we want to prove that $P$ is true. If we can show that the conditional $\sim S\to \mathbf {F}$ is true (i.e., $\sim S\implies \mathbf {F}$), then the truth table for conditional tells us that $\sim S$ must be false, and hence $S$ must be true, as desired.

The truth table: $${\begin{array}{c|c|c|c}S&\sim S&\mathbf {F} &\sim S\to \mathbf {F} \\\hline T&F&F&T\\F&T&F&F\\\end{array}}$$ In words, the method of proof by contradiction is as follows: we first assume that the statement we want to prove to be true is false, and then proceed to show that this gives a contradiction, and therefore our assumption must be wrong. That is, it is impossible for the statement to be false since it leads to something "absurd". Hence, the statement is true.

The name of proof by contradiction comes from the fact that the assumption that the statement is false is later contradicted by some other fact. This is also known as reductio ad absurdum, which means reduction to absurdity.

In general, we often use the method of proof by contradiction when the statement we want to prove is negative sounding, e.g. "There is no ....", "There does not exist ...", etc.

Also, to indicate to the reader that we are using proof by contradiction, it is recommended that we write "assume to the contrary that ..." (or something similar) instead of just "assume ..." for the assumption that the statement is false.

Example. Prove that no odd number can be written as a sum of two odd numbers.

Proof. Assume to the contrary that the statement "no odd number can be written as a sum of two odd numbers" is false. That is, assume to the contrary that there is an odd number $n$ that can be written as a sum of two odd numbers $x$ and $y$. Then, we have $x=2k+1$ and $y=2k'+1$ for some $k,k'\in \mathbb {Z}$. Hence, we have $$n=x+y=2(k+k'+1),$$ which means $n$ is even since $k+k'+1\in \mathbb {Z}$. But this contradicts to our assumption that $n$ is odd. So, the result follows.

$\Box$

Example. Prove that there is no smallest positive real number.

Proof. Assume to the contrary that there is a smallest positive real number $x$. Now, consider the number $x/2$. Since $x>0$, it follows that $x/2>0$. Also, we have $x/2<x$. Hence, $x/2$ is a positive real number that is less than $x$, contradicting to our assumption that $x$ is the smallest positive real number.

$\Box$

Exercise.

Which of the following statement is/are true?

	There is no smallest positive rational number.
	There is no smallest positive integer.
	There is no smallest nonnegative integer.

Prove that there is no greatest positive real number.

Proof

Proof. Assume to the contrary that there is a largest positive real number $x$. Now, consider the number $2x$. Since $x>0$, it follows that $2x>0$. Also, we have $2x>x$. Hence $2x$ is a positive real number that is greater than $x$, contradicting to our assumption that $x$ is the greatest positive real number.

$\Box$

Example. Prove that the sum of an arbitrary rational number and an arbitrary irrational number is irrational.

Although this statement appears to be not so negative sounding, "irrational" just means "not rational". In this sense, we can see that this statement is also quite negative sounding. Also, it is not easy to show that a number is irrational directly (while, on the other hand, showing that a number is rational is quite easy: just express it as a quotient of an integer by a nonzero integer).

Proof. Assume to the contrary that the sum of an arbitrary rational number $x$ and an arbitrary irrational number $y$ is a rational number $z$. So, we have $x+y=z$ where $x={\frac {p_{1}}{q_{1}}}$ and $z={\frac {p_{2}}{q_{2}}}$ where $p_{1},p_{2},q_{1},q_{2}\in \mathbb {Z}$ with $q_{1}\neq 0$ and $q_{2}\neq 0$. But we can then rewrite the equation as $$y=z-x={\frac {p_{2}}{q_{2}}}-{\frac {p_{1}}{q_{1}}}={\frac {p_{2}q_{1}-p_{1}q_{2}}{q_{1}q_{2}}}.$$ Since $p_{2}q_{1}-p_{1}q_{2},q_{1}q_{2}\in \mathbb {Z}$ and $q_{1}q_{2}\neq 0$, this means $y$ is rational, contradicting to our assumption that $y$ is irrational.

$\Box$

The following is a typical example in introducing proof by contradiction:

Example. Prove that the number ${\sqrt {2}}$ is irrational.

Proof. Assume to the contrary that ${\sqrt {2}}$ is rational. Then, ${\sqrt {2}}={\frac {p}{q}}$ for some $p,q\in \mathbb {Z}$ with $q\neq 0$. By dividing $p$ and $q$ by some common factor that is at least 2, if necessary, we can further assume that $p$ and $q$ have no common factor greater than or equal to 2, i.e., $p/q$ has been expressed in (or reduced to) the lowest terms.

Taking square for the both sides of the equation ${\sqrt {2}}={\frac {p}{q}}$, we get $2={\frac {p^{2}}{q^{2}}}\implies p^{2}=2q^{2}$. Since $q^{2}\in \mathbb {Z}$, this means $p^{2}$ is even. By a previous result, this implies that $p$ is even. Hence, we have $p=2k$ for some $k\in \mathbb {Z}$.

Now substituting it into the equation $p^{2}=2q^{2}$, we get $4k^{2}=2q^{2}\implies q^{2}=2k^{2}$, which means $q^{2}$ is also even since $k^{2}\in \mathbb {Z}$. By a previous result again, this implies that $q$ is even.

Since both $p$ and $q$ are even, they have 2 as a common factor, contradicting to our assumption that $p/q$ has been expressed in (or reduced to) the lowest terms.

$\Box$

The following example is another typical example for demonstrating proof by contradiction. But before discussing it, we need to introduce the following theorem since it is used in the proof.

Theorem. (Fundamental theorem of arithmetic) Every integer $n\geq 2$ can be expressed as a product of one or more (not necessarily distinct) primes uniquely. That is, $n=p_{1}p_{2}\dotsc p_{r}$ for some prime numbers $p_{1},p_{2},\dotsc ,p_{k}$, uniquely.

Proof. We will prove this theorem after introducing proof by mathematical induction.

$\Box$

Remark.

• Notice that the "uniqueness" in the theorem is in the sense of the combination of prime number(s) used is unique. Simply changing the order of the multiplication is not counted as another expression.
• This theorem is also called unique prime factorization.

Example. (Euclid's theorem) Prove that there are infinitely many prime numbers.

Proof. Assume to the contrary that there are finitely many prime numbers, say $n$ prime numbers. We first list them in ascending order: $p_{1}<p_{2}<\dotsb <p_{n}$. Now, consider the number $$q=p_{1}p_{2}\dotsb p_{n}+1.$$ Since the smallest prime number is 2, we have $p_{1}p_{2}\dotsb p_{n}\geq 1$ , and hence $q\geq 2$. Applying the fundamental theorem of arithmetic, there is a unique prime factorization for $q$, and thus there is a prime number dividing $q$.

Since $p_{1},\dotsc ,p_{n}$ are all the primes by our assumption, it follows that one of them, say $p_{i}$, divides $q$, i.e., $q=kp_{i}$ for some $k\in \mathbb {Z}$. In addition, we know that $p_{i}$ divides $p_{1}p_{2}\dotsb p_{n}$, i.e., $p_{1}p_{2}\dotsb p_{n}=k'p_{i}$ for some $k'\in \mathbb {Z}$.

Therefore, we have $1=q-p_{1}p_{2}\dotsb p_{n}=(k-k')p_{i}$. This means $p_{i}$ divides 1, which is impossible (notice that 2 is the smallest prime, and only 1 divides itself). So, we are arriving at a contradiction.

$\Box$

Remark.

• This proof is first suggested by Euclid.

We can also use proof by contradiction to prove that a statement "$\forall x\in S,P(x)\to Q(x)$" is true. We first assume that the negation of the statement, i.e., "$\exists x\in S,P(x)\land (\sim Q(x))$" is true, and proceed to arrive at a contradiction. (Recall that $P\to Q\iff (\sim P)\lor Q$. So, $\sim (P\to Q)\iff P\land (\sim Q)$.) Thus, to prove that $\forall x\in S,P(x)\implies Q(x)$ by contradiction, we assume that there exists $x\in S$ such that $P(x)$ is true and $Q(x)$ is false, and then deduce a contradiction.

Example. Prove by contradiction that for every $n\in \mathbb {Z}$, if $n$ is odd, then $3n+1$ is even.

Proof. Assume to the contrary that there exists $n\in \mathbb {Z}$ such that $n$ is odd and $3n+1$ is odd. Since $n$ is odd, we have $n=2k+1$ for some $k\in \mathbb {Z}$. Then, $$3n+1=3(2k+1)+1=6k+4=2(3k+2).$$ This means $3n+1$ is even since $3k+2\in \mathbb {Z}$, contradicting to our assumption that $3n+1$ is odd.

$\Box$

Exercise. Prove by contradiction that for every nonnegative real number $a$, if $a<x$ for every positive real number $x$, then $a=0$.

Proof

Proof. Assume to the contrary that $a<x$ for every positive real number $x$ and $a\neq 0$. Since $a$ is nonnegative, this means $a>0$. Now, consider the number $x=a>0$. By assumption, we have $a<x=a$, which implies that $1<1$, arriving at a contradiction.

$\Box$

Example. Prove that $x=\log _{10}3$ is irrational.

Proof. Assume to the contrary that $x$ is rational, i.e., $x={\frac {p}{q}}$ for some $p,q\in \mathbb {Z} \setminus \{0\}$ ($x\neq 0$). Notice that $x>0$. So, we only have the following cases:

Case 1: $p,q\in \mathbb {N}$.

Now, we have $${\begin{aligned}&&10^{x}&=1\\&\Rightarrow &10^{p/q}&=3\\&\Rightarrow &10^{p}&=3^{q}.\end{aligned}}$$ But $10^{p}$ is even, while $3^{q}$ is odd (product of even (odd) numbers is even (odd)).

Case 2: $p$ and $q$ are both negative integers.

Then, we write $x={\frac {-p}{-q}}$. Now, we have $${\begin{aligned}&&10^{x}&=3\\&\Rightarrow &10^{-p/-q}&=3\\&\Rightarrow &10^{-p}&=3^{-q}.\\\end{aligned}}$$ But $10^{-p}$ is even, while $3^{-q}$ is odd ($-p$ and $-q$ are positive integers).

So, in either case, we arrive at a contradiction.

$\Box$

Exercise. A student provides the following proof to the claim "$x=\log _{10}1$ is irrational.":

Proof. Assume to the contrary that $x$ is rational, i.e., $x={\frac {p}{q}}$ for some $p,q\in \mathbb {Z} \setminus \{0\}$ ($x\neq 0$). Notice that $x>0$. So, we only have the following cases:

Case 1: $p,q\in \mathbb {N}$.

Now, we have $${\begin{aligned}&&10^{x}&=1\\&\Rightarrow &10^{p/q}&=1\\&\Rightarrow &10^{p}&=1.\end{aligned}}$$ But $10^{p}$ is even, while $1$ is odd.

Case 2: $p$ and $q$ are both negative integers.

Then, we write $x={\frac {-p}{-q}}$. Now, we have $${\begin{aligned}&&10^{x}&=1\\&\Rightarrow &10^{-p/-q}&=1\\&\Rightarrow &10^{-p}&=1.\\\end{aligned}}$$ But $10^{-p}$ is even, while $1$ is odd.

So, in either case, we arrive at a contradiction.

$\Box$

Is the proof correct? If not, point out the mistake.

Solution

The proof is incorrect. Indeed, $\log _{10}1=0$ is rational. The mistake is that the student states that $x\neq 0$ and also $x>0$ in the proof, which are not true.

Exercise. Prove that for every $x,y\in \mathbb {R}$, if $x+y$ is rational, then both $x$ and $y$ are rational, or both $x$ and $y$ are irrational.

Proof

Proof. Assume to the contrary that there exists $x,y\in \mathbb {R}$ such that $x+y\in \mathbb {Q}$ and exactly one of $x$ and $y$ is rational, and the other irrational. WLOG, assume $x\in \mathbb {Q}$ and $y\in \mathbb {I}$. Then, since $y=(x+y)-x$, and $x+y\in \mathbb {Q}$ and $x\in \mathbb {Q}$, we have $y\in \mathbb {Q}$, contradicting to our assumption that $y\in \mathbb {I}$.

$\Box$

Example. (Sum and product of a rational and an irrational number) Prove that for every $x,y\in \mathbb {R}$, (a) if $x\in \mathbb {Q}$ and $y\in \mathbb {I}$, then $x+y\in \mathbb {I}$;

(b) if $x\in \mathbb {Q} \setminus \{0\}$ and $y\in \mathbb {I}$, then $xy\in \mathbb {I}$.

Solution.

(a)

Proof. Assume to the contrary that there exist $x,y\in \mathbb {R}$ such that $x\in \mathbb {Q}$ and $y\in \mathbb {I}$ and $x+y\in \mathbb {Q}$. Then, $y=(x+y)-x\in \mathbb {Q}$, contradicting to our assumption that $y\in \mathbb {I}$.

$\Box$

(b)

Proof. Assume to the contrary that there exist $x\in \mathbb {Q} \setminus \{0\}$ and $y\in \mathbb {I}$ and $xy\in \mathbb {Q}$. Then, $y={\frac {xy}{x}}\in \mathbb {Q}$ ($x\neq 0$), contradicting to our assumption that $y\in \mathbb {I}$.

$\Box$

Sometimes we can prove a statement using multiple methods:

Example. Prove that for every positive real number $x$ and $y$, if $x\leq y$, then $x^{2}\leq y^{2}$.

We can prove it using (i) direct proof; (ii) proof by contrapositive; (iii) proof by contradiction.

(i)

Proof. Assume $x\leq y$. Then multiplying both sides by $x$ gives $x^{2}\leq xy$. Also, multiplying both sides by $y$ gives $xy\leq y^{2}$. Combining these two inequalities, we get $x^{2}\leq y^{2}$.

$\Box$

(ii)

Proof. Assume $x^{2}>y^{2}$. Rearranging the inequality gives $x^{2}-y^{2}>0\implies (x-y)(x+y)>0$. Now dividing both sides by the positive number $x+y$ preserves the direction of inequality, and thus gives $x-y>0\implies x>y$.

$\Box$

(iii)

Proof. Assume to the contrary that $x\leq y$ and $x^{2}>y^{2}$. Then, we have $x\leq y\implies x-y\leq 0$. Also, since $x$ and $y$ are positive, $x+y>0$. So we have $(x-y)(x+y)\leq 0\implies x^{2}-y^{2}\leq 0\implies x^{2}\leq y^{2}$, contradicting to our assumption that $x^{2}>y^{2}$.

$\Box$

Exercise. Let $x$ be a positive real number. Prove that if $x-{\frac {3}{x}}>2$, then $x>3$ by (i) direct proof; (ii) proof by contrapositive; (iii) proof by contradiction.

Solution

(i)

Proof. Assume $x-{\frac {3}{x}}>2$. Multiplying both side by $x$ gives $x^{2}-3>2x\implies x^{2}-2x-3>0\implies (x+1)(x-3)>0$. Then, dividing both sides by the positive number $x+1$ gives $x-3>0\implies x>3$.

$\Box$

(ii)

Proof. Assume $x\leq 3$. Then, $x-3\leq 0$. Also, $x+1>0$ ($x$ is positive). Thus, $(x-3)(x+1)\leq 0$. This implies $$x^{2}-2x-3\leq 0\implies x-{\frac {3}{x}}\leq 2.$$

$\Box$

(iii)

Proof. Assume to the contrary that $x-{\frac {3}{x}}>2$ and $x\leq 3$. Then, $x-3\leq 0$. Also, $x+1>0$. So, $(x-3)(x+1)\leq 0$, and hence $x-{\frac {3}{x}}\leq 2$. This contradicts to our assumption that $x-{\frac {3}{x}}>2$.

$\Box$

We can see that when proving a statement "$\forall x\in S,P(x)\implies Q(x)$", we may be able to use both proof by contrapositive and proof by contradiction. However, the two proofs are different, and we will compare them in the following table:

Proving that "$\forall x\in S,P(x)\implies Q(x)$."

	Proof by contrapositive	Proof by contradiction
Assumption	$\sim Q(x)$	$P(x)\land \sim Q(x)$
Goal	$\sim P(x)$	$\mathbf {F}$

From this table, we can see that the proof by contradiction is more advantageous in terms of assumption, since it has one more "help" from $P(x)$ (when we assume $P(x)\land \sim Q(x)$, we can use both $\sim Q(x)$ and $P(x)$.) However, in terms of goal, the proof by contrapositive is more advantageous since the goal is more clear ($\sim P(x)$), while for the proof by contradiction, it is not clear that what the form of the contradiction is. There can be many "ways" for arriving at a contradiction (compare the contradiction in the proof of "${\sqrt {2}}$ is irrational" vs. that of "there are infinitely many primes").

Existence proof

Consider the statement "$\exists x\in S,P(x)$". This statement is true if $P(x)$ is true for at least one $x\in S$. Otherwise, it is false. Thus, to prove such kind of statement, it suffices to find one element $x\in S$ such that $P(x)$ is true, and this is known as an existence proof. In particular, we should verify that the choice of element $x$ is actually belonging to $S$ and $P(x)$ is actually true for that choice.

Example. Prove that there exists positive integers $a,b,c$ such that $a^{2}+b^{2}=c^{2}$ (such integers $a,b,c$ are known as a Pythagorean triple).

Proof. Take $a=3$, $b=4$ and $c=5$ (which are integers). Then, $a^{2}+b^{2}=3^{2}+4^{2}=5^{2}=c^{2}$.

$\Box$

Remark.

• The choice of $a,b,c$ is not unique. For instance, one can also take $a=5,b=12$ and $c=13$. But, giving one example of $a,b$ and $c$ that satisfies the requirement is enough.

Example. Prove that there exists an integer $x$ such that $x^{3}=x$.

Proof. Take $x=1$. Then, we have $x^{3}=1^{3}=1=x$.

$\Box$

The following example demonstrates a more advanced version of existence proof: non-constructive proof.

Example. Prove that there exist irrational numbers $a$ and $b$ such that $a^{b}$ is rational.

Proof. We have proved that ${\sqrt {2}}$ is irrational. So, we can make use of this fact in this proof.

Consider the real number ${\sqrt {2}}^{\sqrt {2}}$. This number is either rational or irrational. Now we consider the following cases:

Case 1: ${\sqrt {2}}^{\sqrt {2}}$ is rational. Then, we can take $a=b={\sqrt {2}}\in \mathbb {I}$, and then $a^{b}$ is rational.

Case 2: ${\sqrt {2}}^{\sqrt {2}}$ is irrational. Then, we can take $a={\sqrt {2}}^{\sqrt {2}}\in \mathbb {I}$ and $b={\sqrt {2}}\in \mathbb {I}$. Then, $a^{b}=\left({\sqrt {2}}^{\sqrt {2}}\right)^{\sqrt {2}}=({\sqrt {2}})^{{\sqrt {2}}\cdot {\sqrt {2}}}=({\sqrt {2}})^{2}=2,$ which is rational.

Thus, in either case, we can find two irrational numbers $a$ and $b$ such that $a^{b}$ is rational.

$\Box$

Remark.

• This type of proof is known as non-constructive proof since it does not actually construct an example $a$ and $b$, and so we do not know which two irrational numbers $a$ and $b$ satisfy this requirement. However, this proof does prove the existence of such $a$ and $b$.

Exercise.

(a) Prove that there exist distinct irrational numbers $a$ and $b$ such that $a^{b}$ is rational. (You may use the fact that ${\sqrt {3}}$ is irrational.)

(b) Prove that there exist a rational number $a$ and an irrational number $b$ such that $a^{b}$ is rational.

(c) Prove that there exist a rational number $a$ and an irrational number $b$ such that $a^{b}$ is irrational. (You may use the fact that ${\frac {1}{2{\sqrt {2}}}}$ is irrational.)

(d) Prove that there exist rational numbers $a$ and $b$ such that $a^{b}$ is irrational.

Solution

(a)

Proof. Consider the real number ${\sqrt {3}}^{\sqrt {2}}$. It is either rational or irrational. Now, we consider the following cases:

Case 1: ${\sqrt {3}}^{\sqrt {2}}$ is rational. Then, we can take $a={\sqrt {3}}\in \mathbb {I}$ and $b={\sqrt {2}}\in \mathbb {I}$, and $a^{b}$ is rational.

Case 2: ${\sqrt {3}}^{\sqrt {2}}$ is irrational. Then, we can take $a={\sqrt {3}}^{\sqrt {2}}\in \mathbb {I}$ and $b={\sqrt {2}}\in \mathbb {I}$. Then, $a^{b}=\left({\sqrt {3}}^{\sqrt {2}}\right)^{\sqrt {2}}=({\sqrt {3}})^{2}=3$, which is rational.

$\Box$

(b)

Proof. Take $a=10$ and $b=\log _{10}3$. Recall that we have proved that $b=\log _{10}3$ is irrational. Then, we have $a^{b}=10^{\log _{10}3}=3$, which is rational.

$\Box$

(c)

Proof. Consider the real number $2^{1/(2{\sqrt {2}})}$. Now, consider the following cases:

Case 1: $2^{1/(2{\sqrt {2}})}$ is irrational. Then, take $a=2$ and $b={\frac {1}{2{\sqrt {2}}}}\in \mathbb {I}$, and $a^{b}$ is irrational.

Case 2: $2^{1/(2{\sqrt {2}})}$ is rational. Then, take $a=2^{1/(2{\sqrt {2}})}\in \mathbb {Q}$ and $b={\sqrt {2}}\in \mathbb {I}$. Then, $a^{b}=\left(2^{1/(2{\sqrt {2}})}\right)^{\sqrt {2}}=2^{1/2}={\sqrt {2}}$, which is irrational.

$\Box$

(d)

Proof. Take $a=2$ and $b=1/2$. Then, $a^{b}=2^{1/2}={\sqrt {2}}$, which is irrational.

$\Box$

Disproof

Consider the statement "$\forall x\in S,P(x)$.". Suppose we somehow believe that the statement is false. Then, we want to prove that it is false, i.e., prove that "$\exists x\in S$ such that $P(x)$ is false." An element $x_{0}\in S$ for which $P(x_{0})$ is false is known as a counterexample of the statement, and a process of showing that the statement is false (in other words, disproving the statement) is called a disproof of the statement. One counterexample is enough to disprove the statement.

Example. Disprove that $x^{3}\geq 0$ for every $x\in \mathbb {R}$.

Disproof. Take $x=-1$. Then, $(-1)^{3}=-1<0$.

$\Box$

Example. Disprove that the product of two arbitrary irrational numbers is irrational.

Disproof. To disprove this, we need to find $x,y\in \mathbb {I}$ such that $xy\in \mathbb {Q}$.

Take $x=y={\sqrt {2}}$. Then, $xy=2\in \mathbb {Q}$.

$\Box$

To disprove the statement "$\forall x\in S,P(x)\to Q(x)$, we show that there exists an element $x_{0}\in S$ such that $P(x_{0})\to Q(x_{0})$ is false, i.e., $P(x_{0})$ is true and $Q(x_{0})$ is false.

Example. Disprove that for every $x\in \mathbb {Z}$, if $x^{2}\equiv 1{\pmod {4}}$, then $x\equiv 1{\pmod {4}}$.

Disproof. Take $x=3$. Then $x^{2}=9\equiv 1{\pmod {4}}$ but $3\not \equiv 1{\pmod {4}}$.

$\Box$

To disprove the statement "$\exists x\in S,P(x)$", we need to show that there is no such $x$. That is, we need to show that "$\forall x\in S,\sim P(x)$" (the negation of statement) is true. In this case, we are not just constructing counterexamples. We have to prove that ${\color {darkgreen}\forall }x\in S,\sim P(x)$, instead of $\exists x\in S,\sim P(x)$.

Example. Disprove that there exists $n\in \mathbb {Z}$ such that $n^{2}+3n+4$ is even.

Disproof. To disprove this, we need to prove that for every $n\in \mathbb {Z}$, $n^{2}+3n+4$ is even. But this has been proved previously (in the section about proof by cases).

$\Box$

Often, before proving or disproving statements, the truth of falseness of them are not known, and we need to decide whether every of them is true or false. After that, we will prove it if it is true and disprove it otherwise. Of course, our decision is not perfectly accurate, and sometimes we make mistake, which leads us to do the opposite thing, i.e., proving a wrong statement or disproving a correct statement. Clearly, when we do such thing, we cannot succeed. However, the process of performing such wrong thing may give us some insights about what the correct direction is, and how to prove/disprove the statement.

To decide whether a statement is true or false, you may follow some tips below:

• Follow your mathematical intuition. As you have learnt more about mathematics, you may have intuition and idea about whether a statement is true or false, before proving/disproving it.
• Construct some simple examples. Such examples constructed may be a counterexample (for disproving "$\forall \dotsb$")/example (for proving "$\exists \dotsb$") if you are lucky. Even if they are not counterexamples/examples, you may observe some kind of patterns from it, which may give you some insights about how to prove/disprove the statement.

Example. Prove or disprove every of the following statements:

(a) There exists a real number $x$ satisfying the equation $x^{6}+9x^{2}+3=0$.

(b) Let $A,B$ and $C$ be sets. If $A\times C=B\times C$, then $A=B$.

(c) For every real number $x$, ${\frac {x^{2}+x}{x^{2}-x}}={\frac {x+1}{x-1}}$.

(d) There exists a real number $x$ such that $x^{3}<x<x^{2}$.

Solution.

(a)

Disproof. Since $x$ is a real number, we have $x^{6}\geq 0$ and $x^{2}\geq 0$. Hence, $x^{6}+9x^{2}+3\geq 3$, and thus $x^{6}+9x^{2}+3\neq 0$ for every $x\in \mathbb {R}$.

$\Box$

(b)

Disproof. Take $A=\{1\}$, $B=\{2\}$ and $C=\varnothing$. Then, $A\times C=B\times C=\varnothing$, but $A\neq B$ .

$\Box$

(c)

Disproof. Take $x=0$. Then the LHS is undefined (the denominator is zero), but the RHS is -1.

$\Box$

(d)

Proof. Take $x=-2$. Then, $x^{3}=-8$ and $x^{2}=4$, and we have $x^{3}<x<x^{2}$.

$\Box$

Exercise. Prove or disprove every of the following statements:

(a) There exists a real number $x$ such that ${\sqrt {2}}-x$ and ${\sqrt {2}}+x$ are both rational.

(b) There exists $m,n\in \mathbb {Q}$ with $m\neq n$ such that ${\frac {1}{m}}+{\frac {1}{n}}=3$.

(c) There exist even numbers $x$ and $y$ such that $3x^{2}+y^{2}\equiv 0{\pmod {8}}$.

(d) For every $a,b,c,d\in \mathbb {R}$, if $a<b$ and $c<d$, then $ac<bd$.

(e) For every $a,b\in \mathbb {Q}$ with $a<b$, there exists $x\in \mathbb {Q}$ such that $a<x<b$.

Solution

(a)

Disproof. We want to prove the statement is false. We use proof by contradiction.

Assume to the contrary that the statement is true, i.e., there exists a real number $x$ such that ${\sqrt {2}}-x$ and ${\sqrt {2}}+x$ are both rational. Then, we have $({\sqrt {2}}-x)+({\sqrt {2}}+x)=2{\sqrt {2}}$ is rational, which contradicts to the fact that $2{\sqrt {2}}$ (product of a rational number and an irrational number) is irrational.

$\Box$

(b)

Proof. Take $m=1$ and $n=1/2$. Then, ${\frac {1}{m}}+{\frac {1}{n}}=1+2=3$.

$\Box$

(c)

Proof. Take $x=y=2$. Then, $3x^{2}+y^{2}=3(2)^{2}+2^{2}=12+4=16\equiv 0{\pmod {8}}$.

$\Box$

(d)

Disproof. Take $a=c=-2$ and $b=d=1$. Then, $a<b$ and $c<d$, but $ac=4>1=bd$.

$\Box$

(e)

Proof. For every $a,b\in \mathbb {Q}$, choose $x={\frac {m+n}{2}}\in \mathbb {Q}$ (sum/product of two rational numbers is rational). Since $m<n$, we have $m={\frac {m}{2}}+{\frac {m}{2}}<{\frac {m+n}{2}}<{\frac {n}{2}}+{\frac {n}{2}}=n$, as desired.

$\Box$

Proof by mathematical induction

The last proof method discussed in this chapter is proof by mathematical induction. This method is used to prove a statement in the form of "For every integer $n$ greater than or equal to an integer $m$, $P(n)$ is true.". That is, it is used to prove that a sequence of statements $P(m),P(m+1),P(m+2),\dotsc$ is true. Of course, we can prove that every of these statements is true one by one, but the principle of mathematical induction gives an alternative and more convenient method.

To prove the principle of mathematical induction, we need the well-ordering principle. Before introducing it, we need the definition of well-ordered.

Definition. (Well-ordered set) A nonempty set $S$ of real numbers is well-ordered if every nonempty subset of $S$ has a least element.

Example.

• The set $\{-3,1,2\}$ is well-ordered since its nonempty subsets are $\{-3\},\{1\},\{2\},\{-3,1\},\{-3,2\},\{1,2\},\{-3,1,2\}$, and every of these subsets has a least element.
• The sets $\mathbb {Z} ,\mathbb {Q} ,\mathbb {R}$ are not well-ordered since none of these sets themselves have a least element (it can be proved that there is no smallest integer/rational number/real number).

Now, one may ask that whether the set $\mathbb {N}$ is well-ordered. It may appear that it is well-ordered. Here, we will just regard this as an axiom:

Axiom. (Well-ordering principle) The set $\mathbb {N}$ is well-ordered.

The well-ordering principle can then be used to prove (a less general version of) the principle of mathematical induction.

Theorem. (The principle of mathematical induction)

The principle of mathematical induction can be illustrated by the sequential effect of falling dominoes. "$P(m)$ is true" means the first domino can be pushed down, and "for every integer $k\geq m$, $P(k)\implies P(k+1)$" means for every domino, if it falls down, then it will push the next domino down also. With these two requirements satisfied, every domino will fall down eventually (every statement involved is true).

For every $m\in \mathbb {Z}$, if $P(m),P(m+1),P(m+2),\dotsc$ are statements satisfying

(i) $P(m)$ is true; and

(ii) for every integer $k\geq m$, $P(k)\implies P(k+1)$,

then the statements $P(m),P(m+1),P(m+2),\dotsc$ are true.

This theorem is quite intuitive: with the conditions satisfied, we have an "infinite chain of implications":

• $P(m)$ is true (by (i)).
• Thus, $P(m+1)$ is true (by (ii)).
• Thus, $P(m+2)$ is true (by (ii)).
• Thus, $P(m+3)$ is true (by (ii)) ...

But strictly speaking, this is not counted as a proof. We will give a formal (partial) proof to this theorem below:

Proof. Here we only prove the case where $m\in \mathbb {N}$.

Assume to the contrary that the theorem is false. Then, the conditions (i) and (ii) are satisfied by the statements, but there exist some positive integers $n$ for which $P(n)$ is false. Now, let the set $$S=\{n\in \mathbb {N} :P(n){\text{ is false}}\}.$$ Since $S$ is a nonempty subset of $\mathbb {N}$, by the well-ordering principle, $S$ contains a least element. Let us assume $s$ to be the least element.

Since $P(m)$ is true by the condition (i), $m\notin S$. This means the least element $s$ cannot be $m$. Hence, $s\geq m+1$, which means $s-1\geq m$.

Since $s$ is the least element of $S$, we have $s-1\notin S$, i.e., $P(s-1)$ is a true statement. Then, by the condition (ii), $P(s)$ is true (we have $s-1\geq m$). It follows that $s\notin S$. But this contradicts to our assumption that $s$ is the least element of $S$ (in particular, $s\in S$).

$\Box$

Remark.

• This proof can be extended to the case where $m\in \mathbb {Z}$. But the proof needs to use the result that the set $\{i\in \mathbb {Z} :i\geq m\}$ is well-ordered. Once we have proven this result, we can simply change the set $S$ in the proof to $\{i\in \mathbb {Z} :i\geq m{\text{ and }}P(i){\text{ is false}}\}$, and also modify some sentences in the proof slightly for the extension.
• Notice that in the inductive hypothesis, we assume $P(k)$ is true for an arbitrary integer $k$ with $k\geq m$, but not for every integer $k\geq m$. This is because if we assume the latter, then we are assuming what we want to prove, and so the proof is invalid. While for the former assumption, we just assume $P(k)$ is true for an arbitrary (but not every) integer $k$ with $k\geq m$, but this does not lose generality since $k$ is arbitrary.

Using the principle of mathematical induction, to prove that the statement $P(n)$ is true for every integer $n\geq m$, it suffices to prove two things:

(i) $P(m)$ is true.

(ii) For every integer $k\geq m$, $P(k)\implies P(k+1)$.

Thus, proof in this form is a two-step process. We often call the proof of (i) as the basis step or base case, and the proof of (ii) is called the inductive step. In particular, when we prove (ii), we usually use the method of direct proof, and first assume $P(k)$ is true for an arbitrary integer $k$ with $k\geq m$. Such assumption is often called the inductive (or induction) hypothesis.

Example. Prove that for every $n\in \mathbb {N}$, $$P(n):1+2+\dotsb +n={\frac {n(n+1)}{2}}$$ is true.

Proof. Here we use the principle of mathematical induction.

Basis Step: Since $1={\frac {1(1+1)}{2}}$, the statement $P(1)$ is true.

Inductive Hypothesis: Let $k$ be an arbitrary positive integer. Assume $P(k)$ is true. That is, assume $${\color {blue}1+2+\dotsb +k={\frac {k(k+1)}{2}}}$$ is true.

Inductive Step: Since $${\begin{aligned}{\color {blue}1+2+\dotsb +k}+(k+1)&={\color {blue}{\frac {k(k+1)}{2}}}+(k+1)&({\text{inductive hypothesis}})\\&={\frac {k^{2}+k+2k+2}{2}}\\&={\frac {(k+1)(k+2)}{2}},\end{aligned}}$$ it follows that $P(k+1)$ is true. Hence, by the principle of mathematical induction, $P(n)$ is true for every positive integer $n$.

$\Box$

Remark.

• One can also prove this statement using a trick:

First write the sum as $1+2+\dotsb +(n-1)+n$.

Now also write the same sum, but in reverse order: $n+(n-1)+\dotsb +2+1$.

After that, add the two sums together in the following way:

$${\begin{aligned}&&{\color {darkgreen}1}+{\color {blue}2}+\dotsb +{\color {darkgreen}(n-1)}+{\color {blue}n}\\&+)&{\color {darkgreen}n}+{\color {blue}(n-1)}+\dotsb +{\color {darkgreen}2}+{\color {blue}1}\\\hline &&\underbrace {{\color {darkgreen}(n+1)}+{\color {blue}(n+1)}+\dotsb +{\color {darkgreen}(n+1)}+{\color {blue}(n+1)}} _{n{\text{ times}}}\end{aligned}}$$

Now, we can see that two times the sum gives $n(n+1)$. Thus, the sum $1+2+\dotsb +(n-1)+n$ is ${\frac {n(n+1)}{2}}$.

Exercise. For every $n\in \mathbb {N}$, consider the sum $$1^{3}+2^{3}+\dotsb +n^{3}.$$ Guess a general formula for the sum and prove it. (Hint: you may compute the value of sum for some values of $n$, and see whether there are any patterns.)

Solution

When $n=1,2,3,4$, the sum is $1,9,36,100$ respectively. Notice that $1=1^{2},9=3^{2}=(1+2)^{2},36=6^{2}=(1+2+3)^{2}$ and $100=10^{2}=(1+2+3+4)^{2}$. Hence, it is natural to guess that the formula is, for every $n\in \mathbb {N}$, $$1^{3}+2^{3}+\dotsb +n^{3}=(1+2+\dotsb +n)^{2}.$$ But we have proved that $1+2+\dotsb +n={\frac {n(n+1)}{2}}$. So this formula can be alternatively expressed as $$1^{3}+2^{3}+\dotsb +n^{3}=\left({\frac {n(n+1)}{2}}\right)^{2}.$$

Proof. Let $P(n)$ be the open statement "$1^{3}+2^{3}+\dotsb +n^{3}=\left({\frac {n(n+1)}{2}}\right)^{2}$".

Basis Step: Since $1^{3}=\left({\frac {1(1+1)}{2}}\right)^{3}$, $P(1)$ is true.

Inductive Hypothesis: Assume $P(k)$ is true for an arbitrary positive integer $k$. That is, assume $$1^{3}+2^{3}+\dotsb +k^{3}=\left({\frac {k(k+1)}{2}}\right)^{2}.$$

Inductive Step: Since $${\begin{aligned}1^{3}+2^{3}+\dotsb +k^{3}+(k+1)^{3}&=\left({\frac {k(k+1)}{2}}\right)^{2}+(k+1)^{3}\\&={\frac {k^{2}(k+1)^{2}+{\color {darkgreen}4}(k+1)^{3}}{2^{2}}}\\&={\frac {(k+1)^{2}(k^{2}+{\color {darkgreen}4}(k+1))}{2^{2}}}\\&={\frac {(k+1)^{2}(k+2)^{2}}{2^{2}}}\\&=\left({\frac {(k+1)(k+2)}{2}}\right)^{2},\end{aligned}}$$ $P(k+1)$ is true. Hence, by the principle of mathematical induction, $P(n)$ is true for every positive integer $n$.

$\Box$

Remark.

• The following diagram illustrates this statement:

We can use the proof by mathematical induction for proving some inequalities also:

Example. Prove that for every integer $n\geq 5$, $2^{n}>n^{2}$.

Proof. Let $P(n)$ be the open statement "$2^{n}>n^{2}$".

Basis Step: Since $2^{5}=32>25=5^{2}$, $P(5)$ is true.

Inductive Hypothesis: Assume $P(k)$ is true for an arbitrary integer $k$ with $k\geq 5$. That is, assume $$2^{k}>k^{2}.$$ Inductive Step: Since $$2^{k+1}=2(2^{k})>2k^{2}\quad ({\text{inductive hypothesis}}),$$ it suffices to show that $2k^{2}>(k+1)^{2}$. Now, consider $2k^{2}-(k+1)^{2}$: $$2k^{2}-(k+1)^{2}=k^{2}-2k-1=(k-1)^{2}-2>0.\quad (k\geq 5)$$ Thus, $P(k+1)$ is true. Hence, by the principle of mathematical induction, $P(n)$ is true for every integer $n\geq 5$.

$\Box$

Exercise. Prove that for every integer $n\geq 4$, $n!>2^{n}$.

Proof

Let $P(n)$ be the open statement "$n!>2^{n}$".

Basis Step: Since $4!=24>16=2^{4}$, $P(4)$ is true.

Inductive Hypothesis: Assume $P(k)$ is true for an arbitrary integer $k\geq 4$. That is, assume $$k!>2^{k}.$$

Inductive Step: Since $$(k+1)!=(k+1)k!>{\color {darkgreen}(k+1)}2^{k}>{\color {darkgreen}2}\cdot 2^{k}=2^{k+1},$$ (we have $k+1>2$ since $k\geq 4$) $P(k+1)$ is true. Hence, by the principle of mathematical induction, $P(n)$ is true for every integer $n\geq 4$.

Example. (Sum of a geometric sequence) Prove that for every integer $n\geq 0$ and for every real number $r\neq 1$, we have $$1+r+r^{2}+\dotsb +r^{n}={\frac {1-r^{n+1}}{1-r}}.$$

Proof. Let $P(n)$ be the open statement "$1+r+r^{2}+\dotsb +r^{n}={\frac {1-r^{n+1}}{1-r}}$".

Basis Step: Since $1={\frac {1-r^{1}}{1-r}}$, $P(0)$ is true.

Inductive Hypothesis: Assume $P(k)$ is true for an arbitrary nonnegative integer $k$. That is, assume $$1+r+r^{2}+\dotsb +r^{k}={\frac {1-r^{k+1}}{1-r}}.$$

Inductive Step: Since $$1+r+r^{2}+r^{k}+r^{k+1}={\frac {1-r^{k+1}}{1-r}}+r^{k+1}={\frac {1-r^{k+1}+r^{k+1}-r^{k+2}}{1-r}}={\frac {1-r^{k+2}}{1-r}},$$ $P(k+1)$ is true. Hence, by the principle of mathematical induction, $P(n)$ is true for every $n\geq 0$.

$\Box$

Example. (Cardinality of power set) Prove that for every set $A$ and for every integer $n\geq 0$, if $A$ is finite with $|A|=n$, then $|{\mathcal {P}}(A)|=2^{n}$.

Proof. Let $A_{n}$ be a finite set with cardinality $n$ and $P(n)$ be the open statement $|{\mathcal {P}}(A_{n})|=2^{n}$.

Basis Step: Since $A_{0}=\varnothing$, and $|{\mathcal {P}}(\varnothing )|=|\{\varnothing \}|=1=2^{0}$, $P(0)$ is true.

Inductive Hypothesis: Assume $P(k)$ is true for an arbitrary nonnegative integer $k$. That is, assume $|{\mathcal {P}}(A_{k})|=2^{k}$. In other words, there are $2^{k}$ subsets of $A_{k}$.

Inductive Step: First, fix an element $a\in A_{k+1}$. Now let $B=A_{k+1}\setminus \{a\}$. Then, $B$ contains $k$ elements, and thus by inductive hypothesis, there are $2^{k}$ subsets of $B$.

Let $S$ be a subset of $B$. Since $B$ is a subset of $A_{k+1}$, it follows that $S$ is a subset of $A_{k+1}$. But, $a\notin S$ since $a\notin B$. So, $S\cup \{a\}$ is also a subset of $A_{k+1}$, that is distinct from $S$. Thus, every subset $S$ of $B$ gives rise to two subsets of $A_{k+1}$, namely $S$ and $S\cup \{a\}$. As a result, there are $2^{k}$ subsets of $A_{k+1}$ without the element $a$ and $2^{k}$ subsets with the element $a$.

So, we have $2^{k}+2^{k}=2^{k+1}$ subsets of $A_{k+1}$ altogether. Hence, $|{\mathcal {P}}(A_{k+1})|=2^{k+1}$, and thus $P(k+1)$ is true. Hence, by the principle of mathematical induction, $P(n)$ is true for every integer $n\geq 0$.

$\Box$

Exercise. (Generalization of De Morgan's law) Prove that for every subset $A_{1},A_{2},\dotsc ,A_{n}$ of a universal set $U$ and for every integer $n\geq 2$, $$(A_{1}\cap A_{2}\cap \dotsb \cap A_{n})^{c}=A_{1}^{c}\cup A_{2}^{c}\cup \dotsb \cup A_{n}^{c}.$$ (Hint: you may use the ordinary De Morgan's law, i.e., for every subset $B,C$ of a universal set $U$, $(B\cap C)^{c}=B^{c}\cup C^{c}$.)

Proof. Let $P(n)$ be the open statement "$(A_{1}\cap A_{2}\cap \dotsb \cap A_{n})^{c}=A_{1}^{c}\cup A_{2}^{c}\cup \dotsb \cup A_{n}^{c}$.".

Basis Step: By the ordinary De Morgan's law, $P(2)$ is true.

Inductive Hypothesis: Assume $P(k)$ is true for an arbitrary integer $k\geq 2$. That is, assume $$(A_{1}\cap A_{2}\cap \dotsb \cap A_{k})^{c}=A_{1}^{c}\cup A_{2}^{c}\cup \dotsb \cup A_{k}^{c}.$$ Inductive Step: Since $${\begin{aligned}({\color {blue}A_{1}\cap A_{2}\cap \dotsb \cap A_{k}}\cap A_{k+1})^{c}&=({\color {blue}A_{1}\cap A_{2}\cap \dotsb \cap A_{k}})^{c}\cup A_{k+1}^{c}&({\text{ordinary De Morgan's law}})\\&=({\color {blue}A_{1}^{c}\cup A_{2}\cup \dotsb \cup A_{k}^{c}})\cup A_{k+1}^{c}&({\text{inductive hypothesis}})\\&=A_{1}^{c}\cup A_{2}\cup \dotsb \cup A_{k}^{c}\cup A_{k+1}^{c},\end{aligned}}$$ it follows that $P(k+1)$ is true. Hence, by the principle of mathematical induction, $P(n)$ is true for every integer $n\geq 2$.

$\Box$

The strong form of induction

In this section, we will discuss a stronger form of mathematical induction. Sometimes, we need this form of mathematical induction since merely assuming "$P(k)$ is true ..." in the inductive hypothesis may not be enough to show that $P(k+1)$ is true. We may need some more helps, particularly the fact that the statement is true for all cases from the basis step to the given $k$. That is, if "$m$" is 1, then we assume $P(1),\dotsc ,P(k)$ are all true.

Since "$P(1)\land P(2)\land \dotsb \land P(k)$" is stronger than "$P(k)$", we have the name "the strong form of induction".

Theorem. (The strong form of induction) For every $m\in \mathbb {Z}$, if $P(m),P(m+1),P(m+2),\dotsc$ are statements satisfying

(i) $P(m)$ is true; and

(ii) for every integer $k\geq m$, $P(m)\land P(m+1)\land \dotsb \land P(k)\implies P(k+1)$,

then the statements $P(m),P(m+1),P(m+2),\dotsc$ are true.

This theorem is also quite intuitive: with the conditions satisfied, we get an "infinite chain of implications":

1. $P(m)$ is true by (i).
2. Because of 1., $P(m+1)$ is true by (ii).
3. Because of 1. and 2., $P(m+2)$ is true by (ii).
4. Because of 1., 2., and 3., $P(m+3)$ is true by (ii) ...

Proof. The proof for the strong form of induction is similar to that of the principle of mathematical induction. We just need to modify some parts of the proof. The blue part is the modified part.

Here we only prove the case where $m\in \mathbb {N}$.

Assume to the contrary that the theorem is false. Then, the conditions (i) and (ii) are satisfied by the statements, but there exist some positive integers $n$ for which $P(n)$ is false. Now, let the set $$S=\{n\in \mathbb {N} :P(n){\text{ is false}}\}.$$ Since $S$ is a nonempty subset of $\mathbb {N}$, by the well-ordering principle, $S$ contains a least element. Let us assume $s$ to be the least element.

Since $P(m)$ is true by the condition (i), $m\notin S$. This means the least element $s$ cannot be $m$. Hence, $s\geq m+1$, which means $s-1\geq m$.

Since $s$ is the least element of $S$, we have $s-1\notin S$, i.e., $P(s-1)$ is a true statement. Also, ${\color {blue}s-2,s-3,\dotsc ,m+1\notin S}$ (they are all less than ${\color {blue}s}$). Hence, ${\color {blue}P(m),P(m+1),\dotsc ,P(s-2)}$ are also true statements. Then, by the condition (ii), $P(s)$ is true (we have $s-1\geq m$). It follows that $s\notin S$. But this contradicts to our assumption that $s$ is the least element of $S$ (in particular, $s\in S$).

$\Box$

Hence, to prove that the statement $P(n)$ is true for every $n\geq m$ by the strong form of induction, we need to prove

(i) the basis step: $P(m)$ is true; and (ii) the inductive step: for every integer $k\geq m$, if $P(m),P(m+1),\dotsc ,P(k)$ are true (the inductive hypothesis), then $P(k+1)$ is true.

We usually use the strong form of induction to prove results that are related to recurrence relation.

Example. A sequence $x_{1},x_{2},\dotsc$ of numbers is defined by $x_{1}=1$, $x_{2}=3$ and $$x_{n}=2x_{n-1}-x_{n-2}{\text{ for every integer }}n\geq 3$$ (an equation in such form is called a recurrence relation). Prove that $x_{n}=2n-1$ for every $n\in \mathbb {N}$.

Proof. Let $P(n)$ be the open statement "$x_{n}=2n-1$". Now, we will use the strong form of induction to prove that $P(n)$ is true for every $n\in \mathbb {N}$.

Basis Step: Since $x_{1}=1=2\cdot 1-1$, $P(1)$ is true.

Inductive Hypothesis: Let $k$ be an arbitrary positive integer. Assume that $P(1),\dotsc ,P(k)$ are true. That is, assume ${\color {blue}x_{i}=2i-1}$ for every integer $i$ with ${\color {blue}1\leq i\leq k}$.

Inductive Step: We want to show that $P(k+1)$ is true, i.e., $x_{k+1}=2(k+1)-1=2k+1$. Now, using the recurrence relation, we have $${\begin{aligned}x_{k+1}&=2x_{k}-x_{k-1}&({\text{only holds when }}k+1\geq 3)\\&=2(2k-1)-(2(k-1)-1)&({\text{inductive hypothesis}})\\&=2k-1.\end{aligned}}$$ So, we have proved that $P(k+1)$ is true for the case where $k+1\geq 3$. Now, it remains to prove that $P(k+1)$ is true when $k=1$, but it is easy to prove that: $x_{2}=3=2(2)-1$, so $P(2)$ is true. Hence, by the strong form of induction, $P(n)$ is true for every $n\in \mathbb {N}$.

$\Box$

Exercise. A sequence $x_{1},x_{2},\dotsc$ of numbers is defined by $x_{1}=1$, $x_{2}=4$ and $$x_{n}=2x_{n-1}-x_{n-2}+2{\text{ for every integer }}n\geq 3.$$ Guess a formula for $x_{n}$ for every $n\in \mathbb {N}$, and prove it.

Solution

When compute $x_{n}$ for $n=3,4$ according to the recurrence relation, we get $x_{3}=9$ and $x_{4}=16$. This pattern suggests us to guess that $x_{n}=n^{2}$ for every $n\in \mathbb {N}$.

Proof. Let $P(n)$ be the open statement "$x_{n}=n^{2}$". Now, we will use the strong form of induction to prove that $P(n)$ is true for every $n\in \mathbb {N}$.

Basis Step: Since $x_{1}=1=1^{2}$.

Inductive Hypothesis: Let $k$ be an arbitrary positive integer. Assume that $P(1),\dotsc ,P(k)$ are true.

Inductive Step: We divide our proof into two cases:

Case 1: $k=1$. Then, $x_{k+1}=x_{2}=4=2^{2}=(k+1)^{2}$. So, $P(k+1)$ is true.

Case 2: $k\geq 2$. Using recurrence relation, we have $${\begin{aligned}x_{k+1}&=2x_{k}-x_{k-1}+2\\&=2k^{2}-(k-1)^{2}+2&({\text{inductive hypothesis}})\\&=k^{2}+2k+1\\&=(k+1)^{2}.\end{aligned}}$$ Thus, $P(k+1)$ is true.

Hence, $P(n)$ is true for every $n\in \mathbb {N}$ by the strong form of induction.

$\Box$

Example. A sequence $x_{1},x_{2},\dotsc$ of numbers is defined by $x_{1}=1,x_{2}=2,x_{3}=3$ and $$x_{n}=x_{n-1}+x_{n-2}+x_{n-3}{\text{ for every integer }}n\geq 4,$$ then $x_{n}<2^{n}$ for every $n\in \mathbb {N}$.

Proof. Let $P(n)$ be the open statement $x_{n}<2^{n}$.

Basis Step: Since $x_{1}=1<2^{1}=2$, $P(1)$ is true.

Inductive Hypothesis: Let $k$ be an arbitrary integer. Assume $P(1),\dotsc ,P(k)$ are true.

Inductive Step:

Case 1: $k=1$. Then, $x_{k+1}=x_{2}=2<2^{k+1}=2^{2}=4$.

Case 2: $k=2$. Then, $x_{k+1}=x_{3}=3<2^{k+1}=2^{3}=8$.

Case 3: $k\geq 3$. Then, $${\begin{aligned}x_{k+1}&=2x_{k}-x_{k-1}+2\\&<2\cdot 2^{k}-2^{k-1}+2&({\text{inductive hypothesis}})\\&=2^{k+1}+(2-2^{k-1})\\&<2^{k+1}.&(2^{k-1}>2{\text{ since }}k\geq 3)\\\end{aligned}}$$ Hence, $P(k+1)$ is true.

By the strong form of induction, $P(n)$ is true for every $n\in \mathbb {N}$.

$\Box$

Remark.

• It may appear that we consider $2-2^{k-1}$ quite "suddenly" in the proof above. Indeed, if we "think from the bottom" for case 3, then it is natural to consider it: we want $2^{k+1}-2^{k-1}+2$, which is in the form of $2^{k+1}+{\text{something}}$, to be less than $2^{k+1}$. So, it is natural consider the "something".

Exercise. Consider the sequence $F_{1},F_{2},\dotsc$ of Fibonacci numbers, defined by $F_{1}=1,F_{2}=1$ and $$F_{n}=F_{n-1}+F_{n-2}{\text{ for every integer }}n\geq 3.$$ (a) Construct a table for comparing the value of $F_{n}$ against the value of $n^{2}$ for $n=1,2,\dotsc ,15$.

(b) Hence, make a guess in the form of "$F_{n}>n^{2}$ for every integer $n\geq \;?$.", and prove the statement.

(c) By considering the even Fibonacci numbers in the table in (a), make a guess in the form of "$F_{n}$ is even if and only if $n\equiv \;?{\pmod {?}}$, for every $n\in \mathbb {N}$.", and prove the statement. (Hint: since there is "if and only if" in the statement, in the inductive step, we need to prove both "$\Rightarrow$" direction and "$\Leftarrow$" direction. But, we can prove both directions at once in this case.

(d) Prove that $F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\sqrt {5}}}$ for every $n\in \mathbb {N}$, where $\varphi ={\frac {1+{\sqrt {5}}}{2}}$ (golden ratio) and $\psi ={\frac {1-{\sqrt {5}}}{2}}$ (conjugate of golden ratio). This gives a direct formula to compute $n$th Fibonacci number, which is more efficient than using the recurrence relation in the definition for the computation. (Hint: The roots of the quadratic equation $x^{2}=x+1$ are $\varphi$ and $\psi$.)

Solution

(a) $${\begin{array}{cccccccccccccccc}n&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\hline F_{n}&1&1&2&3&5&8&13&21&34&55&89&144&233&377&610\\n^{2}&1&4&9&16&25&36&49&64&81&100&121&144&169&196&225\\\end{array}}$$ (b) From (a), it appears that when $n\geq 13$, $F_{n}$ increases faster than $n^{2}$. So, it is natural to guess that $F_{n}>n^{2}$ for every integer $n\geq 13$.

Proof. Let $P(n)$ be the open statement $F_{n}>n^{2}$.

Basis Step: Since $F_{13}=233>13^{2}=169$, $P(13)$ is true.

Inductive Hypothesis: Let $k$ be an arbitrary integer with $k\geq 13$. Assume that $P(13),P(14),\dotsc ,P(k)$ are true.

Inductive Step: Using recurrence relation, we have $${\begin{aligned}F_{k+1}&=F_{k}+F_{k-1}\\&>k^{2}+(k-1)^{2}\\&=2k^{2}-2k+1\\&=(k^{2}+2k+1)+(k^{2}-4k)\\&>k^{2}+2k+1&(k^{2}>4k{\text{ since }}k\geq 13)\\&=(k+1)^{2}.\end{aligned}}$$ Hence, $P(k+1)$ is true, and by the strong form of induction, $P(n)$ is true for every integer $n\geq 13$.

$\Box$

(c) From the table in (a), when $n=3,6,9,12,15$ (which are all multiples of 3), $F_{n}$ is even. This suggests us to guess that $F_{n}$ is even if and only if $n\equiv 0{\pmod {3}}$ for every $n\in \mathbb {N}$.

Proof. Let $P(n)$ be the open statement $F_{n}$ is even if and only if $n\equiv 0{\pmod {3}}$.

Basis Step: Since $F_{1}$ is odd and $1\not \equiv 0{\pmod {3}}$, $P(1)$ is true ($\mathbf {F} \iff \mathbf {F}$).

Inductive Hypothesis: Let $k$ be a positive arbitrary integer. Assume that $P(1),\dotsc ,P(k)$ are true.

Inductive Step: By recurrence relation, $F_{k+1}=F_{k}+F_{k-1}$. So, $${\begin{aligned}F_{k+1}{\text{ is even}}&\iff (F_{k}{\text{ is even and }}F_{k-1}{\text{ is even}}){\text{ or }}(F_{k}{\text{ is odd and }}F_{k-1}{\text{ is odd}})\\&\iff (k\equiv 0{\pmod {3}}{\text{ and }}k-1\equiv 0{\pmod {3}}){\text{ or }}(k\not \equiv 0{\pmod {3}}{\text{ and }}k-1\not \equiv 0{\pmod {3}})&({\text{inductive hypothesis}})\\&\iff (\underbrace {k\equiv 0{\pmod {3}}{\text{ and }}k\equiv 1{\pmod {3}}} _{\mathbf {F} }){\text{ or }}(k\not \equiv 0{\pmod {3}}{\text{ and }}k\not \equiv 1{\pmod {3}})\\&\iff k\equiv 2{\pmod {3}}&({\text{Euclid's division lemma}})\\&\iff k+1\equiv 3{\pmod {3}}\\&\iff k+1\equiv 0{\pmod {3}}\\\end{aligned}}$$ (We have $k-1\not \equiv 0{\pmod {3}}\iff k\not \equiv 1{\pmod {3}}$, since by the compatibility with translation, it can be shown directly that $k-1\equiv 0{\pmod {3}}\iff k\equiv 1{\pmod {3}}$, and after showing this, we have the desired logical equivalence.)

Thus, $P(k+1)$ is true. Hence, by the strong form of induction, $P(n)$ is true for every $n\in \mathbb {N}$.

$\Box$

(d)

Proof. Let $P(n)$ be the statement $F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\sqrt {5}}}$.

Basis Step: Since ${\frac {\varphi -\psi }{\sqrt {5}}}={\frac {2{\sqrt {5}}/2}{\sqrt {5}}}=1=F_{1}$, $P(1)$ is true.

Inductive Hypothesis: Let $k$ be a positive arbitrary integer. Assume $P(1),\dotsc ,P(k)$ are true.

Inductive Step:

Case 1: $k=1$. Then, ${\frac {\varphi ^{k+1}-\psi ^{k+1}}{\sqrt {5}}}={\frac {\varphi ^{2}-\psi ^{2}}{\sqrt {5}}}={\frac {(\varphi -\psi )(\varphi +\psi )}{\sqrt {5}}}={\frac {(2{\sqrt {5}}/2)(2/2)}{\sqrt {5}}}=1=F_{k+1}=F_{2}$. Hence, $P(k+1)$ is true.

Case 2: $k\geq 2$. Then, apply the recurrence relation: $${\begin{aligned}F_{k+1}&=F_{k}+F_{k-1}\\&={\frac {\varphi ^{k}-\psi ^{k}}{\sqrt {5}}}+{\frac {\varphi ^{k-1}-\psi ^{k-1}}{\sqrt {5}}}&({\text{inductive hypothesis}})\\&={\frac {\varphi ^{k}+\varphi ^{k-1}-\psi ^{k}-\psi ^{k-1}}{\sqrt {5}}}\\&={\frac {\varphi ^{k-1}(\varphi +1)-\psi ^{k-1}(\psi +1)}{\sqrt {5}}}\\&={\frac {\varphi ^{k-1}\varphi ^{2}-\psi ^{k-1}\psi ^{2}}{\sqrt {5}}}&({\text{hint}})\\&={\frac {\varphi ^{k+1}-\psi ^{k+1}}{\sqrt {5}}}.\\\end{aligned}}$$ Hence, $P(k+1)$ is true.

Thus, by the strong form of induction, $P(n)$ is true for every $n\in \mathbb {N}$.

$\Box$