Mathematical Reasoning
Introductory Notes on Mathematical Proofs and Discrete Math

Abstract

This document presents a compilation of notes I took while taking Discrete Math & Probability Theory (CS70) at the University of California at Berkeley, with an emphasis on Discrete Math. These notes were inspired by the book Introduction to Mathematical Proofs.

Note 1 Numbers, Sets, and Functions

1.1 Quadratic Equations

One of the simplest classes of equations we regularly solve are linear equations, equations of the form below, where the greatest power of our variable is one. As a matter of convention, we write the general equation as

$ax+b=0.$ (1.1)

Solving this equation can be done by rearranging and then dividing both sides by $a$, yielding

$x=-{\displaystyle \frac{b}{a}}.$

Naturally, we may want to solve some more complicated quadratic equations, where the greatest power of the variable is two. Such equations take the general form

$a{x}^2+bx+c=0.$ (1.2)

To solve this equation, we need to isolate $x$ and in doing so, reduce the number of terms with the variable from two to one. This can be accomplished factoring through a problem solving strategy called wishful thinking. First, we being by taking out the coefficient of the first term, $a$.

$a\left(x^2+{\displaystyle \frac{b}{a}}x\right)+c$

Writing the left-hand side of the equation like this, we can see by adding the right constant inside the parentheses, this can be reduced to a square. Returning to our original equation, this results in the following steps.

$0$ $=a{x}^2+bx+c$

$=a\left(x^2+{\displaystyle \frac{b}{a}}x\right)+c$

$=a\left(x^2+{\displaystyle \frac{b}{a}}x+{\displaystyle \frac{b^2}{4a^2}}\right)-{\displaystyle \frac{b^2}{4a}}+c$

$=a{\left(x+{\displaystyle \frac{b}{2a}}\right)}^2-\left({\displaystyle \frac{b^2}{4a}}-c\right)$

We’ve derived the exact type of equation we can easily solve, one in which the variable $x$ is restricted to a single term.

$a{\left(x+{\displaystyle \frac{b}{2a}}\right)}^2-\left({\displaystyle \frac{b^2}{4a}}-c\right)$ $=0$

$a{\left(x+{\displaystyle \frac{b}{2a}}\right)}^2$ $={\displaystyle \frac{b^2}{4a}}-c$

${\left(x+{\displaystyle \frac{b}{2a}}\right)}^2$ $={\displaystyle \frac{b^2-4ac}{4a^2}}$

$x+{\displaystyle \frac{b}{2a}}$ $=\pm \sqrt{{\displaystyle \frac{b^2-4ac}{4a^2}}}$

We needed to include the plus-minus ($\pm$) sign since squaring removes the sign and therefore the term

$x+{\displaystyle \frac{b}{2a}}$

could be either positive or negative and have the same square. By simplifying the square root, and moving the constant beside $x$ to the other side, we derive the quadratic formula which gives the solutions to a quadratic equation in terms of its coefficients.

$x$ $=-{\displaystyle \frac{b}{2a}}\pm \sqrt{{\displaystyle \frac{b^2-4ac}{4a^2}}}$ (1.3)

$={\displaystyle \frac{-b\pm \sqrt{b^2-4ac}}{2a}}$ (1.4)

From this, we can construct our first theorem in this course.

Theorem 1.

A quadratic equation $a{x}^2+bx+c=0$ has at least one solution when

$b^2-4ac\ge 0$ (1.5)

Proof.

In the case where $b^2-4ac\ge 0$, we have explicitly constructed a solution to the quadratic equation. To verify this, we will plug the positive root into the equation to ensure the result is 0.

$a{x}^2+bx+c$ $=a{\left({\displaystyle \frac{-b+\sqrt{b^2-4ac}}{2a}}\right)}^2+b\left({\displaystyle \frac{-b+\sqrt{b^2-4ac}}{2a}}\right)+c$

$=\left({\displaystyle \frac{b^2}{2a}}-{\displaystyle \frac{b\sqrt{b^2-4ac}}{2a}}-c\right)+\left({\displaystyle \frac{b\sqrt{b^2-4ac}}{2a}}-{\displaystyle \frac{b^2}{2a}}\right)+c$

$=0$

Therefore, we have show a solution exists when $b^2-4ac\ge 0$ for a quadratic equation. More than that, we have determined the specific form of such a solution. ∎ End of proof

We can actually show a stronger result about the solutions of a quadratic equation, though the proof is to the reader.

Theorem 2.

If $b^2-4ac$ is positive, a quadratic equation has two solutions; if it is negative, the equation has no real solutions; and if it is exactly equal to zero there is only one unique solution. This can be express in the following way.

The techniques used to solve this problem and prove its solution provide a preview of the kinds of thinking and problem solving which will be invaluable to this course. More than any one theorem or result, this course is an introduction to mathematical thinking.

1.2 Inequalities

Our discussion so far has revolved around statements of equality, and so naturally we might wonder about inequalities. To clearly define our terminology going forward, we will use the following definitions.

Terminology	Definition
Positive	$x>0$
Negative
Nonnegative	$x\ge 0$

In order to work with these, it is important to review some basic properties of inequalities.

1. For any real numbers $a$ and $b$, one of the following statements is true:

2. For real numbers $a$, $b$, and $c$…

   $\text{if }a>b\text{ and }b>c,\text{ then }a>c$

3. Given that $a>b$, adding or subtracting constants from both sides preserves equality, meaning for any $c$, the inequalities below are also true.

   $a+c$ $>b+c$

   $a-c$ $>b-c$

4. If $a>b$, the effect of multiplying by another number $c\ne 0$ depends on the sign of $c$.

   $ac>bc\text{ if }c>0$

   In other words, if $c$ is negative, the sign of the inequality is flipped.

5. The square of any real number is nonnegative. Furthermore, the square of a number is 0 if and only if the number itself is 0.

These five fundamental properties are essential in proving some foundational inequalities, the first of which is called the Arithmetic-Geometric Mean Inequality. In the presentation of the theorem, we explain how to approach proofs.

Theorem 3 (AGM Inequality).

If $x$ and $y$ are real numbers, then:

${\left({\displaystyle \frac{x+y}{2}}\right)}^2\ge xy$ (1.6)

Rough Work.

A mathematical proof begins with true statements and derives the desired result through a series of logical sound steps. In looking for an appropriate place to start, it often helps to rearrange the statement we want to prove until we reach a true statement, working backwards to construct the proof. In this case:

${\left({\displaystyle \frac{x+y}{2}}\right)}^2$ $\ge xy$

$⟹{\displaystyle \frac{x^2+2xy+y^2}{4}}$ $\ge xy$

$⟹x^2+2xy+y^2$ $\ge 4xy$

$⟹x^2-2xy+y^2$ $\ge 0$

$⟹{(x-y)}^2$ $\ge 0$

We know the last line is true, since the square of any number must be nonnegative, hence writing the proof is now easy.

Proof.

For any real numbers $x$ and $y$, we know the square of the difference must be positive.

${(x-y)}^2$ $\ge 0$

$⟹x^2-2xy+y^2$ $\ge 0$

$⟹x^2+2xy+y^2$ $\ge 4xy$

$⟹{\displaystyle \frac{x^2+2xy+y^2}{4}}$ $\ge xy$

$⟹{\left({\displaystyle \frac{x+y}{2}}\right)}^2$ $\ge xy$

Therefore, the Arithmetic-Geometric Mean holds for any real numbers. ∎ End of proof

Furthermore, in the case where both $x$ and $y$ are nonnegative, we can take positive square roots to obtain another form of the inequality.

${\displaystyle \frac{x+y}{2}}\ge \sqrt{xy}\text{ for }x,y\ge 0$ (1.7)

This form elucidates the name of this inequality; the left side is the arithmetic mean of $x$ and $y$, while the right-hand side represents the geometric mean, while powerful inequality relates the two types of averages. Our proof also provides us some additional insight, since it begins with the claim

${(x-y)}^2\ge 0$

Remember the square of any real number is equal to 0 if and only if the number is 0. Therefore we have a simple condition for equality in the AGM Inequality.

Theorem 4.

Equality hold in the AGM Inequality if and only if $(x-y)=0$ or $x=y$. In other words

${\left({\displaystyle \frac{x+y}{2}}\right)}^2=xy\text{ if and only if }x=y.$ (1.8)

To introduce the second major inequality, the absolute value of a number, traditionally denoted as $|x|$ needs to be defined.

The absolute value can be thought of as the positive distance to the origin. For example, $-2$ is exactly 2 units away from the origin. The absolute value can also be visualized through its graph.

Figure 1.1: The graph $y=|x|$

Once again, we present fundamental properties of absolute values, in order to provide a foundation for working with these mathematical functions.

1. For any real number $x$, $|x|\ge x$ and $|x|\ge 0$.

2. Given real numbers $x$ and $y$, $|xy|=|x|\cdot |y|$.

3. Squaring a number strips its negative sign, and taking the positive root ensures the result will be positive. Therefore the [positive] square root of the square is the absolute value.

   $|x|=\sqrt{x^2}$

The last property is rather interesting, and can be proved. Notice for proving these simple properties of absolute values, a proof by cases is often most effective, a proof technique in which we break all possibilities into distinct cases or scenarios and prove the claim for each of them. Since the absolute value function behaves different for positive and negative numbers, these are naturally our cases.

Theorem 5.

For any real number $x$, we have:

$|x|=\sqrt{x^2}$ (1.9)

Proof by Cases.

Consider the cases when $x$ is positive, zero and negative separately. Note formally, one of these cases must be true from the trichotomy property (see the first property of inequalities above).

Case 1. $x>0$

$\sqrt{x^2}$ $=x$

$=|x|$

Case 2. $x=0$

$\sqrt{0^2}$ $=0$

$=|0|$

Case 3.

Assume that $x=-a$ for some positive real number $a$. Notice that $|x|=a$ Plugging this into the expression of the square root of the square:

$\sqrt{x^2}$ $=\sqrt{{(-a)}^2}$

$=\sqrt{a^2}$

$=a$

$=|x|$

∎ End of proof

At this point, we can go ahead and introduce the next major inequality. Note that we mentioned that the absolute value of the product of two numbers is the product of the absolute values, or

$|xy|=|x|\cdot |y|.$

Unfortunately, the same does not hold true for sums–the analogous statement is false.

$|2+(-1)|\ne |2|+|-1|$

However, there is a relationship between the two quantities which can be expressed as an inequality.

Theorem 6 (Triangle Inequality).

Given real numbers $x$, $y$ the sum of the absolute values is always greater than or equal to the absolute value of the sum.

$|x+y|\le |x|+|y|$ (1.10)

Rough work.

Once again, we begin with rough work to determine how to progress on the proof. In order to remove the absolute value sides, it seems reasonable to square both sides.

$|x+y|$ $\le |x|+|y|$

$⟹{|x+y|}^2$ $\le {(|x|+|y|)}^2$

$⟹{(x+y)}^2$ $\le {(|x|+|y|)}^2$

$⟹x^2+2xy+y^2$ $\le {|x|}^2+2|x||y|+{|y|}^2$

$⟹x^2+2xy+y^2$ $\le x^2+2|xy|+y^2$

$⟹xy$ $\le |xy|$

Notice we arrived at a statement which is clearly true. Remember that the absolute value of any real number is always greater than or equal to the number. At this point we can write the proof.

Proof.

Consider any real number $x$ and $y$. From the basic properties of absolute values we know the product of these numbers must be less than or equal to its absolute value.

$xy$ $\le |xy|$

$⟹x^2+2xy+y^2$ $\le x^2+2|xy|+y^2$

$⟹x^2+2xy+y^2$ $\le {|x|}^2+2|x||y|+{|y|}^2$

$⟹{(x+y)}^2$ $\le {(|x|+|y|)}^2$

$⟹{|x+y|}^2$ $\le {(|x|+|y|)}^2$

Both terms being squared are positive, hence we can safely square root both sides without affecting the inequality.

$\therefore |x+y|\le |x|+|y|$

∎ End of proof

Once again in this proof, we used rough work to arrive at a statement we knew was true, and then worked backward to derive the result we wanted from this true statement. We had to be more careful working backward in this example since we square rooted an inequality. Though this works when both terms inside the square are positive, it may fail spectacularly otherwise.

$4\ge 1$

$⟹{(-2)}^2$ $\ge {(1)}^2$

$\mathrm{／}⟹-2$ $\ge 1\text{ false!}$

1.3 Sets

So far we have been relying on intuition to define the real numbers, the focus of our attention. Although the formal definitions of the real numbers are outside the scope of these notes, it is worth paying attention to this fundamental notion of a group of numbers. In mathematics, this concept is represented as a set, a well-defined collection of objects. Some examples are listed below.

$S=\{\text{Saturday},\text{Sunday}\}$

$T=\{1,2,3,\mathrm{\dots }\}$

$R=\{n^2:n\text{ is even}\}$

$\varphi \text{ or }\{\}$

The last example presents two ways to denote the empty set, the set with no elements. Notice $R$ is the set of squares of all even numbers. The ‘:’ introduces a condition in the set definition. Since every set must be well-defined, every object is either an element of the set or not. If set $A$ contains element $a$ but does not contain $b$, we can write

$a\in A\text{ and }b\notin A.$

In defining sets, we often specify the elements to be included from some universe of objects. However, the elements of elements not in $A$ clearly make a set as well, one which is intrinsically linked to $A$. This set is denoted the complement of $A$, written as $A^c$ and defined as

$A^c=\{x\in \text{universe }:x\notin A\}$

Though we will explore notions of size in more depth later on, for now we define the cardinality, written as

$|A|\text{ or }\mathrm{card}(A),$

as its size. For finite sets, sets without an infinite number of elements, the cardinality is simply the number of elements. All such cardinalities are in the set $\{0,1,2,\mathrm{\dots }\}$, with 0 reserved for the empty set.

Since a set is unordered and cannot contain duplicate items, a natural definition of equality is that both sets contain the same elements. On the other hand, if every element of set $B$ is in set $A$, then in some sense the latter set contains the former. Mathematically, we write that $B$ is a subset of $A$ or

$B\subseteq A.$

Notice under this definition, the empty set is a subset of every set. Similarly, a set is always a subset of itself. In cases where we want to exclude this possibility, that the sets are equal, in explaining the relationship between the two sets, we can write $B$ is a proper subset of $A$ or

$B\subset A$

which means $B\subseteq A$ but $B\ne A$. Along with the real numbers there are a handful of other important sets used to refer to classes of numbers.

Symbol	Name	Set
$\mathbb{N}$	Natural Numbers	$\{1,2,3,4,\mathrm{\dots }\}$
$\mathbb{Z}$	Integers	$\{\mathrm{\dots },-2,-1,0,1,2,\mathrm{\dots }\}$
$\mathbb{Q}$	Rational Numbers	$\{{\displaystyle \frac{p}{q}}:p,q\in \mathbb{Z}\}$
$ℝ$	Real Numbers

Notice we defined the natural numbers to exclude 0, but the symbol ${\mathbb{N}}_0$ could be used to refer to all naturals along with 0. Based on the descriptions of each of these sets, each contains the previous plus some additional elements. Therefore, we can write

$\mathbb{N}\subseteq {\mathbb{N}}_0\subseteq \mathbb{Z}\subseteq \mathbb{Q}\subseteq ℝ.$ (1.11)

Since each set contains the previous, we may wonder what elements are in one but not the other. In some cases, this set itself might be valuable. For example all real numbers which are not rational are referred to as as irrational, and the set which contains all such numbers the irrational numbers. This set then is a result of taking the real numbers and subtracting away the rational numbers. This operation, along with a few more are formalized before for arbitrary sets $A$ and $B$.

$\text{Subtraction. }A-B$ $=\{x\in A:x\notin B\}$

$\text{Intersection. }A\cap B$ $=\{x:x\in A\text{ and }x\in B\}$

$\text{Union. }A\cup B$ $=\{x:x\in A\text{ or }x\in B\}$

$\text{Cartesian Product. }A\times B$ $=\{(a,b):a\in A\text{ and }b\in B\}$

The intersection is the set of all elements in both, while the union is the set of all elements in either. Two sets are called disjoint if their intersection is the empty set meaning they have no common elements. Written out this would mean for disjoint sets $S$ and $T$,

$S\cap T=\varphi$

The cartesian product of two sets outputs a set with a completely different structure: a set of tuples containing all possibly pairs of elements from $A$ and $B$. Unlike sets, tuples are ordered lists of elements which could contain duplicates. This idea of product can be extended beyond two sets.

$A\times B$ $=\{(a,b):a\in A,b\in B\}$

$B\times A$ $=\{(b,a):a\in A,b\in B\}$

$A\times B\times C$ $=\{(a,b,c):a\in A,b\in B,c\in C\}$

Repeated products of the same set can be abbreviated as a power, similar to the real numbers.

$A^k$ $=\underset{k\text{ times}}{\underbrace{A\times \mathrm{\cdots }\times A}}$

$=\{(a_1,a_2,\mathrm{\dots },a_k):a_1,a_2,\mathrm{\dots },a_k\in A\}$

One final concept that must be introduced to complete our discussion on introductory set theory is the power set of a set, which contains all possible subsets. Formally we write this as

$\text{Power set. }𝒫(A)=\{S:S\subseteq A\}.$

To ensure this section includes a proof, we end with a simple theorem about the size of a power set. We will explore another proof of this theorem later in the course.

Theorem 7.

For a finite set $A$, if $|A|=n$, then its power set $𝒫(A)$ has cardinality $2^n$.

Examples.

One way to begin working on a proof is the test the claim with examples, since they may yield insight into why the result is true.

$\varphi$ $=\{\varphi \}$

$𝒫(\{0,1\})$ $=\{\varphi ,\{0\},\{1\},\{0,1\}\}$

In each of these cases, the result holds. When the sizes of sets were 0 and 2, their power sets had sizes of 1 and 4 respectively. Notice we would also expect the number of subsets to be even, since for every subset $S\subseteq A$, $(A-S)$ is also one, and this theorem seems to check out in that regard. At this point we can present the proof

Proof.

Since $A$ is finite and $|A|=n$ then the set must have $n$ elements. Let us arbitrarily assign labels so that

$A=\{a_1,a_2,\mathrm{\dots }{a}_n\}$

In constructing a subset, each of these $n$ distinct elements can be chosen to either be included or excluded from the set. Since every subset can be created with these series of $n$ choices, and each choice has two options, the number of subsets is $2^n$. ∎ End of proof

A major class of proofs involves proving two sets are equal. One possible way of doing this involves showing each set is a subset of another. To prove set $S$ is a subset of $T$, we must show if $x$ is an element of $S$ then it is also an element of $T$. This would mean every element in $S$ is contained in $T$ and therefore $S\subseteq T$. To provide an example, we introduce another theorem.

Theorem 8 (De Morgan’s laws).

Given two sets $A$ and $B$, the following statements are true.

${(A\cup B)}^c$ $=A^c\cap B^c$ (1.12)

${(A\cap B)}^c$ $=A^c\cup B^c$ (1.13)

Proof.

Since the proof the statements are nearly identical, only the first will be proved; the second is left as an exercise. Since we are proving the equality of sets, we proceed by showing the left-hand side (LHS) is a subset of the right-hand side (RHS) and vice versa.

Part 1. ${(A\cup B)}^c\subseteq (A^c\cap B^c)$

Assume that $x\in {(A\cup B)}^c$, we will show $x$ is also an element of $(A^c\cap B^c)$ through a series of implications.

$x\in {(A\cup B)}^c$ $⟹x\notin (A\cup B)$

$⟹x\notin A\text{ and }x\notin B$

$⟹x\in A^c\text{ and }x\in B^c$

$⟹x\in A^c\cap B^c$

Part 2. $(A^c\cap B^c)\subseteq {(A\cup B)}^c$

Now assume that $x\in (A^c\cap B^c)$, we will show $x$ is also an element of $x\in {(A\cup B)}^c$.

$x\in (A^c\cap B^c)$ $⟹x\in A^c\text{ and }x\in B^c$

$⟹x\notin A\text{ and }x\notin B$

$⟹x\notin (A\cup B)$

$⟹x\in {(A\cup B)}^c$

Since we have proved that ${(A\cup B)}^c\subseteq (A^c\cap B^c)$ and $(A^c\cap B^c)\subseteq {(A\cup B)}^c$, this is enough to show equality.

$\therefore {(A\cup B)}^c$ $=A^c\cap B^c$

∎ End of proof

1.4 Functions

At this point we can introduce a very special type of set which has profound uses in mathematics. This, of course, is a function, which is a set of input-output ordered pairs which can represented as

$\{(x,f(x)):x\in \text{domain}\}$

Term	Definition
Domain	The set of all allowed inputs
Codomain (Target Space)	The set of all allowed outputs
Image (Range)	The set of all actual outputs

The function, then, takes an input from the domain and returns a single output in the codomain. This property of linking the domain to the codomain explains why function are often called maps. Since the image is the set of outputs, and a subset of the codomain, it would be the set that results from applying the function to every element in the domain. Thus, for a function $f$ with domain $A$, the image is often denoted as $f(A)$.

$f(A)$ $=\{f(a):a\in A\}$

In defining a function, the domain and codomain must be explicitly specified, hence the following notation is often used.

A function is called real-valued if its image is a subset of the real numbers, and thus all its outputs are real numbers. The graph of a function is a plot of all the input-output pairs. In working with functions there are a few elementary ways to combine them.

$\text{Addition. }(f+g)(x)=f(x)+g(x)$ (1.14)

$\text{Multiplication. }(f\cdot g)(x)=f(x)\cdot g(x)$ (1.15)

$\text{Composition. }(f\circ g)(x)=f(g(x))$ (1.16)

We are often extremely interested in the image of a real-valued function. In particular, we may wonder about the nature of this set: does it have a maximum or minimum, or does the function go to infinity? Formally, a function $f:A\to ℝ$ is bounded if there exists some $M\in ℝ$ such that

$|f(x)|\le M$

for all $x\in A$. Notice in this definition $M$ acts both a positive and negative bound since the statement is equivalent to

$-M\le f(x)\le M.$

It turns out that sums and products of bounded functions are bounded as well, results we prove below. Notice in these proofs we clearly state our assumptions and what we plan on showing, a technique that helps inform our approach.

Theorem 9.

If functions $f$ and $g$ are bounded so are the functions $(f\cdot g)$ and $(f+g)$, formed by the sum and product of these functions respectively.

Proof.

Since $f$ and $g$ are bounded, there exist $M\in ℝ$ and $N\in ℝ$ for which

$|f(x)|\le M\text{ and }|g(x)|\le N.$

We hope to show there exists some bound on $|(f\cdot g)(x)|$, therefore our aim should be to express this in terms of the quantities we already have bounds for.

$|(f\cdot g)(x)|$ $=|f(x)\cdot g(x)|$

$=|f(x)|\cdot |g(x)|$

$\le M\cdot N$

This shows that we have discovered a bound for the function: the product of the two bounds of our original function. Hence the function is bounded. ∎ End of proof

Proof.

Once again, assume there exist $M\in ℝ$ and $N\in ℝ$ for which

$|f(x)|\le M\text{ and }|g(x)|\le N.$

We wish to find a bound for $|(f+g)(x)|$. However, in this case it is more tricky to decompose this into $|f(x)|$ and $|g(x)|$, and requires the triangle inequality.

$|(f+g)(x)|$ $=|f(x)+g(x)|$

$\le |f(x)|+|g(x)|$

$\le M+N$

Thus, we have proved $(f+g)$, showing the sum of the bounds of the functions is the bound for the sum of the functions. ∎ End of proof

In general, approach bounding proofs by expressing the bounded functions by their definitional inequality. Then work on manipulating these inequalities through inequality or absolute value rules to obtain the desired result.

1.5 Fields

So far in our deals with $ℝ$, we have been implicitly relying on properties or axioms of arithmetic in the real numbers. Many of these properties are not exclusive to the reals, and apply to a class of algebraic structures called fields. A field, $F$, consists of

$(F,0,1,+,\cdot )\text{ where }F=\{0,1,\mathrm{\dots }\}.$

$F$ is a set of elements in the field in including at least the additive identity 0 and the multiplicative identity 1. A field also includes two predefined binary operations, addition and multiplication, which take two inputs in $F$ and return the sum and product in $F$ respectively. These function must obey the following axioms for $x,y,z\in F$.

$+:F\times F\to F$

$\cdot :F\times F\to F$

Name	Addition	Multiplication
Closure	$x+y\in F$	$x\cdot y\in F$
Associativity	$(x+y)+z=x+(y+z)$	$(x\cdot y)\cdot z=x\cdot (y\cdot z)$
Commutativity	$x+y=y+x$	$x\cdot y=y\cdot x$
Identity	$x+0=x$	$x\cdot 1=x$
Inverses	each non-zero element has an additive inverse	each element has an multiplicative inverse
Distributivity	$x\cdot (y+z)=x\cdot y+x\cdot z$

To clarify the inverse axioms, the first states that for any $x\in F$, there exists a $-x$ in the field, such that

$x+(-x)=0,-x\in F.$

In this case, $-x$ is simply an element of the field, and is called the additive inverse of $x$. Commutatively, $x$ is the additive inverse of $-x$. Sometimes, the additive inverse of a field element is itself–the trivial example is 0:

$0+0=0.$

For non-zero elements in the field, a multiplicative inverse exists as well, which means for $x\in F-\{0\}$, there exists a $x^{-1}$, such that

$x\cdot x^{-1}=1,x^{-1}\in F.$

Similar to the additive inverse, this inverse is an element of the field and likewise can be the same number. With this axiom, we can define two new operations in the field. Subtraction amounts to adding by the additive inverse and division is multiplication by the multiplicative inverse. For field elements $x$, $y$ in some field $F$.

$x-y$ $:=x+(-y)$ (1.17)

$x/y$ $:=x\cdot y^{-1}\text{ given }y\ne 0$ (1.18)

Notice the $:=$ here emphasizes the expression on the left is defined to be equal to the expression on the right. To avoid confusion, when working in fields, we will refrain from using subtraction and division and instead refer to the inverses.

Naturally, we may now wonder, having laid out these axioms, which sets which classes of numbers, with regularly defined addition and multiplication, constitute fields. To prove whether a set with defined operations is a field is simply a matter of checking each of the axioms.

Theorem 10.

The natural numbers $(\mathbb{N})$ and integers $(\mathbb{Z})$ are not fields.

Proof.

We will prove this theorem in two parts, first dealing with the natural numbers proceeded by the integers.

Part 1. $\mathbb{N}$

The additive inverse axiom fails for all integers. Specifically, the number 1, for example, has no additive inverse since for all $n\in \mathbb{N},1+n>0$. Since 1 had no additive inverse this is not a field.

Part 2. $\mathbb{Z}$

The multiplicative inverse axiom fails for $2\in \mathbb{Z}$. Once way of rigourously showing this is to notice $2\cdot n$ is even for all $n\in \mathbb{Z}$. Therefore this value can never be 1, and hence no multiplicative inverse exists.
∎ End of proof

Theorem 11.

The rational numbers $(\mathbb{Q})$ and real numbers $(ℝ)$ with regularly defined addition and multiplication constitute fields.

Proof.

The process of proving these are fields are rather tedious, verifying each of the field axioms individually, and left as an exercise. However, note that the inverse axioms that failed for the natural numbers and integers hold for these two sets. The additive and multiplicative inverses are respectively shown below.

${\displaystyle \frac{p}{q}}\in \mathbb{Q}\to -{\displaystyle \frac{p}{q}},{\displaystyle \frac{q}{p}}\in \mathbb{Q}$

$x\in ℝ\to -x,{\displaystyle \frac{1}{x}}\in ℝ$

∎ End of proof

These suite of axioms lead to a host of simple properties, which should feel familiar to us after working with the real numbers. We introduce an expansive theorem which lays out many of these properties.

Theorem 12.

Given a field $F$ defined with addition and multiplication and three elements $x$, $y$, and $z$, the following properties must hold.

$x\cdot 0=0$ (1.19)

$\text{if }x\cdot y=0\text{ then }x=0\text{ or }y=0$ (1.20)

$-x=x\cdot (-1)$ (1.21)

$(-x)\cdot (-y)=x\cdot y$ (1.22)

$\text{if }x+y=x+z\text{ then }y=z$ (1.23)

$\text{if }x\cdot y=x\cdot z\text{ then }y=z\text{ if }x\ne 0$ (1.24)

Proof.

Proving every statement in the theorem would take up a lot of space, hence we will present proofs for the first and last statement, hopefully providing a model for approaching proofs to the remaining statements.

Statement 1.18. $x\cdot 0=0$

Notice that although we take this for grated in the real numbers, it is not a field axiom and must be proved. Since 0 is the additive inverse, in searching for a proof we should look to exploit its properties.

$x\cdot 0$ $=x\cdot (0+0)$ identity

$=x\cdot 0+x\cdot 0$ distributive

At this point notice by closure we know $x\cdot 0$ lies within the field. Therefore, by the inverses axiom it must have an additive inverse. Now we add this to both sides of the equation.

$x\cdot 0+x\cdot 0$ $=x\cdot 0$

$x\cdot 0+x\cdot 0+(-(x\cdot 0))$ $=x\cdot 0+(-(x\cdot 0))$

$x\cdot 0+(x\cdot 0+(-(x\cdot 0)))$ $=0$ associative

$x\cdot 0+0$ $=0$ inverse

$x\cdot 0$ $=0$ identity

This is the result we were looking for. Notice instead of subtracting $x\cdot 0$ from each side, as we would in the real numbers, we added the additive inverse to both sides. In this proof we clearly listed which axiom allowed us to make each step, and although this is not necessary, it makes it less likely to perform an operation which is not allowed.

Statement 1.23. $\text{if }x\cdot y=x\cdot z\text{ then }y=z\text{ if }x\ne 0$

Once again, we attempt a direct proof based on the field axioms. Since $x\ne 0$ from the inverses axiom, we know there exists some $x^{-1}\in F$ such that

$x\cdot x^{-1}=1$

We simply multiply both sides of out equation with this term.

$x\cdot y$ $=x\cdot z$

$x^{-1}\cdot x\cdot y$ $=x^{-1}\cdot x\cdot z$

$(x^{-1}\cdot x)\cdot y$ $=(x^{-1}\cdot x)\cdot z$ associativity

$1\cdot y$ $=1\cdot z$ inverse

$y$ $=z$ identity

Once again, we have arrived at our result, hence we have proved this this statement for arbitrary fields. Notice we could approach this problem as if we were asked to prove this for real numbers. Instead of dividing both sides by $x$ we multiplied by $x^{-1}$ to arrive at the result. ∎ End of proof

The two fields we have discussed so far have had an infinite number elements with predefined addition and multiplication operations that mirror their common usage. However, we may wonder what other fields exists, and in particular, what such a field would look like for a finite number of elements, a finite field. Since a field must have at least two elements, let us attempt to construct a two element field, called the binary field. Consider the field

$(S,0,1,+,\cdot )\text{ where }S=\{0,1\}.$

Unfortunately, we must define multiplication and addition in this field since otherwise the latter would defy the closure field axiom as

$1+1$ $=2\notin S.$

For finite fields with a small number of elements, the most effective method of defining these operations involves writing addition and multiplication tables, providing outputs for all possible pairs of input for each function.

      

Notice, that multiplying by 0 always returns 0 (as we proved above) and multiplying by 1 gives the same number. Similarly, adding 0 returns the same number by the identity property.

      

This only leaves one output to be decided, the sum $1+1$. In the next theorem we prove that this is equal to 0. To do this, we introduce a new type of proof, a proof by contradiction.

Theorem 13.

If $S$ is the binary field with $S=\{0,1\}$, then $1+1=0$.

Proof by Contradiction.

By the closure property of fields, we know the sum $1+1$ must lie within $S$ and is therefore it is either 0 or 1. Assume for sake of contradiction that it is indeed 1, so that

$1+1=1.$

By the inverse axiom, we know that 1 has an additive inverse in the field. We now add this inverse to both sides of the equation.

$1+1+(-1)$ $=1+(-1)$

$1+0$ $=0$

$1$ $=0$

This is clearly false since by definition a field must have distinct elements 0 and 1. Since this would be a logical consequence of letting $1+1=1$, that assumption must be false. Hence we are left only with the possibility that

$1+1=0.$

∎ End of proof

In a proof by contradiction, we assume the opposite of the statement we are trying to prove, and show how this leads a result that is clearly false. This contradiction shows that our initial assumption must be false, and therefore its opposite true. In this way, we indirectly prove our claim is true by showing it cannot be false. In the last proof, we demonstrated if $1+1=1$ then $0=1$, which is clearly false. Therefore, we could conclude $1+1\ne 1$, which meant $1+1=0$, what we wanted to show.

Moving on, we can tackle the construction of three-element field $T=\{0,1,\omega \}$. Immediately, we write the addition and multiplication tables and fill out the simple rows and columns.

      

Completing the multiplication table is simple; since every element in the field must have a multiplicative inverse, in the case of $\omega$, this must be itself. In other words, every non-zero row or column in a field multiplication table must have a single 1.

      

This leaves the addition table to be completed, to do this we introduce a new theorem which helps complete the non-diagonal entries.

Theorem 14.

For a three-element field $(T,0,1,+,\cdot )$ with $T=\{0,1,\omega \}$ the following equation must be true.

$1+\omega$ $=0$

Proof by Contradiction.

Assume for sake of contradiction that $1+\omega \ne 0$. Then, by closure the sum must either be $\omega$ or 1. We would show either case results in a contradiction.

Case 1. $1+\omega =1$

Since 1 is in the field, the inverses property tells us that an additive inverse exists. Adding both sides with this additive inverse we immediately see the contradiction.

$1+\omega$ $=1$

$(-1)+1+\omega$ $=1+(-1)$

$\omega$ $=0$

Since the elements are distinct this is a contradiction.

Case 2. $1+\omega =\omega$

We approach this case in a very similar way, clearing the $\omega$’s from both sides to expose a contradiction.

$1+\omega$ $=\omega$

$1+\omega +(-\omega )$ $=\omega +(-\omega )$

$1$ $=0$

This again, is a contradiction. Therefore in the absence of any alternatives, we have proved that $1+\omega =0$ ∎ End of proof

Note in this proof, we applied a case-by-case approach to a proof by contradiction. This is analogous to a proof by cases where we prove the result in every case, except we actually show a contradiction in each case.

      

The remaining two spaces are rather easy to fill out if we remember the property that in a field

$\text{if }x+y=x+z\text{ then }y=z$

Fixing $x$ by focusing on an individual role or column, this tells us that different entries must be different. This is because, for example,

$\text{if }1+1=1+\omega \text{ then }1=\omega .$

Interestingly, this means every row and column of the addition table must contain each of the field elements. Exploiting the analogous rule for multiplication, every non-zero row or column must have every field element appear exactly once. Armed with this knowledge, we can finally complete the operator definitions, showing a three-element field exists.

$T=\{0,1,\omega \}$

      

1.6 Exercises

1. Prove that for two real numbers $x$ and $y$, $|x-y|\ge |x|-|y|$.

2. Given $x+2y=100$, determine the maximum value of $xy$ using the arithmetic-geometric mean inequality.

3. For real numbers $x,y,u,v,$ show that

   ${(xu+yv)}^2\le (x^2+y^2)(u^2+v^2).$

4. When does equality hold for the triangle inequality? In other words, for what values of $x$ and $y$ does

   $|x+y|=|x|+|y|\mathrm{?}$

5. Prove for any $a,b>0$ the following inequality holds true.

   ${\displaystyle \frac{4}{ab}}\le {\left({\displaystyle \frac{1}{a}}+{\displaystyle \frac{1}{b}}\right)}^2$

6. Prove the following for three real numbers $x$, $y$, and $z$.

   $|x+y+z|\le |x|+|y|+|z|$

7. Show the image of the function $f$ is the set (0, 1], for

   $f:ℝ\to ℝ,f(x)={\displaystyle \frac{1}{x^2+1}}.$

8. Let $C$ and $D$ be sets in the domain of $g$. Prove the following relationship about the images of the function.

   $g(C\cap D)\subseteq g(C)\cap g(D)$

9. Let $f$ and $g$ be two bounded functions. Which of the following functions are also bounded?

   $f+g,f\cdot g,{\displaystyle \frac{f}{g}},{\displaystyle \frac{1}{f^2+1}}$

10. If $(f-g)$ and $(f\cdot g)$ are bounded, prove that the function $(f+g)$ is bounded.

11. Consider the four element field $F=\{0,1,a,b\}$ with operations $+$ and $\cdot$. Complete the addition and multiplication tables below, if possible, and determine the number of different fields which satisfy the axioms.

          

12. For each of the statements below either provide a proof or counterexample. (1) For any $x\in S$, we have $x\cdot 0=0$, and (2) $y\cdot 1^{-1}=y^{-1}$ for any $y\ne 0$ in $S$.

Note 2 Language and Proofs

2.1 Statements and Connectives

The atomic unit of mathematical reasoning is the mathematical statement or proposition, a sentence that is either true or false. This requirement is called the principle of bivalence. For a statement, its truth value is whether it is true or false. Examples of statements are given below.

$P$ $\equiv \pi \text{ is rational}$

$Q$ $\equiv x^2+x+1\text{ has a real solution}$

$R$ $\equiv \text{July 4, 1776 was a Thursday}$

In our examples, the first statement is false while the other two are true. On the other hand “let them eat cake” is not a mathematical statement. These statements can be combined with logical connectives to express more complicated thoughts, which are listed below.

Name	Usage	Meaning
Negation	$\neg P$	not $P$
Conjunction	$P\wedge Q$	$P$ and $Q$
Disjunction	$P\vee Q$	$P$ or $Q$
Conditional	$P⟹Q$	if $P$ then $Q$
Biconditional	$P\iff Q$	$P$ if and only if $Q$

Similar to defining operators in a finite field, we provide rigorous definitions for these logical connectives by showing whether the compound statement is true of false for every possible set input. Fortunately there are very few possible inputs since each statement can either be true or false. In composing a table, called a truth table, we let each row correspond to a unique input.

Notice this truth table shows completely negation, since it tells us how the statement behaves given every input. In this case, if a statement is true its negation is false and if a statement is false its negation is true. In English, then, the negation of a statement would be its opposite. The truth tables for the remaining connective are given below; notice each require two inputs and thus have four possible inputs.

These truth tables provide complete definitions for each of these operators, but fail to provide very much intuition.

1. Negation: As mentioned before, if $R$ is true its negation is false and vice versa. The simple interpretation of this that $\neg R$ is the opposite of $R$.

   $P$ $\equiv \pi \text{ is rational}$

   $\neg P$ $\equiv \pi \text{ is not rational}$

   $Q$ $\equiv \sqrt{2}>0$

   $\neg Q$ $\equiv \sqrt{2}\le 0$

2. Conjunction: $P\wedge Q$ is true only when both $P$ and $Q$ are true, which matches with we think about “and.”

   $P$ $\equiv \sqrt{2}\text{ is irrational}$

   $Q$ $\equiv (x^2=2)\text{ holds when }x=\sqrt{2}$

   $P\wedge Q$ $\equiv \sqrt{2}\text{ is irrational and a solution to }{x}^2=2$

3. Disjunction: $P\vee Q$ is true when either $P$, $Q$, or both $P$ and $Q$ are true. Another way to think about this is that $P\vee Q$ is only false when both statements $P$ and $Q$ are both false. There is a slight difference between this logical “or” and the one in everyday usage; often times, “or” in English can mean one or the other but not both, which would be called the exclusive-or in mathematics.

   $P$ $\equiv x\text{ is positive}$

   $Q$ $\equiv x\text{ is negative}$

   $P\vee Q$ $\equiv x\text{ is positive or negative}$

   $\equiv x\text{ is nonzero}$

4. Conditional: This connective is essential in proofs, and thus is worth taking closer look at.

   The first statement is called the hypothesis and the second statement the conclusion. The statement $(P⟹Q)$, interpreted as either

   “if $P$ then $Q$” or

   “$P$ implies $Q$,”

   means when $P$ (the hypothesis) is true, $Q$ (the conclusion) must be true as well. On the other hand, when $P$ is false, it does matter whether $Q$ is true or false, and the statement is true in either case. Once again, the only time a conditional is false is when $P$ is true but $Q$ is false.

5. Biconditional: A biconditional $(P\iff Q)$ is true when both $P$ and $Q$ have the truth value and false they do not. Therefore, if the biconditional is true the statements $P$ and $Q$ are logically interchangeable since both are true or false together. For this reason, $P$ and $Q$ can be said to be “logically equivalent.” This concept can be expressed in two ways as either

   $P\iff Q\text{ or }P\equiv Q,$

   where the second notation is traditionally used to indicate the two logical compound expressions are equivalent, especially when one side might itself contain the biconditional connective.

It turns out that from these logical connective we can construct many expressions which are identical. We prove a few of the important logical equivalences.

Theorem 15 (De Morgan’s laws).

For two logical statements $R$ and $S$, the following equivalences are true.

$\neg (R\wedge S)$ $\equiv \neg R\vee \neg S$ (2.1)

$\neg (R\vee S)$ $\equiv \neg R\wedge \neg S$ (2.2)

Proof.

The general way to prove logical statements are equivalent is to construct truth tables and show both statements have identical outputs for the same inputs. In order to avoid receptiveness, we will do this for the first statement and leave the proof of the second as an exercise.

$R$	$S$	$R\wedge S$	$\neg (R\wedge S)$
T	T	T	F
T	F	F	T
F	T	F	T
F	F	F	T

This gives us the truth table for the left-hand side of the equation. We follow the same process, slow building up the right-hand side.

$R$	$S$	$\neg R$	$\neg S$	$\neg R\vee \neg S$
T	T	F	F	F
T	F	F	T	T
F	T	T	F	T
F	F	T	T	T

Since $(\neg R\vee \neg S)$ and $\neg (R\wedge S)$ are true and false together, given the same inputs (have identical columns) the two statements are logically equivalent.
∎ End of proof

Theorem 16.

The following important logical equivalences are also true.

$P\iff Q$ $\equiv (P⟹Q)\wedge (Q⟹P)$ (2.3)

$P⟹Q$ $\equiv (\neg Q⟹\neg P)$ (2.4)

$P⟹Q$ $\equiv \neg (P\wedge \neg Q)$ (2.5)

2.2 Predicates and Quantifiers

Even after the application of connectives, statements are rather limited and specific, and so to express classes of statements, predicates are used. A predicate with variables is an expression which is either true or false when its variables are supplied. Since predicates are not statements until its variables are defined, they are sometime called open statements.

$P(n)=n\text{ is even}$

Above is an example of such a predicate; although it currently is neither true nor false, as soon as $P$ is given a reasonable input its truth value is defined.

$P(0)\text{ is true}$

$P(1)\text{ is false}$

$P(2)\text{ is true}$

$\mathrm{\dots }$

Notice the truth value changes as a function of the input, though we need only consider inputs for which it is well-defined. For example, in this case, the expression $P(\pi )$ makes no sense since even and odd are not defined for real numbers.

Having introduced this machinery, we can return to DeMorgan’s laws and explain its connection to the identically named rules for sets. For two sets $A$ and $B$, consider the following statements.

$R(x)$ $\equiv x\in A$

$S(x)$ $\equiv x\in B$

From DeMorgan’s laws, we know the following logical equivalence is true.

$\neg [R(x)\wedge S(x)]$ $\equiv \neg R(x)\vee \neg S(x)$

We will translate both sides into the language of set theory.

$\neg [R(x)\wedge S(x)]$ $\equiv \neg [(x\in A)\wedge (x\in B)]$

$\equiv \neg [x\in (A\cap B)]$

$\equiv x\notin (A\cap B)$

$\equiv x\in {(A\cap B)}^c$

$\neg R(x)\vee \neg S(x)$ $\equiv \neg (x\in A)\vee \neg (x\in B)$

$\equiv x\notin A\vee x\notin B$

$\equiv x\in A^c\vee x\in B^c$

$\equiv x\in A^c\cup B^c$

$\therefore {(A\cap B)}^c=A^c\cup B^c$

Similarly, with these defined statements,

$\neg [R(x)\vee S(x)]$ $\equiv \neg R(x)\wedge \neg S(x)$

$\text{means }{(A\cup B)}^c$ $=A^c\cap B^c$

So far we have only discussed whether statements are true for individual inputs, but often times we are interested in the behavior of a predicate over a set of inputs. To do this, we introduce two quantifiers.

$\text{Universal. }\forall x\in S$ $\equiv \text{ “for all }x\text{ in }S\text{”}$

$\text{Existential. }\exists x\in S$ $\equiv \text{ “there exists an }x\text{ in }S\text{”}$

Attaching either a universal quantifier or existential quantifier to a predicate makes it a statement.

$(\forall x\in S)P(x)\equiv$ “for all $x$ in $S$,$P(x)$ is true”

$(\exists x\in S)P(x)\equiv$ “there exists an $x$ in $S$ such that

 $P(x)$ is true”

In English these quantifiers can often be disguised, but are commonly used when talking about mathematical statements. A predicate with multiple variables can have multiple quantifiers, where order matters.

$S$ $=(\forall x\in ℝ)(\exists M\in ℝ)(|x^2|\le M)$

$=\text{for all real numbers }x\text{, there exists a real }M\text{ such that }|x^2|\le M$

$T$ $=(\exists M\in ℝ)(\forall x\in ℝ)(|x^2|\le M)$

$=\text{there exists a real }M\text{ such that for all real }x\text{, }|x^2|\le M$

The first statement means that for any real input of $x^2$, we can find a $y$-value which is more extreme that it. This is trivially true since any finite input of the function is finite, take for example

$M=x^2+1.$

On the other hand, the second statements says there is some bound $M$ for which all values in the image of $f(x)=x^2$ lie between $-M$ and $M$. Note this is identical to the definition of a bounded function we discussed earlier, only written in the form of a statement. Now consider the negation of this statement. To argue a function is not bounded is to should for all bounds $M$ we can chose at least one point which exceeds this bound.

$\neg T$ $=(\forall M\in ℝ)(\exists x\in ℝ)(x^2>M)$

If we compare the definition of bounded with its negation we notice an interesting relationship, where, in addition to the predicate being negated, all universal quantifiers turn into existential ones and vice versa. This is formalized below.

Theorem 17.

When negating a quantified predicate, flip the quantifiers in addition to negating the predicate.

$\neg [(\forall x\in S)P(x)]$ $\equiv (\exists x\in S)\neg P(x)$ (2.6)

$\neg [(\exists x\in S)P(x)]$ $\equiv (\forall x\in S)\neg P(x)$ (2.7)

2.3 Proving Existential Statements

The simplest class of statements we need to prove are those with existential quantifiers; those of the form

$(\exists x\in S)P(x).$

To prove such a statement is rather straightforward and usually involves finding the $x$ for which the claim is true. For example, we can prove the following statement, which is sufficient to show the irrational numbers do not obey closure under regular addition and therefore cannot be considered a field.

Theorem 18.

There exist two irrational numbers $r$ and $s$ for which $r$ + $s$ is rational.

Proof.

Expressed as a logical statement, we are interested in the statement

$(\exists r,s\in ℝ-\mathbb{Q})(r-s\in \mathbb{Q}).$

We will prove this existentially qualified statement by fining such a pair of irrational $r$ and $s$ for which their sum is irrational. Consider now:

$\{\begin{array}{cc}r=\pi \hfill & \\ s=-\pi \hfill & \end{array}$

$r-s=\pi +(-\pi )=0$

Since we have found at least one pair of elements for which this statement is true, we have proved that the sum of two irrational numbers can be rational. ∎ End of proof

Of course, explicitly finding an example which satisfies the statement may not be as easy. Sometimes it is possible to show such an example must exist without actually finding it in a type of proof called a non-constructive proof. The most famous example of such a proof is given below.

Theorem 19.

There exist two irrational numbers $r$ and $s$ for which $r^s$ is rational.

Proof by Cases.

This proof seems nearly impossible to attempt directly. The irrational numbers are a very diverse set and a clear starting point is elusive. Instead, we attempt a non-constructive proof with a trick.

Case 1. ${\sqrt{2}}^{\sqrt{2}}$ is irrational

Notice what happens when this number is raised to the power of $\sqrt{2}$.

${\left({\sqrt{2}}^{\sqrt{2}}\right)}^{\sqrt{2}}$ $={\sqrt{2}}^{\sqrt{2}\cdot \sqrt{2}}$

$={\sqrt{2}}^2$

$=2\in \mathbb{Q}$

Therefore if ${\sqrt{2}}^{\sqrt{2}}$ is irrational, then we have found two irrational numbers for which their power is rational.

Case 2. ${\sqrt{2}}^{\sqrt{2}}$ is rational

It turns out that if this case is correct, then our proof is automatically done, since the square root of two, an irrational number, when raised to the power of itself is rational.

Ultimately, we have shown that either

${\left({\sqrt{2}}^{\sqrt{2}}\right)}^{\sqrt{2}}\text{ or }{\sqrt{2}}^{\sqrt{2}}$

must be rational and the result of raising one irrational number to the power another. Although we do not know which case is correct, one of them must be true and thus there must exist two irrational numbers who power is rational. (In case you were still curious, it turns out the first case is correct.) ∎ End of proof

We will now introduce even and odd integers and use this an an opportunity to prove statements about this property.

$\text{Even. }x\text{ is even means }x=2k\text{ for some }k\in \mathbb{Z}$

$\text{Odd. }x\text{ is odd means }x=2k+1\text{ for some }k\in \mathbb{Z}$

Notice with definition every integer is either even or odd but not both. The sets of even and odd numbers look as follows

${\mathbb{Z}}_e$ $=\{\mathrm{\dots },-4,-2,0,2,4,\mathrm{\dots }\}$

${\mathbb{Z}}_o$ $=\{\mathrm{\dots },-3,-1,1,3,5,\mathrm{\dots }\}$

where ${\mathbb{Z}}_e$ denotes the even integers and ${\mathbb{Z}}_o$ the odd integers. We will leave our discussion of parity, the property of being either even or odd, here for now.

2.4 Unary Proofs

Despite this discussion about proving existential quantifiers, we are primarily interested in proving or disproving statements with universal quantifiers. That is, we prefer more general results about all natural numbers, all integers, or all real numbers. To disprove a statement, we can prove its negation. For a universally quantified statement, these have the following forms.

$P$ $\equiv (\forall x\in S)P(x)$

$\neg P$ $\equiv (\exists x\in S)\neg P(x).$

Hence, proving such a statement false amounts to finding at least one example for which the result fails to hold. As we showed above, this can either be done explicitly or implicitly (non-constructively). In the scenario where we find such case, we call it a counterexample. Since the negation of a universal quantifier is existential, only one counterexample is needed to prove the entire claim false.

It follows that we may now want to explore techniques to help prove these statements true. Of course, we usually deal with infinite sets and it is impossible to manually verify the predicate holds for all possible inputs. However, once we realize the majority of results fall within one of three classes of statements,

$S_1$ $\equiv (\forall x\in S)P(x),$

$S_2$ $\equiv (\forall x\in S)[P(x)⟹Q(x)],\text{ and}$

$S_3$ $\equiv (\forall x\in S)[P(x)\iff Q(x)],$

we can apply the tools mathematical logic to discover more efficient methods to approach these proofs. But first, we provide examples of statements of this form statements we have already encountered.

Type	Examples
$P(x)$	for all real numbers $x$, $\sqrt{x^2}=|x|$
	for all $x,y\in ℝ$, $|x|+|y|\ge |x+y|$
	for any finite set $S$, the size of $𝒫(S)$ is $2^{|S|}$
	for any statements $S$ and $T$, $\neg (S\wedge T)\equiv \neg S\wedge \neg T$
$P(x)⟹Q(x)$	if $x=y$ and $x,y>0$ then their arithmetic mean equals their geometric mean.
	if $b^2-4ac\ge 0$ then a quadrative equation has at least one solution
	if $F$ is a field with $x,y\in F$, then $(x+y)\in F$

We first begin our examination of proof techniques with statements of the form

$(\forall x\in S)P(x).$

Notice that these statements are actually of the form

$(\forall x\in S)[H(x)⟹P(x)],$

where $H(x)$ represents many of the definitions and assumptions we take for granted. For example, in proving the triangle inequality, we assumed that the absolute value function was defined in a particular way, along with a few axioms of the real numbers. However since the hypotheses are not meaningful in the sense that they provides any significant information apart from the generally accepted rules, they are acceptable to omit. The two main methods of proving such a statement are a direct proof and a proof by contradiction. In the former,we derive the statement directly from those which are true. An example of such a proof is given below.

Theorem 20.

For any real number $x$ the following inequality is always true.

$|x|+{\displaystyle \frac{1}{|x|}}\ge 2$ (2.8)

Proof.

It turns out that this statement is rather useful, and appears frequently in other places. This statement is relatively easy to prove as well, since it appears to be a special case of the arithmetic-geometric inequality. Take:

$\{\begin{array}{cc}a=|x|\hfill & \\ b=1/|x|\hfill & \end{array}$

Since both $a$ and $b$ are greater than 0 we can apply the special case of the theorem which hold for positive numbers.

$a+b$ $\ge 2\sqrt{ab}$

$=2\sqrt{|x|\cdot 1/|x|}$

$=2$

$\therefore |x|+{\displaystyle \frac{1}{|x|}}$ $\ge 2$

∎ End of proof

While a direct proof is rather straightforward, it can difficult to see how to proceed when confronted with a statement. In this case, a proof by contradiction can be used: assume the negation of the statement and show that it must be wrong. Remember that a either a statement or its negation must be true, therefore showing the negation to be false is equivalent to proving the statement true. An example where a direct proof might be difficult is given below.

Theorem 21.

For any list of real numbers, there must be at least one value which is a large as the average. Alternatively, this can be expressed as:

$\max (x_1,x_2,\mathrm{\dots },x_n)\ge {\displaystyle \frac{x_1+x_2+\mathrm{\cdots }+x_n}{n}}$ (2.9)

Proof by Contradiction.

Attempting a direct proof seems unwise; instead, we approach this with a proof by contradiction. Assume there exist a list of real numbers for which every number is less than the average. Therefore we would have

Since we have a bound on every single term, we can find a bound on the sum.

$x_1+x_2+\mathrm{\cdots }+x_n$

$=n\left({\displaystyle \frac{x_1+\mathrm{\cdots }+x_n}{n}}\right)$

$=x_1+x_2+\mathrm{\cdots }+x_n$

At this point, we have arrive at the conclusion that the sum of the numbers is less than itself. This is a contradiction, and thus such a list cannot exist. ∎ End of proof

Notice in this case, the result we where trying to prove was actually doubly quantified. Formally, we would write

$(\forall (x_1,\mathrm{\dots },x_n)\in {ℝ}^n)(\exists x_i\in (x_1,\mathrm{\dots },x_n))[x_i\ge \mathrm{mean}(x_1,\mathrm{\dots },x_n)]\equiv$

for all lists of real numbers, there exists some element in the list for which…

In proving this statement via contradiction, we need to be careful in taking the negation, remembering to swap quantifier types. Our negation is then

$(\exists (x_1,\mathrm{\dots },x_n)\in {ℝ}^n)(\forall x_i\in (x_1,\mathrm{\dots },x_n))[x_i\ge \mathrm{mean}(x_1,\mathrm{\dots },x_n)]\equiv$

there exists some list of real numbers for which all elements are…

Notice this is precisely what we assumed during the proof, thus making it logically sound. Proofs by contradiction are also rather useful for claims of irrationality. Although rational numbers are well-defined and easy to work with, the irrationals are less so. Using a proof by contradiction would allows to work with the former class of numbers rather than the latter. An example of such a proof is below.

Theorem 22.

The square root of two $(\sqrt{2})$ is irrational.

Proof by Contradiction.

Above we used the fact that the square root of 2 was irrational, but we never proved it. We do so now using a proof by contradiction. Assume, then, that the square root of two is rational so we can write

$\sqrt{2}={\displaystyle \frac{p}{q}}$

for $p$ and $q$ in lowest terms. We emphasize this point here, that the fraction is in lowest terms, since ever rational number can be written in this way. At this point we square both sides to remove the square root.

$2={\displaystyle \frac{p^2}{q^2}}$

$⟹2q^2=p^2$

Notice that $p^2$ can be expressed as two times an integer so it must even. It follows that $p$ must also be even, since if it was odd so would its square. therefore, for some $k\in \mathbb{Z}$, we can write

$p=2k$

$2q^2={(2k)}^2$

$⟹q^2=2k^2$

This means that $q^2$ is also even and so $q$ must be as well. This however is a contradiction, since we assumed the fraction was in reduced form and therefore both the number and denominator cannot be divisible by two. ∎ End of proof

2.5 Conditional Proofs

In the last chapter, we also mentioned two other classes of statements we are likely to prove.

$S_2$ $\equiv (\forall x\in S)[P(x)⟹Q(x)]$

$S_3$ $\equiv (\forall x\in S)[P(x)\iff Q(x)]$

Despite being slightly more complex, many of the techniques we see in this section are similar to those we explored earlier. We now tackle the second class of statements of the form $P(x)⟹Q(x)$. A summary of the three techniques we will use throughout the course of the section are below.

Method	Approach	Statement
Direct	assume $P(x)$, show $Q(x)$	$P(x)⟹Q(x)$
Contrapostive	assume $\neg Q(x)$, show $\neg P(x)$	$\neg Q(x)⟹\neg P(x)$
Contradiction	assume $P(x)\wedge \neg Q(x)$, show contradiction	$\neg [P(x)\wedge \neg Q(x)]$

Once again, the most straightforward approach is to attempt a direct proof. For an example, we can prove the following theorem rather simply, assuming the hypothesis and manipulating it to arrive at the conclusion.

Theorem 23.

The sum and product of two even numbers are both even.

Proof.

We proceed with a direct proof; to help see the hypothesis and conclusion we can write this out as a logical statement.

$(\forall n,m\in \mathbb{Z})[(n,m\in {\mathbb{Z}}_e)⟹(n+m,nm\in {\mathbb{Z}}_e)]$

We’re using shorthand here where $n,m\in \mathbb{Z}$ is a more compact way of writing $n\in \mathbb{Z}$ and $m\in \mathbb{Z}$. Nonetheless, our assumptions and desired conclusion are now clear, and we can proceed. Assume $n,m$ are even so that for some $k_1,k_2\in \mathbb{Z}$:

$\{\begin{array}{cc}n=2k_1\hfill & \\ m=2k_2\hfill & \end{array}$

We will now express both the product and sum in terms of $k_1$ and $k_2$.

$n+m$ $=2k_1+2k_2$

$=2(k_1+k_2)$

$nm$ $=(2k_1)(2k_2)$

$=4k_1{k}_2$

$=2(2k_1{k}_2)$

Since the sum and product can be expressed as 2 times some integer we can conclude they are both even. For sake of completeness, we introduce a more general theorem. The proof of each of its remaining parts are very similar and left as an exercise. ∎ End of proof

Theorem 24.

For integers $n,m\in \mathbb{Z}$ the following conditions determine whether the sum or product is even or odd.

1. if $n$ is even and $m$ is even, $n+m$ is even and $nm$ is even

2. if $n$ is even and $m$ is odd, $n+m$ is odd and $nm$ is even

3. if $n$ is odd and $m$ is even, $n+m$ is odd and $nm$ is even

4. if $n$ is odd and $m$ is odd, $n+m$ is even and $nm$ is odd

This theorem can be summarized with the following two tables,

      

which are oddly reminiscent of the addition and multiplication tables in a binary field. In fact, if we constructed a field

$(F,e,o,+,\cdot )\text{ with }F=\{e,o\},$

its operations would be defined in exactly this way, with $e$ as the additive identity and $o$ the multiplicative identity. For now, we leave this connection as an unlikely coincidence, but we will revisit this after tackling modular arithmetic.

$P(x)⟹Q(x)\equiv \underset{\text{contrapositive}}{\underbrace{\neg Q(x)⟹\neg P(x)}}$

Above is one of the logical equivalences we proved earlier, the right-hand side is called is called the contrapositive or contraposition. This fundamental equivalence tells us that to prove a conditional we can instead prove the contrapositive by assuming the negation of the conclusion and deriving the negation of the hypothesis. The canonical example is the set of statements:

Original. if it rains the streets are wet

Contrapositive. if the streets are dry then it did not rain

This is useful when the negations of the hypothesis and conclusions are better defined or easier to work with. This often occurs when we have statements with “not equal to” and in claims about parity.

Theorem 25.

If the $n^2$ is even, then $n$ must be even as well. Similarly, if $n^2$ is odd, then $n$ must be odd. In other words, $n^2$ always has the same parity as $n$.

Proof by Contrapositive.

We will show the two parts of this theorem separately, and prove the first with the contrapositive. The second part is left as an exercise.

Part 1. $n^2$ is even

We can write out our statement formally, so we can see its hypothesis and conclusion more easily. This also makes it easy to see the contrapositive.

$(\forall n\in \mathbb{Z})(n^2\text{ is even }⟹n\text{ is even})$

$(\forall n\in \mathbb{Z})(n\text{ is odd }⟹n^2\text{ is odd})$

The contrapositive is substantially easier to prove; assume that $n$ is odd so that for some integer $k$, $n=2k+1$. We can then express the square in terms of $k$.

$n^2$ $={(2k+1)}^2$

$=4k^2+4k+1$

$=2(2k^2+2)+1$

Since $n^2$ can also be expressed as one more than an even number, it must also be odd. Therefore, we have proved our original statement. Notice we used this fact in the proof that the square root of two was irrational, though only casually proved it. ∎ End of proof

Theorem 26.

For any two non-negative numbers $x$ and $y$,

$\text{if }x\ne y\text{ then }{x}^2\ne y^2$

Proof.

This result means that different positive numbers must have different squares. This fact was actually essential in many of our proofs, since it means that given we are working with positive numbers, we are allowed to square root both sides of the equation without affecting the equality. In other words, knowing each positive number has a unique squares allows us to work backward and determine a number uniquely from its square. It turns out this property is not unique to the squaring function but rather applies to an entire class of functions; but for now we stick with proving this statement, or rather its contrapositive.

$(\forall x,y\in ℝ)(x^2=y^2⟹x=y)$

The proof at this point is rather straightforward, and involves simplifying the hypothesis to reach the conclusion.

$x^2$ $=y^2$

$⟹\sqrt{x^2}$ $=\sqrt{y^2}$

$⟹|x|$ $=|y|$

$⟹x$ $=y,\text{ since }x,y\ge 0$

∎ End of proof

2.6 Conditional Statements and Contradiction

The final proof technique, as outlined earlier, is a proof by contradiction. Remember the only case in which a conditional is false is when the hypothesis is true and the conclusion is false. Therefore its negation is as follows.

$\neg [P(x)⟹Q(x)]\equiv P(x)\wedge \neg Q(x)$

Once again, in a proof by contradiction the idea is to assume the negation and show a contradiction. Since we are interested in proving a conditional, we assume the hypothesis and the negation of the conclusion, showing this yields a contradiction. We use this proof technique a revisit and strengthen a theorem we presented earlier.

Theorem 27.

For any prime number $p$, the $k$th root of $p$ is irrational, where $k$ is any integer greater than 1.

Proof.

Notice that this statement can be expressed as a conditional; if $p$ is prime then

$\sqrt[k]{p}\in ℝ-\mathbb{Q},\text{ given }k\ge 2.$

Once again, proving something is irrational positively is difficult, hence it makes sense to approach this via a proof by contradiction. For sake of contradiction then, we assume the hypothesis and the negation of the conclusion, that $p$ is prime and for $k\ge 2$ the $k$th root of $p$ is rational. By definition, this means

$\sqrt[k]{p}={\displaystyle \frac{r}{s}},\text{ for }r,s\in \mathbb{Z}$

were $r$ and $s$ are co-prime integers. Proving this same theorem in the special case where both $k$ and $p$ were 2, we can guess the proof for this will likely be similar. Therefore we raise both sides of the equation to the power of $k$ and rearrange.

$p={\left({\displaystyle \frac{r}{s}}\right)}^k$

$⟹p{s}^k=r^k$

Clearly the left-hand side of this equation is divisible by $p$, so therefore $r^k$ must be as well. Since $p$ is prime, this implies that $r$ itself must be divisible by $p$. Hence, for some $n\in \mathbb{Z}$, we can write

$r=np\text{ so}$

$p{s}^k$ $=r^k$

$=n^k{p}^k$

Dividing both sides by $p$, we reach the following equality, which immediately yields the contradiction.

$s^k=n^k{p}^{k-1}$

Now the right-hand side is divisible by $p$ so this implies so is the left-hand side. But since $p$ is a prime, $p$ dividing $s^k$ means $p$ also divides $s$. But this is a contradiction, since this means that both $r$ and $s$ are divisible by $p$ and therefore the fraction

${\displaystyle \frac{r}{s}}$

was not in lowest terms after all. Therefore, we have proved what we intended to. ∎ End of proof

Notice what we proved could be interpreted as showing the polynomial with integer coefficients

$x^k-p=0$

has no rational roots. Naturally, we maybe interested in a more general questions of when polynomials have rational roots; so we now prove a more general result to this effect and see how this above theorem simply follows as a corollary.

Theorem 28 (Rational Root Theorem).

Let $p(x)$ be an arbitrary polynomial with integer coefficients, which can be written as

$p(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+\mathrm{\cdots }+a_{1}x+a_0.$

If $p$ has rational roots, meaning there exists some $x\in \mathbb{Q}$ such that $p(x)=0$, then if $x$ is expressed as

${\displaystyle \frac{p}{q}}$

in lowest terms, then $p$ must divide $a_0$, the constant term, and $q$ must divide $a_n$, the leading coefficient.

Proof.

This could be approached with a proof by contradiction, but instead we provide a direct proof. Assume that there exists a rational solution the $p(x)$ which is expressed as a fraction in lowest terms. Then we can write the evaluation of the polynomial at $x$ which should be equal to 0, by definition.

$p\left({\displaystyle \frac{p}{q}}\right)$ $=0$

$a_n{\displaystyle \frac{p^n}{q^n}}+a_{n-1}{\displaystyle \frac{p^{n-1}}{q^{n-1}}}+\mathrm{\cdots }+a_1{\displaystyle \frac{p}{q}}+a_0$ $=0$

Once again, similar to the insight we used in the previous few proofs, we want to clear the fractions so we can once again work with integers. This can easily be done by multiplying both sides of the equation with $q^n$, yielding

$a_n{p}^n+a_{n-1}{p}^{n-1}q+a_{n-2}{p}^{n-2}{q}^2+\mathrm{\cdots }+a_{1}p{q}^{n-1}+a_0{q}^n=0.$

We then rearrange this polynomial in two ways by isolating all the $p$ and all the $q$ terms, so we can factor.

$a_n{p}^n+a_{n-1}{p}^{n-1}q+a_{n-2}{p}^{n-2}{q}^2+\mathrm{\cdots }+a_{1}p{q}^{n-1}$ $=-a_0{q}^n\text{ and}$

$a_{n-1}{p}^{n-1}q+a_{n-2}{p}^{n-2}{q}^2+\mathrm{\cdots }+a_{1}p{q}^{n-1}+a_0{q}^n$ $=-a_n{p}^n$

To reach the first equation we moved the last term to the other side, and for the second equation, we moved the leading coefficient. Notice that both left-hand sides now have a common factor so we can simplify even further.

$p(a_n{p}^{n-1}+a_{n-1}{p}^{n-2}q+\mathrm{\cdots }+a_1{q}^{n-1})$ $=-a_0{q}^n\text{ and}$

$q(a_{n-1}{p}^{n-1}+\mathrm{\cdots }+a_{1}p{q}^{n-2}+a_0{q}^{n-1})$ $=-a_n{p}^n$

In the first equation, we can see that left-hand side is divisible by $p$, therefore so must the right-hand side. Notice that since

${\displaystyle \frac{p}{q}}$

was in lowest terms, $q^n$ clearly is not divisible by $p$, hence this means that $p$ divides $a_0$. By symmetry, the second equation shows that $q$ must divide $a_n$. This is exactly what we needed to show, which is that if $p(x)$ has a rational root, then

$\{\begin{array}{cc}p\text{ divides }{a}_0\hfill & \\ q\text{ divides }{a}_n.\hfill & \end{array}$

∎ End of proof

We can now offer a slicker proof to our original statement, using the theorem we just proved. Remember we wanted to prove

$\sqrt[k]{p}\in ℝ-\mathbb{Q}$

where $k$ is any integer greater than 1 and $p$ is a prime number. Above we used a long proof by contradiction to show this, but now we offer a simpler proof.

Proof.

Consider the following polynomial, for which the $k$th root of $p$ is a solution.

$x^k-p=0$

It is sufficient to show that the polynomial has no rational roots, because that implies the root of $p$ must be irrational. Notice that this is a polynomial with rational roots, hence we can apply the rational roots theorem to conclude that if

$x={\displaystyle \frac{m}{n}}\text{ for }m,n\in \mathbb{Z}\text{ and }n\ne 0$

is a rational root of the polynomial then $n$ must divide 1, the leading coefficient, and $m$ must divide $p$, the constant term. There the set of all possible rational roots to this polynomial is

$n\in \{1,-1\},m\in \{-p,-1,1,p\}$

$\therefore x\in \{-p,-1,1,p\}$

At this point, we simply try all possibilities to conclude no such rational $x$ can exist.

$1^k-p$ $\ne 0$

${(-1)}^k-p$ $\ne 0$

$p^k-p$ $\ne 0$

${(-p)}^k-p$ $\ne 0$

Notice this is technically a proof by contradiction; we assume that a rational root exists, then use the rational roots theorem to that this root must then be one of

$\{-p,-1,1,p\}.$

Showing that none of these are actually roots results in a contradiction, proving our original statement. ∎ End of proof

In some sense, the rational roots theorem we proved was a more general result than showing

$f(x)=x^k-p$

has no rational roots. Proving the harder general case allowed us to revisit our original problem and more easily show it was true. In this case it simply amounted to evaluating the polynomial at four points.

We will revisit this technique of proving more general results and then looking back to apply these to more specific cases later. In the next chapter, we will see cases where this may be necessary; but finding more general principles is a virtue in itself. It turns out that the rational roots theorem, once again, is a specific case of Gauss’ Lemma, but this remains out of scope of this set of notes.

Note 3 Mathematical Induction

3.1 Sum and Product Notation

In the last note, we ended up working with polynomials with an arbitrary number of terms, relying on the following notation.

$p(x)=\underset{n-1\text{ terms}}{\underbrace{a_n{x}^n+a_{n-1}{x}^{n-1}+\mathrm{\cdots }+a_{1}x+a_0}}$

While this was perfectly rigorous, it relies on the reader being able to notice the pattern among terms in the summation. It may be less ambiguous to explicitly state this pattern, for which we introduce the following notation.

${\displaystyle \sum _{i=a}^b}f(i)$ $=f(a)+f(a+1)+\mathrm{\cdots }+f(b-1)+f(b)$

${\displaystyle \prod _{i=a}^b}f(i)$ $=f(a)f(a+1)\mathrm{\dots }f(b-1)f(b)$

Using this notation, we would express a generic $n$ degree polynomial with coefficients $\{a_n\mathrm{\dots }{a}_0\}$ as the following.

$p(x)$ $=a_n{x}^n+a_{n-1}{x}^{n-1}+\mathrm{\cdots }+a_{1}x+a_0$

$={\displaystyle \sum _{i=0}^n}{a}_i{x}^i$

Notice that both of these are common computational processes in computer science which can be expressed as with the following pseudo-code.

⬇

def sum(f, a, b):

sum = 0

for i in [a, ..., b]:

sum = sum + f(i)

return sum

def prod(f, a, b):

prod = 1

for i in [a, ..., b]:

prod = prod * f(i)

return prod

The following properties of summation and product naturally extend from its definition, and should intuitively be true, though writing out a proof should not be too difficult.

${\displaystyle \sum _{i=a}^b}cf(i)$ $=c{\displaystyle \sum _{i=a}^b}f(n)$

${\displaystyle \sum _{i=a}^b}(f(i)+c)$ $=\underset{\text{number of terms}}{\underbrace{(b-a+1)}}c+{\displaystyle \sum _{i=a}^b}f(n)$

There is an analogous equivalence for a product, though this time the number we we pull out get raised to the power of the number of terms.

${\displaystyle \prod _{i=a}^b}cf(i)$ $=c^{b-a+1}{\displaystyle \prod _{i=a}^b}f(n)$

These summations (and products) appear frequently in mathematics, especially in calculus where the number of terms goes to infinity, so over the course of this chapter, we help develop tools to help simplify then more useful formula. As an example, consider the sum of the first $n$ natural numbers.

Theorem 29.

For all natural numbers $n$, the following equation holds.

${\displaystyle \sum _{i=1}^n}i$ $=1+2+\mathrm{\cdots }+n$

$={\displaystyle \frac{n(n+1)}{2}}$

Proof.

We offer a direct proof of this fact using a trick; first denote the sum itself as $S$, so we have the expression

$S=1+2+3+\mathrm{\cdots }+(n-1)+n.$

Now we sum the sequence the with itself in reverse order, in essence adding two equations.

Notice in the bottom sum, each of the $n$ terms is $(n+1)$. Therefore we can simplify the expression even further to get

$2S=n(n+1)\text{ or}$ (3.1)

$S={\displaystyle \frac{n(n+1)}{2}}$ (3.2)

This is exactly what we need to show, hence we have derived the formula. ∎ End of proof

Notice the simplified expression is more useful to us, since it more clearly expresses the relationship between $n$ and the sum. More specifically, from this formula we can tell that the sum is actually a well-defined polynomial in $n$, a fact which is obfuscated by the summation. However in the above proof we used a trick, and it is not clear how we would approach proving formulae like this more generally.

3.2 The Naturals Numbers

While most of our proofs until how have been focused on the real numbers and integers, we now turn our attention to the natural numbers. To develop another fundamental proof technique for working with these numbers, we need a more precise definition of the natural numbers, which we currently refer to with the set

$\mathbb{N}=\{1,2,3,\mathrm{\dots }\}.$

To avoid the ambiguity of the ellipses, we can define the natural numbers ($\mathbb{N}$) as the intersection of all subsets $A$ of the real numbers with the following properties

1. $1\in A$

2. if $n\in A$, then $s(n)\in A$ where $s$ is the successor function which represents $s(n)=n+1$.

Notice this is consistent with our intuitive definition of the natural numbers. If $A$ obeys these two definitions, then we know 1 must be in $A$, along with all number in the sequence $1,2,3,\mathrm{\dots }$

$\{1,2,3,\mathrm{\dots }\}\subseteq A$

Furthermore, since this set itself satisfies these conditions, we know that it is an example of one such set $A$. Therefore the intersection of all such sets is indeed what we expected,

$\mathbb{N}=\{1,2,3,\mathrm{\dots }\}.$

Taking the intersection of all such sets $A$ is essentially equivalent to taking the “smallest” set which satisfies these properties; otherwise, notice that the real numbers themselves also satisfy both properties. With this definition, we have a more systematic way to understand the natural numbers which yields a new proof technique.

Theorem 30 (Principle of Induction).

Let $P(n)$ be a predicate defined for natural numbers $n\in \mathbb{N}$. If the following two statements hold,

1. $P(1)$ is true

2. if $P(k)$ is true, then $P(k+1)$ is true

then $P(n)$ is true for all natural numbers $n\in \mathbb{N}$.

Proof.

We consider the set $A$ for which this predicate is true and show that this is equal to the set of natural numbers.

$A=\{n:P(n)\text{ is true}\}$

First notice that since $P(n)$ is defined for natural numbers only, hence immediately we know $A\subseteq \mathbb{N}$. Now we know that

1. $1\in A$ because $P(1)$ is true, and

2. if $P(k)$ is true, then $P(k+1)$ is true, so if $k\in A$ then $(k+1)\in A$.

Therefore we have shown that $A$ is one of the sets used in the above definition. Since $\mathbb{N}$ is the intersection of all possible such sets, we know that it must be contained in $S$ so that

$\mathbb{N}\subseteq A$

Since we have showed $A$ is both a subset and a superset of $\mathbb{N}$, this means $A=\mathbb{N}$. Since $A$ represents the set of number for which $P(n)$ is true, this means $P(n)$ is true for all natural numbers $n$. ∎ End of proof

This means that we now have a proof technique which can be applied to proving statements which are true for over the natural numbers, namely by showing that the statements holds for $n=1$ and that for all $k$, if $P(k)$ is true then it implies $P(k+1)$. This can be precisely expressed with the following logical equivalence, which conveys the same idea.

$(\forall n\in \mathbb{N})P(n)\equiv P(1)\wedge (\forall k\in \mathbb{N})[P(k)⟹P(k+1)]$

3.3 Inductive Proofs

Through the above manipulation, we have discovered a fundamentally different way to prove universally quantified statements, specifically those which are true over the natural numbers, by exploiting the definition of the natural numbers. The logical equivalence

$(\forall n\in \mathbb{N})P(n)\equiv P(1)\wedge (\forall k\in \mathbb{N})[P(k)⟹P(k+1)],$

shows exactly what is required, but we can unwrap this. Proving some statement $(\forall n\in \mathbb{N})P(n)$ using this tool is called a proof by induction. Since the right-hand side of the expression is a conjunction, we need to show both sides are true, meaning a proof by induction has two separate parts.

1. Base Case. Show $P(1)$ is true.

2. Induction Step. Assume $P(k)$ is true for any natural number $k$, and use this to show $P(k+1)$ must be true.

The validity of this proof technique follows directly from the principle of mathematical induction. We can use this the approach the problem of proving equalities like the following systematically.

${\displaystyle \sum _{i=1}^n}i={\displaystyle \frac{n(n+1)}{2}}$

First, let us define the statement we are trying to prove more explicitly. If we denote the above expression with the predicate $P(n)$, we want to show that if the free variable $n$ is a natural number, then the statement is true, or

$(\forall n\in \mathbb{N})P(n).$

Proof.

Since we have a statement we wish to prove the over the natural numbers, we use a proof by induction. This involves showing the base case and then the induction step.

1. Base Case. We want to show $P(1)$ is true, which is easy to show.

   ${\displaystyle \sum _{i=1}^1}i=1={\displaystyle \frac{1(1+1)}{2}}$

2. Induction Step. Assume $P(k)$ is true for some natural number $k$ so that we have

   $1+2+\mathrm{\cdots }+k={\displaystyle \frac{k(k+1)}{2}}.$

   We want to show that the statement $P(k+1)$ must follow; which written out corresponds to

   $1+2+\mathrm{\cdots }+(k+1)={\displaystyle \frac{(k+1)(k+2)}{2}}.$

   Notice the similarity in structure on the right-hand side of both equations, which suggests a obvious substitution. We prove $P(k+1)$ by starting with the right-hand side and deriving the left-hand side.

   $1+2+\mathrm{\cdots }+(k+1)$ $=\underset{\text{left-hand side of }P(k)}{\underbrace{1+2+\mathrm{\cdots }+k}}+(k+1)$

   $={\displaystyle \frac{k(k+1)}{2}}+(k+1)$

   $={\displaystyle \frac{k(k+1)}{2}}+{\displaystyle \frac{2(k+1)}{2}}$

   $={\displaystyle \frac{(k+1)(k+2)}{2}}$

   We are allowed to make the substitution in the second line, because we assumed this about the sum of the first $k$ natural numbers. We use this assumption to extend what we know to conclude the same thing about the first $(k+1)$ natural numbers. Therefore, this concludes the proof; we have shown that $P(n)$ is true for all natural numbers $n$.

∎ End of proof

At this point, we should point out that never do we assume what we are trying to prove. Instead, in the induction step we assume $P(k)$ is true for one particular value of $k$ and show $P(k+1)$. This assumption, that $P(k)$ is true, referred to as the induction hypothesis in the inductive step. Our first inductive proof was rather verbose, but we now offer a more streamlined example to prove something similar.

Theorem 31.

For all non-negative integers $n$, the summation formulas below have the following closed form solutions.

1. ${\displaystyle \sum _{i=1}^k}{i}^2$ $={\displaystyle \frac{k(k+1)(2k+1)}{6}}$ (3.3)

2. ${\displaystyle \sum _{i=1}^k}{i}^2$ $={\displaystyle \frac{k^2{(k+1)}^2}{4}}$ (3.4)

Proof.

We only prove the first statement by induction; the proof for the second statement is very similar.

1. Base Case. We want to confirm the statement is true for $n=1$.

   ${\displaystyle \sum _{i=1}^1}{i}^2=1={\displaystyle \frac{1(1+1)(2+1)}{6}}$

2. Induction Step. Assume that the statement is true for some arbitrary number $k$, so that

   ${\displaystyle \sum _{i=1}^k}{i}^2$ $={\displaystyle \frac{k(k+1)(2k+1)}{6}}.$

   We want to show that the statement is also true for $(k+1)$. To show this, we write out the sum of the first $(k+1)$ squares and then use the induction to simplify.

   ${\displaystyle \sum _{i=1}^{k+1}}i$ $=\underset{\text{induction hypothesis}}{\underbrace{1^2+2^2+\mathrm{\cdots }+k^2}}+{(k+1)}^2$

   $={\displaystyle \frac{k(k+1)(2k+1)}{6}}+{(k+1)}^2$

   $={\displaystyle \frac{(k+1)(k+2)(2k+3)}{6}}$

   This is exactly what we needed to show, hence this concludes the proof by induction.

∎ End of proof

3.4 Sequences and Recurrences

In some sense, induction treats the natural numbers as an ordered list of elements, starting with 1 and increasing in the order we write them out.

$\mathbb{N}=\{1,2,3,\mathrm{\dots }\}$

A natural generalization of this idea is to consider ordered lists of items with arbitrary elements, a notion we denote a sequence, which can be represented as

$⟨a⟩=a_1,a_2,a_3,\mathrm{\dots }$

The subscript represents the term number, which gives the position of a particular element, or term, in the sequence. More formally a sequence is defined as a function from the natural numbers, which maps term numbers to terms.

Since the natural numbers are ordered, constructing this function ties the order of the natural numbers to those of the terms in the sequence, imposing an order. Two kinds of sequences that appear frequently in mathematics are arithmetic sequences and geometric sequences. The former is a sequence such that that the difference between consecutive terms is constant while the later is a sequence in which consecutive terms have the same ratio.

$\text{Arithmetic. }a,a+d,a+2d,a+3d,a+4d,\mathrm{\dots }$

$\text{Geometric. }a,ar,a{r}^2,a{r}^3,a{r}^4,\mathrm{\dots }$

In the above sequences, we can specify an arithmetic sequence completely by its first term $a$ and the common difference $d$. Meanwhile, for a geometric sequence, the first term $a$ is needed along with the common ratio $r$. By inspection, we can see that the $n$th term of an arithmetic sequence is

$a_n=a+(n-1)d,$

while for a geometric sequence, we simply multiply the ratio to the first term $(n-1)$ times, giving the formula

$b_n=a{r}^{n-1}.$

Given the similarity in structure of sequences to the natural numbers, induction provides a natural way to prove things about these sequences. Consider the following theorem about the sum of first $n$ terms of arithmetic and geometric sequences.

Theorem 32.

Consider the arithmetic sequence $⟨a⟩$ and the geometric sequence $⟨b⟩$, with the following terms

$a_i$ $=a+(i-1)d$

$b_i$ $=a{r}^{i-1}$

The sum of the first $n$ terms of each sequence have the following formula, given $r\ne 1$.

${\displaystyle \sum _{i=1}^n}{a}_i$ $=a+(a+d)+(a+2d)+\mathrm{\cdots }+(a+(n-1)d)$ (3.5)

$={\displaystyle \frac{n}{2}}\left(2a+(n-1)d\right)$ (3.6)

${\displaystyle \sum _{i=1}^n}{b}_i$ $=a+ar+a{r}^2+\mathrm{\cdots }+a{r}^{n-1}$ (3.7)

$=a{\displaystyle \frac{r^n-1}{r-1}}$ (3.8)

Proof.

We prove both statements in order, using induction, starting with the sum of an arithmetic sequence.

1. Base Case. This is for $n=1$, because we are simply summing a sequence with 1 term.

   ${\displaystyle \sum _{i=1}^n}{a}_i=a={\displaystyle \frac{1}{2}}(2a+(1-1)d)$

2. Induction Step. Assume this statement is true for the sum of the first $k$ terms of an arithmetic sequence. We show that also holds for the first $(k+1)$ terms.

   ${\displaystyle \sum _{i=1}^{k+1}}{a}_i$ $=a_{k+1}+{\displaystyle \sum _{i=1}^k}{a}_i$

   $=a_{k+1}+{\displaystyle \frac{k}{2}}\left(2a+(k-1)d\right)$

   $=(a+kd)+{\displaystyle \frac{k}{2}}\left(2a+(k-1)d\right)$

   $={\displaystyle \frac{k}{2}}\left({\displaystyle \frac{2a}{k}}+2d\right)+{\displaystyle \frac{k}{2}}\left(2a+(k-1)d\right)$

   $={\displaystyle \frac{k}{2}}\left[2a{\displaystyle \frac{k+1}{k}}+(k+1)d\right]$

   $={\displaystyle \frac{k+1}{2}}\left(2a+kd\right)$

This proves the formula for the sum for the first $n$ terms of an arithmetic sequence; we now approach a similar proof for the sum of the first $n$ terms of a geometric sequence.

1. Base Case. Once again, this is trivial for $n=1$ since that involves summing a one-term sequence.

   ${\displaystyle \sum _{i=1}^n}{b}_i=a=a{\displaystyle \frac{r^1-1}{r-1}}$

2. Induction Step. Assume this statement is true for the sum of the first $k$ terms. We show that also holds for the first $(k+1)$ terms.

   ${\displaystyle \sum _{i=1}^{k+1}}{b}_i$ $=b_{k+1}+{\displaystyle \sum _{i=1}^k}{a}_i$

   $=b_{k+1}+a{\displaystyle \frac{r^k-1}{r-1}}$

   $=a{r}^k+a{\displaystyle \frac{r^k-1}{r-1}}$

   $=a{\displaystyle \frac{r^k(r-1)}{r-1}}+a{\displaystyle \frac{r^k-1}{r-1}}$

   $=a{\displaystyle \frac{r^k(r-1)+r^k-1}{r-1}}$

   $=a{\displaystyle \frac{r^{k+1}-1}{r-1}}$

∎ End of proof

Notice that the algebra involved in these proofs were much messier that for those we dealt with before, yet we forged ahead. One benefit of induction is that that if the statement is true, then the algebra will almost certainly work out, so we know how exactly to simply the expression. Now consider a different kind of sequence.

Theorem 33.

If we define a sequence $⟨a⟩$ recursively, so that

then, for all natural numbers $n$, this sequence is equivalent to the polynomial

$a_n={\displaystyle \frac{n(n+1)}{2}}.$ (3.9)

Proof.

We provide an informal proof of this statement, based on our previous result; a more thorough proof would simplify formalize this with induction. Consider $a_n$ for some arbitrary $n$, we begin simplifying the expression using the second rule.

$a_n$ $=a_{n-1}+n$

$=a_{n-2}+(n-1)+n$

$=a_{n-3}+(n-2)+(n-1)+n$

$=a_1+2+\mathrm{\cdots }+(n-2)+(n-1)+n$

$=1+2+\mathrm{\cdots }+(n-1)+n$

$={\displaystyle \frac{n(n+1)}{2}}$

Notice there is however, one additional case we need to check now, which is when $n=1$, but clearly the formula trivially holds here. ∎ End of proof

The sequence we encountered above is rather different from those which we previously encountered. Such a sequence is by a recurrence relation is characterized by two features:

1. Base cases. Explicit values of the sequence for a small number of terms. In this case, by definition, $a_1=1$.

2. Recursive definition. A relationship between the value of the sequence $a_n$ to other values, typically smaller. In the above example, for non-base cases, we were given

   $a_n=a_{n-1}+n.$

While this type of recurrence equation describes a perfectly well-defined sequence, a more explicit definition of each term is often desirable. This explicit formula is called closed-form solution of the recurrence, which usually relates $a_n$ directly to $n$, rather than other terms. However the recursive definition is sometimess cleaner; we can convey the essence of an arithmetic and geometric sequence with the following recurrence relations.

The closed forms of these are the term expression we began with, which are

$a_n$ $=a+(n-1)d$

$b_n$ $=a{r}^{n-1}$

3.5 Extending Induction

So far the power of induction seems rather limited since it applies to only statements of a very particular form, namely statements which are true over the natural numbers. However it turns out that induction can can applied to prove statements which are true over an entire class of sets, including for all non-negative integers, or all even numbers, or all odd numbers, which is explained with the following theorem.

Theorem 34.

Suppose we want to prove some predicate $P(n)$ for all $n\in A$, where $A$ is some set which can be expressed as

$A=\{a_1,a_2,a_3,\mathrm{\dots }\}.$

A more precise condition is that $A$ be countable, but we return to this notion in a later chapter. Then it is sufficient to show

1. Base Case. $P(a_1)$ is true.

2. Induction Step. if $P(a_k)$ is true for any natural number $k$, then $P(a_{k+1})$ must be true

Proof.

We prove this by reduction, showing that this technique is exactly identical to induction. First consider defining the following new predicate which is related to $P(n)$.

$Q(n)\equiv P(a_n)$

First notice that the elements of $A$ are indexed by $n$, so to prove $P(a_n)$ for all $a_n\in A$ is equivalent to proving $Q(n)$ for all $n\in \mathbb{N}$. At this point, we notice that we can apply induction on $n$ to prove $Q(n)$ for all natural numbers, which entails showing the following two things.

1. Base Case. $Q(1)$ is true.

2. Induction Step. if $Q(k)$ is true for any natural number $k$, then $Q(k+1)$ must be true

Now if we show these both hold, then this proves $Q(n)$ over the natural numbers, which is equivalent to showing $P(a)$ is true for all $a$ in $A$. All that is left is to translate these conditions back into terms of $P$.

1. Base Case. $P(a_1)$ is true.

2. Induction Step. if $P(a_k)$ is true for any natural number $k$, then $P(a_{k+1})$ must be true

∎ End of proof

This shows that to prove some predicate over a set which can be expressed as an ordered list, we can: (1) show that it is true for the first element, and (2) that if it is true for some element, it is true for the next element.

$\begin{array}{c}P(a_1)\text{ is true}\hfill \\ P(a_1)⟹P(a_2)⟹P(a_3)⟹P(a_4)⟹\mathrm{\dots }\hfill \\ \\ P(a_n)\text{ is true for all }n\in A\hfill \end{array}$

This suggests the common “domino” analogy for understanding induction. To prove that that a line of dominoes have fallen down, it is sufficient to show that the first one had fallen down and that if a domino has been knocked down, it causes the next one to fall.

With this theorem, we can introduce some common patterns used in induction proofs to prove statements over different sets, and armed with these we can revisit and generalize some of our past results.

Set	Base Case	Induction Step
$\mathbb{N}=\{1,2,3,\mathrm{\dots }\}$	$P(1)$	$P(k)⟹P(k+1)$
${\mathbb{N}}_0=\{0,1,2,\mathrm{\dots }\}$	$P(0)$	$P(k)⟹P(k+1)$
$\{0,2,4,\mathrm{\dots }\}$	$P(2)$	$P(k)⟹P(k+2)$
$\{1,3,5,\mathrm{\dots }\}$	$P(1)$	$P(k)⟹P(k+2)$
$\{2^0,2^1,2^2,\mathrm{\dots }\}$	$P(1)$	$P(k)⟹P(2k)$
$\{a,a+d,a+2d,\mathrm{\dots }\}$	$P(a)$	$P(k)⟹P(k+d)$

So, for example, to prove a statement is true for all odd natural number, we first show that it is true for 1, and that if it true for some odd integer $k$ it is also true for $k+2$. This is a direct application of the theorem we proved where we define

$a_k=2k-1,\text{ so }A=\{1,3,5,\mathrm{\dots }\}$

Now, with this technique, we can extend many of the inequalities we showed previously, and solve a more general recurrence.

Theorem 35 (Generalized Triangle Inequality).

For any number of real numbers $n\ge 2$, the absolute value of their sum is bounded by the sum of their absolute values.

$|a_1+a_2+\mathrm{\cdots }+a_n|\le |a_1|+|a_2|+\mathrm{\cdots }+|a_n|$

Proof.

We apply a proof by induction on $n$ over the set of natural numbers greater than 1. Our base case should then be $n=2$.

1. Base Case. In the case where $n=2$, this reduces into the triangle inequality we proved previously.

   $|a_1+a_2|\le |a_1|+|a_2|$

2. Induction Step. Assume that this generalized triangle inequality holds for $k$ numbers, so that

   $|a_1+a_2+\mathrm{\cdots }+a_k|\le |a_1|+|a_2|+\mathrm{\cdots }+|a_k|.$

   We will now show that this also holds for $k+1$ numbers; consider the absolute value of their sum.

   $|a_1+\mathrm{\cdots }+a_k+a_{k+1}|$ $=|(a_1+\mathrm{\cdots }+a_k)+a_{k+1}|$

   $\le |a_1+\mathrm{\cdots }+a_k|+|a_{k+1}|$

   $\le |a_1|+|a_2|+\mathrm{\cdots }+|a_k|+|a_{k+1}|$

   In the last step, we make the substitution from the induction hypothesis, which complete the inductive step and thus the proof.

∎ End of proof

We can now approach more general solutions recurrence relations as well. A sequence of the form

is called a first-order linear recurrence relation, which is a well-defined sequence, given the base case $x_n$ is defined. The “first-order” refers to the fact that $x_n$ refers only to one previous term, and the “linear” comes from the fact that $x_n$ is a linear function of $x_{n-1}$, plus some constant.

Theorem 36 (First-Order Linear Recurrences).

The solution to a first-order linear recurrence relation defined as

has closed-form solution

$x_n=a^{n-1}{x}_1+b{\displaystyle \frac{a^{n-1}-1}{a-1}},$ $a\ne 1$

$x_n=x_1+(n-1)b,$ $a=1$

Proof.

Unsurprisingly, we are going to prove this by induction in a long and messy proof. However, we actually have two cases to consider, one where $a$ is 1 and one where it is not. We will first prove the more general of the two results, which is when $a\ne 1$.

1. Base Case. This is easy to check, since it only involves the first erm, which we are given.

   $x_1=a^0{x}_1+b{\displaystyle \frac{a^0-1}{a-1}}$

2. Induction Step. Assume that the closed form is correct for the $k$th term so that

   $x_k=a^{k-1}{x}_1+b{\displaystyle \frac{a^{k-1}-1}{a-1}}$

   Now we show the formula also holds for the next term, namely for the $(k+1)$th term. Do this this, we apply the recursive definition of this term.

   $x_{k+1}$ $=a{x}_k+b$

   $=a\left(a^{k-1}{x}_1+b{\displaystyle \frac{a^{k-1}-1}{a-1}}\right)+b$

   $=a^k{x}_1+ab{\displaystyle \frac{a^{k-1}-1}{a-1}}+b$

   $=a^k{x}_1+b\left(a{\displaystyle \frac{a^{k-1}-1}{a-1}}+1\right)$

   $=a^k{x}_1+b\left({\displaystyle \frac{a^k-a}{a-1}}+{\displaystyle \frac{a-1}{a-1}}\right)$

   $=a^k{x}_1+b{\displaystyle \frac{a^k-1}{a-1}}$

Now, unfortunately, we still have to deal with the case of $a=1$ separately. In this case, however, this recurrence is easier to work with.

1. Base Case. Once again, it is easy to verify the closed-form solution works for just one term.

   $x_1=x_1+(1-1)b$

2. Induction Step. Assume the formula holds for the $k$th term, and show that it also hold for the term after that.

   $x_{k+1}$ $=x_k+d$

   $=x_1+(k-1)d+d$

   $=x_1+kd$

∎ End of proof

Notice that this immediately proves the equivalence of the recurrence relation definition of arithmetic and geometric sequences to the one we originally used. If we take $a=1$, then we get

$\text{then }{x}_n=x_1+(n-1)d$

which refers to arithmetic sequences, while if we take $b=0$ then we find

$\text{then }{x}_n=x_1{a}^{n-1}$

which corresponds exactly to geometric sequences. Of course, it may seem odd that we need a separate case at all to account for when $a=1$, but it turns out, in some sense, the general formula still holds. Rather than being thrown off guard by noticing the $(a-1)$ in the denominator, we can instead take the limit as $a$ tends to 1.

$\underset{a\to 1}{lim}{x}_n$ $=\underset{a\to 1}{lim}\left(a^{n-1}{x}_1+b{\displaystyle \frac{a^{n-1}-1}{a-1}}\right)$

$=x_1\underset{a\to 1}{lim}{a}^{n-1}+b\underset{a\to 1}{lim}{\displaystyle \frac{a^{n-1}-1}{a-1}}$

$=x_1+(n-1)b$

The first limit should be easy to see; the second one is the difference quotient representing derivative of the function

$f(a)=a^{n-1}$

at $a=1$. This is out of the scope of this chapter, but it goes to show that this closed-form solution is not as disjoint as it may appear to be.

3.6 Strong Induction

The power of induction is that it allow use to make stronger assumptions in the process of proving our statement. Instead of proving the statement directly for any arbitrary element $n\in \mathbb{N}$, in the induction step, we assume $P(k)$ is true for some natural number $k$ and simply have to prove $P(k+1)$ to be true. This advantage comes from knowing something about the structure of the natural numbers themselves.

However, it turns out that we are allowed to assume something even stronger during the induction step.

Theorem 37 (Principle of Strong Induction).

Let $P(n)$ be a predicate defined for natural numbers $n\in \mathbb{N}$. If the following two statements hold,

1. $P(1)$ is true

2. if $P(1),P(2),\mathrm{\dots },P(k)$ are true, then $P(k+1)$ is true

then $P(n)$ is true for all natural numbers $n\in \mathbb{N}$.

Proof.

We prove this by showing that this is essential equivalent to the principle of induction. First, we define the following predicate

$Q(n)\equiv P(1)\wedge P(2)\wedge \mathrm{\cdots }\wedge P(n)$

so that $Q(n)$ is true if and only if $P(i)$ is true for all $i$ up to $n$. Notice showing $P(n)$ is true for all $n\in \mathbb{N}$ is equivalent to showing $Q(n)$ is true for all natural numbers. Remember the principle of mathematical induction tell us to show this predicate is true, all we need is to show is the following.

1. $Q(1)$ is true

2. if $Q(k)$ is true, then $Q(k+1)$ is true

Therefore, if we show these two statements hold, then $P(n)$ must be true as well. First consider the first statement; by definition, $Q(1)$ is the same as $P(1)$. Next, we consider the implication, which we express in terms of $P$.

$Q(k)$ $⟹Q(k+1)$

$P(1)\wedge \mathrm{\cdots }\wedge P(k)$ $⟹\underset{\text{redundant}}{\underbrace{P(1)\wedge \mathrm{\cdots }\wedge P(k)}}\wedge P(k+1)$

$P(1)\wedge \mathrm{\cdots }\wedge P(k)$ $⟹P(k+1)$

Therefore, we have shown to prove $Q(n)$ is true far all natural numbers $n$, and thus $P(n)$ is true, we can show

1. $P(1)$ is true, and

2. if $P(1),P(2),\mathrm{\dots },P(k)$ are true, then $P(k+1)$ is true.

∎ End of proof

This allows us to augment the amount of information we get for “free” during the induction step, which allows us to prove statements that we otherwise might not be able to. While this unlocks the door to more complicated recurrence relations, we can also re-visit a fact about the natural numbers we have been relying on without proof.

Theorem 38 (Prime Factorization).

Any natural number $n$ can be expressed as a, possibly empty, product of primes; meaning

$n={\displaystyle \prod _i}{p}_i^{{\alpha }_i}$

for some set of primes $\{p_i\}$ and corresponding powers $\{{\alpha }_i\}$. By convention, we say that the empty product is 1. In other words, every natural number has a prime factorization.

Proof.

We can prove this by strong induction on $n$, with a base case of $n=1$.

1. Base case. As explained, the empty product is taken to be 1 so 1 is trivially the product of primes, namely none at all.

2. Induction Step. Assume that this holds for all numbers less than or equal to some $k$. We now prove this for $(k+1)$ by casework. Now by definition, every number greater than or equal to 2 is either prime or composite. If $(k+1)$, then we are immediately done since we take

   $k+1=\underset{\text{prime}}{\underbrace{{(k+1)}^1}}$

   Otherwise, it it composite, which means by definition, it can be written as the product of two numbers less than itself, since it has a divisor that is not equal to 1 or itself. Therefore,

   $k+1=a\cdot b,\text{ for some }a,b\le k.$

   By our induction hypothesis, we know both $a$ and $b$ can be expressed as a product of primes. Since $(k+1)$ is the product of these, it can clearly also be expressed as a product of primes.

∎ End of proof

It turns out, as you probably already know, that something even stronger is true–that every natural number has a unique prime factorization. This is a theorem called the fundamental theorem of arithmetic, which is currently outside of our grasp, but which we will prove later. As we will see, what we proved just now is an important building block in the proof of the fundamental theorem. A proof that follows a similar pattern, and is also foundational to computers today, is the following.

Theorem 39.

Every non-negative integer can be expressed in binary so that it is a sum of distinct powers of 2. In other words, there exists a subset of the non-negative integer $B\in {\mathbb{N}}_0$ such that

$n={\displaystyle \sum _{i\in B}}{2}^i$

Once again, we use the convention that the empty sum is 0, which allows us to include 0 in this theorem.

Proof.

We will once again use strong induction.

1. Base case. Once again, we trivially take $B=\{\}$ represent 0. The reason this convention makes sense is because we do the same in the decimal numbers system; while we can express

   $15=1\times {10}^1+5\times {10}^0,$

   we can only express 0 by letting all the coefficients of powers of ten be 0. The same reasoning motivates our choice here.

2. Induction step. Assume that all non-negative numbers less than or equal to $k$ can be expressed as the sum of distinct powers of 2. We will now show the same holds for $(k+1)$. Now we have two cases to consider, one where this number is even and one where this is odd. In the former we can write

   $k+1$ $=2m,m\in {\mathbb{N}}_0$

   Since $m$ must be strictly less than $(k+1)$, from the induction hypothesis, we know that it can be expressed as a sum of distinct powers of two. Clearly, when we multiply each of these by two (raising their exponents by one), we find a new representation. The second case to consider is when

   $k+1=k+2^0$

   is odd. This means that $k$ is even and by the induction hypothesis can be represented as a sum of unique powers of 2. Since it is even, this sum cannot include $2^0$, which means we simply add this to find the desired representation.

∎ End of proof

Having shown some unique applications of this proof technique, we return, as promised, to more complicated recurrence relations. In particular, we can now prove closed form representations for recurrences beyond first order, in which each term is a function of more than just the previous term. In the extreme case, we could have a sequence for which each term is defined in terms of all its predecessors.

However, more often, we run into cases where each term is a function of two, three or some other finite number of terms. A famous such sequence is the Fibonacci sequence,

in which the first two terms are 1 and each term after this is the sum of the previous two. The first few terms of this sequence are

$⟨F⟩=1,1,2,3,5,8,13,21,35,56,91,\mathrm{\dots }$

It turns out that there indeed is a closed-form solution to the Fibonacci sequence, albeit one which seems far from intuitive, which we will show below

Theorem 40.

The closed form of the Fibonacci sequence is given by the exact formula,

$F_n={\displaystyle \frac{1}{\sqrt{5}}}\left({\phi }^n-{\psi }^n\right)$

where $\phi$ and $\psi$ are the two roots of the quadratic $x^2-x-1$, or explicitly

$\phi ={\displaystyle \frac{1+\sqrt{5}}{2}},\psi ={\displaystyle \frac{1-\sqrt{5}}{2}}.$

The number $\phi$ appears in other places and is often referred to as the golden ratio.

Proof.

It may not immediately be obvious that the closed firm solution holds; it seems rather miraculous that this formula, peppered with radicals, should somehow yield whole numbers, and additionally correspond to the Fibonacci sequence. Yet, we do just that.

1. Base Cases. The recursive part of the Fibonacci sequence definition only applies to terms past the fist two, hence we will have to show the formula hold manually; this is will be our base cases.

   $F_1$ $={\displaystyle \frac{1}{\sqrt{5}}}\left({\phi }^1-{\psi }^1\right)$

   $={\displaystyle \frac{1}{\sqrt{5}}}\left({\displaystyle \frac{1+\sqrt{5}}{2}}-{\displaystyle \frac{1-\sqrt{5}}{2}}\right)$

   $={\displaystyle \frac{1}{\sqrt{5}}}{\displaystyle \frac{2\sqrt{5}}{2}}$

   $=1$

   To show the formula also holds for the seconds term, we use a trick, which is noting that since $\varphi$ and $\psi$ are roots of $x^2-x-1$,

   ${\phi }^2-\phi -1=0,\text{ so }{\phi }^2=\phi +1\text{ and}$

   ${\psi }^2-\psi -1=0,\text{ so }{\psi }^2=\psi +1.$

   We can use this to simply the exponents in the canonical closed form representation of the second term.

   $F_2$ $={\displaystyle \frac{1}{\sqrt{5}}}\left({\phi }^2-{\psi }^2\right)$

   $={\displaystyle \frac{1}{\sqrt{5}}}\left(\phi +1-\psi -1\right)$

   $={\displaystyle \frac{1}{\sqrt{5}}}\left(\phi -\psi \right)$

   $=F_1$

   $=1$

   This matches with the first few terms of the first two terms of the Fibonacci sequence, which means the base cases hold.

2. Induction Step. Assume that the formula holds for all terms with number less than or equal to $k$, we want to show that it will also hold for the next term. Specifically, we will use,

   $F_k={\displaystyle \frac{1}{\sqrt{5}}}\left({\phi }^k-{\psi }^k\right)$

   $F_{k-1}{\displaystyle \frac{1}{\sqrt{5}}}\left({\phi }^{k-1}-{\psi }^{k-1}\right).$

   We can now plug this into the recursive definition of $F_{k+1}$ to show that the closed form also holds for the next term.

   $F_{k+1}$ $=F_k+F_{k-1}$

   $={\displaystyle \frac{1}{\sqrt{5}}}\left({\phi }^k-{\psi }^k\right)+{\displaystyle \frac{1}{\sqrt{5}}}\left({\phi }^{k-1}-{\psi }^{k-1}\right)$

   $={\displaystyle \frac{1}{\sqrt{5}}}\left({\phi }^k+{\phi }^{k-1}-{\psi }^k-{\psi }^{k-1}\right)$

   $={\displaystyle \frac{1}{\sqrt{5}}}\left({\phi }^{k-1}(\phi +1)-{\psi }^{k-1}(\psi +1)\right)$

   Now we can use the observation we used earlier, in reverse, to swiftly finish the proof. Namely $x+1$ equals $x^2$ when $x$ is $\phi$ or $\psi$. Making the substitution, we immediately get what we want.

   $F_{k+1}$ $={\displaystyle \frac{1}{\sqrt{5}}}\left({\phi }^{k-1}(\phi +1)-{\psi }^{k-1}(\psi +1)\right)$

   $={\displaystyle \frac{1}{\sqrt{5}}}\left({\phi }^{k-1}{\phi }^2-{\psi }^{k-1}{\psi }^2\right)$

   $={\displaystyle \frac{1}{\sqrt{5}}}\left({\phi }^{k+1}-{\psi }^{k+1}\right)$

This is what we needed to show to prove our claim by induction. ∎ End of proof

3.7 The Well-Ordering Principle

We can now show another equivalent fact about the natural numbers which is inextricably linked to induction. This is called the well-ordering principle, which states that every non-empty subset of the natural numbers has a smallest element.

Theorem 41 (Well-ordering Principle).

Let $A$ be a non-empty subset of the natural numbers, $A\subseteq \mathbb{N}$. $A$, then, must have a smallest element.

Proof.

We instead prove the contrapositive of this statement, that if $A$ is a subset of the natural numbers which has no smallest element, then it is the empty set. Now consider the relative complement of $A$ in the natural numbers, which we denote

$B=\mathbb{N}-A$

Notice 1 is an element of $B$, since 1 cannot be an element of $A$, otherwise this would be its least element. Now assume

$1,2,\mathrm{\dots },k\in B,$

which means that none of these numbers are elements of $A$. This implies that $(k+1)$ cannot be in $A$ otherwise it would be its smallest element. Therefore we have shown that $(k+1)$ is in $B$. Therefore, we have

1. $1\in B$, and

2. if $1,2,\mathrm{\dots },k\in B$, then $(k+1)\in B$.

Hence from the principle of strong induction, we know that that $B$ contains the natural numbers. However, since $B$ is the result of subtracting $A$ from the natural numbers, we also know that $B$ is a subset of $\mathbb{N}$, which together implies

$B=\mathbb{N}.$

$\therefore A$ $=\mathbb{N}-B$

$=\varphi$

This completes the proof of the contrapositive, which means that if $A$ has no smallest element, then it must be the empty set. Equivalently, then, every non-empty subset of the natural numbers must have a smallest element. ∎ End of proof

In some sense, the well-ordering principle is the opposite of induction, which makes it a powerful tool for proof by contradiction over the natural numbers. If a predicate $P(n)$ about all natural numbers is false then the set

$\{n\in \mathbb{N}:P(n)\text{ is false}\}$

will be non-empty subset of the natural numbers. It must be non-empty because otherwise this means the predicate is true for all natural numbers. By the well-ordering principle, this set must have a smallest element. A common pattern in a proof by contradiction is the following:

1. Assume that the proposition is false;

2. By the well-ordering principle, there must be a smallest natural number for which the predicate is false, denote this $k$;

3. Show that we can somehow derive a smaller number for which this proposition is also false, contradicting the original assumption that $k$ was the smallest such couter-example.