Discrete Math

Most problems that involve computational methods, need to be solved using computers. Rather than solve for the temperature map of an entire planar region, we solve for the temperature using a discrete set of mesh or grid of points on a representative subset of the planar region.

Discrete mathematics is needed for computer science as information and data is stored digitally. Digitally represented data is inherently discrete and is processed using discrete methods. For example a course grid discrete representation of the 2-d temperature distribution from the plate above could be:

\( \left(\begin{matrix}1&1&1\\2&4&8\\3&9&27\\4&16&64\\5&25&125\\\end{matrix}\right) \)

A voter registry may have voters in a database accessible from a list:

\( \left(\begin{matrix}John\ Smith\\Raheem\ Johnson\\.\\.\\.\\Sarah\ Muller\\\end{matrix}\right) \)

Which may need to be accessed and sorted, say geographically or alphabetically.

Data science solutions to many problems use machine learning algorithms that are inherently discrete in nature. The information that needs processing is discrete, as are the basic problems in data science such as classification or clustering problems. In particular

Digital signal processing involves taking a video, audio, or other signal like temperature, pressure, position and velocity, which is continuous, digitizing it and then processing the digital signal mathematically.

Combinatorics involves in part the study of counting the number of objects, satisfying a specified condition, from sets of variable size. Enumeration and combinatorics is important in many areas and examples including:

Graph theory, which is the study of structures constructed with nodes and the edges joining them, has applications in many fields including,

An example of the shortest tour problem, is shown below, using a software solution.

Many probability assignments are based on counting and combinatorial methods.

Discrete mathematical techniques are important in understanding and analyzing social networks including social media networks.

The mathematics of voting is a thriving area of study, including mathematically analyzing the gerrymandering of congressional districts to favor and/or disfavor competing political parties. The following example illustrates some of the fundamental ideas related to gerrymandering.

There are various types of discrete sets.

There are many different programming languages for programmers to choose from. Each language has its own advantages and disadvantages, and new languages gain popularity while older ones slowly lose ground. In this book, we use the Python 3 programming language. It is popular in both academia and industry, and was designed with education in mind.

PythonTutor is an environment for creating very short and simple Python programs and visualizing their execution. This enables beginners to visually see the data as it gets manipulated by the instructions.

Program files can contain source code and comments. Comments are not instructions for the computer to follow, but instead notes for programmers to read. Comments in Python start with a pound sign (#). Anything following the pound sign that is on the same line as the pound sign will not be executed. Often, at the very beginning of a program, comments are used to indicate the author and other information. Comments are also used to explain tricky sections of code or disable code from executing.

The negation is a statement that has the opposite truth value. The negation of a proposition \(p\), denoted by \(\neg p\), is the proposition "It is not the case, that \(p\)".

For example, the negation of the proposition "Today is Friday." would be "It is not the case that, today is Friday." or more succinctly "Today is not Friday."

"I am a rock and I am an island."

Let \(p\) and \(q\) be propositions. The conjunction of \(p\) and \(q\), denoted in mathematics by \(p \land q\), is True when both \(p\) and \(q\) are True, False otherwise.

"She studied hard or she is extremely bright."

Let \(p\) and \(q\) be propositions. The disjunction of \(p\) and \(q\), denoted in mathematics by \(p \lor q\), is True when at least one of \(p\) and \(q\) are True, False otherwise.

"Take either 2 Advil or 2 Tylenol."

Let \(p\) and \(q\) be propositions. The exclusive disjunction of \(p\) and \(q\) (also known as xor), denoted in mathematics by \(p \oplus q\), is True when exactly one of \(p\) and \(q\) are True, False otherwise.

"If you get a 100 on the final exam, then you earn an A in the class."

Let \(p\) and \(q\) be propositions. The implication of \(p\) and \(q\), denoted in mathematics by \(p \implies q\), is short hand for the statement "if p then q". As such, implication requires \(q\) to be True whenever \(p\) is True. If \(p\) is not True, then \(q\) can be any value. In other words, implication fails (is False) when \(p\) is True and \(q\) is False. Note, this is different from "p if and only if q".

We can form new compound propositions from the implication, \(p \implies q\). They are

The truth tables for these new propositions are shown in the table.

In the section proposition equivalences we will explain why the truth table shows that the conditional \(p \implies q\) and contrapositive \( \neg q \implies \neg p\) are logically equivalent, and why the converse \(q \implies p\) and inverse \( \neg p \implies \neg q\) are logically equivalent.

We illustrate these ideas with an example.

"It is raining outside if and only if it is a cloudy day."

Let \(p\) and \(q\) be propositions. The bi-implication of \(p\) and \(q\), denoted in mathematics by \(p \iff q\), is short hand for the statement "p if and only if q". As such, bi-implication requires \(q\) to be True only when \(p\) is True. In other words, bi-implication fails (is False) when \(p\) is True and \(q\) is False or when \(p\) is False and \(q\) is True.

It is important to contrast implication with bi-implication. Consider the implication example "If you get a 100 on the final exam, then you earn an A in the class." This means that when you get a 100 on the final you also get an A in the class.

As a bi-implication it would say "You get a 100 on the final exam if and only if you earn an A in the class." This becomes a two-way contract where you can earn an A in the class by getting a 100 on the final, but if you do not get a 100 on the final you will not earn an A.

To find truth values of compound propositions, it is useful to break them up into smaller parts.

When creating your own truth table it is crucial to be systematic about ensuring you have all possible truth values for each of the simple propositions. Each simple proposition has two possible truth values, so the number of rows in the table should be \(2^n\) where \(n\) is the number of propositions. You should also consider breaking complex propositions into smaller pieces.

Logical Translations

A long time ago philosophers discovered we could put our thoughts into symbols and more easily follow lines of reasoning. This was an important step in the eventual development of our modern technological society and our use of digital computers. Before computers can work, we have to put our thoughts into them.

BUT, the English language is difficult and we use many different phrases to represent the same logical statements. Translating statements from English sentences to symbols and back is a skill that needs lots of practice.

Two important logical equivalences are De Morgan’s Law. These describe how we "distribute" the negation across the and and or operators.

A proposition is a tautology if its truth value is always True.

A proposition is a contradiction if its truth value is always False.

A proposition that is neither a tautology nor a contradiction is said to be a contingency.

A predicate is a statement involving a variable.

Predicates are denoted as \(P(x)\) or \(Q(x,y)\) where \(P\) and \(Q\) represent the statements and \(x\) and \(y\) represent the possible values. After a value is assigned to each variable, the predicate becomes a proposition which has a truth value.

Consider the statements

Each of these statements considers a proposition over an entire population or set, called the domain, and quantifies how many elements (or people) in the set satisfy the proposition. To represent this idea, we use two main quantifiers, the universal quantifier and the existential quantifier.

The Universal Quantifier, \(\forall\), represents the statement "for all", "for every", "for each". When it comes before a statement, it means that statement is true for all values in the domain.

The Existential Quantifier, \(\exists\), represents the statement "there exists", "for some", "at least one". When it comes before a statement, it means the statement is true for at least one value in the domain.

Recall the previous example statements:

Let \(P(x)\) be the predicate "\(x^2 \geq 0\)". Then we write the statement as \(\forall x P(x)\), where the domain is the set of all integers. This quantified statement will be true since anytime you square a nonzero integer it is positive and \(0^2=0\).

Let \(Q(s)\) be the predicate "student \(s\) has a birthday in July". Then we write the statement as \(\exists s Q(s)\), where the domain is the set of all students in the class. This statement will be true as long as at least one student in the class has a birthday in July. It will be false, otherwise.

It is important to consider the negation of a quantified expression.

This is a universally quantified statement and can be expressed as \(\forall x P(x)\) where \(P(x)\) is the statement "\(x\) has taken Programming Fundamentals" and the domain consists of all the students in this class. The negation of the statement would be "It is not true that every student in this has taken Programming Fundamentals." Equivalently,

This is an existentially quantified statement expressed as \(\exists x \neg P(x)\).

This demonstrates that the negation of a universally quantified statement is an existential statement. In symbols, we have \(\neg \forall x P(x)\equiv \exists x \neg P(x)\).

Similarly, the negation of an existential statement is a universal statement. \(\neg \exists x P(x) \equiv \forall x \neg P(x)\).

The predicate of a quantified statement could be a compound statement. For instance,

This is written as \(\exists x (B(x) \land F(x))\) where \(B(x)\) is the proposition "\(x\) is big." and \(F(x)\) is the proposition "\(x\) is fluffy." and the domain is dogs. Negating this statement would give

\(\neg \exists x (B(x) \land F(x)) \equiv \forall x \neg (B(x) \land F(x)) \equiv \forall x (\neg B(x) \lor \neg F(x))\)

In words,

There are times it will take more than one quantifier to express a statement.

This statement contains both a universal and an existential quantifier. \(\forall x \exists y S(x,y)\) where \(x\) and \(y\) are integers and \(S(x,y)\) is the proposition \(x+y=0\). This statement means, if you have any integer \(x\) (for instance \(x=5\)) then you can find an integer \(y\) (for instance \(y=-5\)) such that \(x+y=0\).

The order of the quantifiers matters. \(\exists x \forall y S(x,y)\) would be

Note that in this statement you find an integer \(x\) so that when you add any integer \(y\) to it you always get 0.

The first statement, for all integers \(x\), there exists an integer \(y\) such that \(x+y=0\), is true. For any integer \(x\) you could choose \(y=-x\) and \(x+y=x+(-x)=0\). While the second statement, there exists an integer \(x\), such that for all integers \(y\), \(x+y=0\), is false.

To negate nested quantifiers, repeatedly apply De Morgan’s Laws of negating a quantifier and a predicate.

Namely, \(\neg \forall x P(x) \equiv \exists x \neg P(x)\) and \(\neg \exists x P(x) \equiv \forall x \neg P(x)\).

A bitwise operation is a Boolean operation that operates on the individual bits (\(0s\), or \(1s\)) of the operand(s) and are summarized

We summarize the truth tables for the bitwise boolean operators.

Logic circuits are important in designing the arithmetic and logic units of a computer processor. Consider the problem of adding two \(8\)-bit numbers in binary. In binary \(0+0=0\), and \(1+0=0+1=1\), but, as in decimal addition, in binary \(1+1=2\), which in binary will be a sum of \(0\) and a carry of \(1\) to the next significant column on the left. Thinking then of adding a specific column of two binary digits, say \(A\) and \(B\), involves as input the digits \(A, B\) and the carry in from the previous column say \(C_{in}\). The output will be the sum \(S\) and the carry out to the next column, say \(C_{out}\). These are the basic components of what is called a binary adder.

The logic table for binary addition based on the digital inputs \(A, B, C_{in}\), and digital outputs \(S\) and \(C_{out}\) is summarized in the table.

It can be shown that the logic for the outputs \(S\), and \(C_{out}\) is given by the following propositions \[ C_{out}=(A\land B)\lor \left(B\land C_{in}\right)\lor \left(A\land C_{in}\right)\] \[S=\left(\sim A\land \sim B\land C_{in}\right)\lor \left(\sim A\land B\land \sim C_{in}\right)\lor \left(A\land \sim B\land \sim C_{in}\right)\lor \left(A\land B\land C_{in}\right) \]

Implementing these logical outputs based on the inputs \((A,B, C_{in})\), is through the use of electronic circuits called logic gates.

The basic logic gates, are the Inverter or Not gate, the And gate, the Or gate and the Xor gate. The graphical representation for each is shown below.

We end this section by first analyzing logic circuits to give their outputs in terms of their input variables, and then, constructing logic circuits based on logical statements.

In the next two examples, we design logic circuits based on logical propositions. The idea is to work backward using order of operations from the right to the left.

Consider the following set described using set builder notation: \[\{x \in \mathbb{Z} : x^2 = 2\}.\]This is the set of all integers whose square is equal to 2. However, no such integers exist. Therefore, using the roster method to describe it, this is the set \(\{ \}.\)

We call the set \(\{ \}\) the empty set and denote this set by \(\emptyset.\) The empty set has no elements.

Suppose that a set \(A\) contains a finite number of distinct elements. We refer to the number of elements of \(A\) as the cardinality of \(A\) and denote this by \(|A|\). If \(A\) contains an infinite number of distinct elements, we say that \(A\) has infinite cardinality and we write \(|A| = \infty.\)

Thus, we see that \(|\{0,1,2\}| = 3\) and \(|\mathbb{Z}| = \infty.\) Additionally, note that \(|\emptyset| = 0.\)

We say that two sets are equal if and only if they contain the same elements. In other words, \(A\) and \(B\) are equal sets if and only if \[\forall x (x \in A \iff x \in B).\]When \(A\) and \(B\) are equal sets, we write \(A = B\). When \(A\) and \(B\) are not equal sets, we write \(A \neq B\).

The sets \(\{2,3,5\}\) and \(\{5,2,3\}\) are equal sets, since they contain the same elements. The order in which the elements of a set are listed does not matter. Additionally, it does not matter whether elements are repeated. Thus, the sets \(\{a,b,c\}\) and \(\{b,b,a,c,b,a,c,c,c\}\) are equal sets as well.

We say that a set \(A\) is a subset of a set \(B\) if and only if every element of \(A\) is an element of \(B.\) In other words, \(A\) is a subset of \(B\) if and only if \[\forall x (x \in A \implies x \in B).\]When \(A\) is a subset of \(B,\) we write \(A \subseteq B\). When \(A\) is not a subset of \(B,\) we write \(A \not\subseteq B\).

In order to show that \(A\) is a subset of \(B,\) we must show that, whenever \(x \in A,\) it is also the case that \(x \in B.\) In order to show that \(A\) is not a subset of \(B,\) we must find a single \(x\) such that \(x \in A\) but \(x \not \in B.\)

Note that, for any set \(A,\) it is always the case that \(\emptyset \subseteq A\) and \(A \subseteq A.\) For any sets \(A\) and \(B,\) if \(A \subseteq B\) and \(B \subseteq A,\) then \(A = B.\)

If \(A \subseteq B\) and \(B\) contains at least one element that is not in A, then we say \(A\) is a proper subset of \(B\), denoted \(A \subset B\).

Given a set \(A,\) we refer to the power set of \(A\) as the set of all subsets of \(A.\) The power set of \(A\) is denoted by \(\mathcal{P}(A).\)

If we let \(A = \{a,b,c\},\) we see that \[\mathcal{P}(A) = \{\emptyset, \{ a \}, \{ b \}, \{ c \}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}.\] The empty set only has the empty set as a subset. Thus, we see that \[\mathcal{P}(\emptyset) = \{\emptyset\}.\]We can also take the power set of a power set. For example, we have the following:

The union of the sets \(A\) and \(B\) is the set containing those elements that are in \(A\) or \(B\) or both, and is denoted by \(A \cup B\). More formally, \[A \cup B = \{x \in U : x \in A \lor x \in B\}.\]

We have the following Venn Diagram for \(A \cup B\):

Note that, for any sets \(A\) and \(B,\) \[A \cup B = B \cup A.\]

The intersection of the sets \(A\) and \(B\) is the set containing those elements that are in \(A\) and \(B\) and is denoted by \(A \cap B\). More formally, \[A \cap B = \{x \in U : x \in A \land x \in B\}.\]

We have the following Venn Diagram for \(A \cap B\):

Note that, for any sets \(A\) and \(B,\) \[A \cap B = B \cap A.\] If it is the case that \(A \cap B = \emptyset,\) then we say that \(A\) and \(B\) are disjoint. In other words, two sets are disjoint if and only if they contain no elements in common.

The difference of the sets \(A\) and \(B\) is the set containing those elements that are in \(A\) but not in \(B\) and is denoted by \(A \setminus B\). Set difference is also denoted by \(A - B\). More formally, \[A \setminus B = \{x \in U: x \in A \land x \not\in B\}.\]

We have the following Venn Diagram for \(A \setminus B\):

Note that, for any sets \(A\) and \(B,\) if \(A = B,\) then \(A \setminus B = \emptyset\) and \(B \setminus A = \emptyset\). Thus, when \(A = B,\) \[A\setminus B = B \setminus A.\] However, if \(A \neq B,\) then \[A \setminus B \neq B \setminus A.\]

The complement of a set \(A\) is the set of all elements in the universal set \(U\) which are not elements of \(A\) and is denoted by \(\overline{A}.\) More formally, \[\overline{A} = \{x \in U: x \not\in A\}.\]

We have the following Venn Diagram for \(\overline{A}\):

For any set \(A,\) \[\overline{A} = U \setminus A.\]

We can also perform more than one set operation on a collection of sets. For example, let \(A,\) \(B,\) and \(C\) be sets and consider the following set: \[(A \setminus B) \cup (C \setminus B).\]This is the set that is obtained by taking the union of the sets \(A \setminus B\) and \(C \setminus B.\) We have \[(A \setminus B) \cup (B \setminus A) = \{x \in U: (x \in A \land x \not\in B) \lor (x \in C \land x \not\in B)\}.\]

We have the following Venn Diagram for \((A \setminus B) \cup (C \setminus B)\):

Video Example 1

Video Example 2

The Cartesian product of two sets \(A\) and \(B\) is the set of ordered pairs defined by,

\( A\times B=\{(a,b)|a\in A\wedge b\in B)\}\),

The ceiling, \(f(x)=\lceil x\rceil\), function rounds up \(x\) to the nearest integer.

The ceiling function, used to compute the ceiling of \(x\), denoted, \( f(x)=\lceil x \rceil \) gives the smallest integer greater than or equal to \(x\).

For example, \( \lceil 3.4 \rceil =4\) and \( \lceil 3.7 \rceil =4\).

The floor \( f(x)=\lfloor x \rfloor \), rounds down \(x\) to the nearest integer.

The floor function, used to compute the floor of \(x\), denoted \( f(x)=\lfloor x \rfloor \), gives the greatest integer less than or equal to \(x\).

For example,\( \lfloor 3.4 \rfloor =3\) and \( \lfloor 3.7 \rfloor =3\).

The graphs of the ceiling (\( \lceil x\rceil\))and floor (\( \lfloor x \rfloor \)) functions are shown below.

The function \(h\left(x\right)=\max{\left(f\left(x\right)\right)},\ g(x))\) is evaluated at each \(x\) for which both \(f(x)\) and \(g(x)\) are defined by the function

\( h(x) =\max(f(x),g(x)) = \left\{ \begin{array}{c} f(x) \\ g(x) \end{array} \right. \begin{array}{c} \text{if } f(x)\text{ }\geq g(x) \\ \text{if } f(x) < g(x) \end{array} \)

So for example if \(f(x) =\ \sqrt x\), and \(g(x) =x^2\) then \(h(x)=\max(f(x),g(x))\), has \(h(1/4) =\max\) \( \left(\sqrt{\frac{1}{4}},\ \left(\frac{1}{4}\right)^2\right) \) \(=max\left(\frac{1}{2},\frac{1}{16}\right)=\frac{1}{2}\), and \(h(4) =\max\) \(\left(\sqrt4,\ 4^2\right)=\max(2,16)=16\). The graph of \(h(x) =\max(\sqrt x,\ x^2)\) over the interval \((0,2)\) is shown below.

The function \(h(x) =\min(f(x),g(x))\) is evaluated at each \(x\) for which both \(f(x)\) and \(g(x)\) are defined and is similar to the \(max\) function, but is defined by the minimum of \(f(x)\), and \(g(x)\) at each \(x\).

\( h(x) =\min(f(x),g(x)) = \left\{ \begin{array}{c} f(x) \\ g(x) \end{array} \right. \begin{array}{c} \text{if } f(x)\text{ }\leq g(x) \\ \text{if } f(x) > g(x) \end{array} \)

So for example if \(f(x) =\ \sqrt x\), and \(g(x) =x^2\) then \(h(x)=\min(f(x),g(x))\), has \(h(1/4) =\min\) \( \left(\sqrt{\frac{1}{4}},\ \left(\frac{1}{4}\right)^2\right) \) \(=\min\left(\frac{1}{2},\frac{1}{16}\right)=\frac{1}{16}\), and \(h(4) =\min\) \(\left(\sqrt4,\ 4^2\right)=\min(2,16)=2\).

The graph of \(h(x) =min(\sqrt x,\ x^2)\) over the interval \([0,2 \)], is shown below

Consider the sum

\(Sum=a_1+a_2+\ldots+a_n=\sum_{i=1}^{n}a_i,\)

which is a description of adding using the index \(i\), the numbers \(a_i\), running from \(i=1\) to \(i=n\).

Suppose we want to evaluate \(b^n\), with base \(b>0\), and exponent, \(n\) a positive integer. For example to evaluate \(5^6\), we could multiply iteratively, 5,

\(1, 5, 5\times5, 5\times5\times5, 5\times5\times5\times5,\) etc .

The factorial of a positive integer \(n\) can be computed iteratively. For example \(4!\) can be calculated as

\(1, 1\times2, 1\times2\times3, 1\times2\times3\times4.\)

Consider an algorithm to determine the minimum element in a finite sequence or list of integers.

The algorithm would be constructed as follows:

A Python implementation of finding the minimum in a set of \(n\) integers is given below.

The linear search algorithm iterates across a list of \(n\) data elements. If the first element in the list is the target element, the algorithm stops. Otherwise, move to the next element and continue repeatedly until the target element is found or not. If the target element is not in the search list the algorithm exhaustively searches through every single element.

This is the worst case scenario with linear search in which the algorithm inspects every single element, either because the target element is the last element of the array, or the target element is not actually in the search list at all. The algorithm runs in \(O(n)\) time in the worst case.

We analyze the bubble sort algorithm beginning with a concrete list of size \(n=5\) and generalize the analysis.

Consider the case of a list of size \(n=5\). The naive bubble sort algorithm in this case will involve 4 passes.

In the first pass, there will be 4 comparisons and up to 4 swaps, after which the element in position 5 is in its correct position.

In the second pass, there will be 3 comparisons and up to 3 swaps, after which the element in position 4 is in its correct position.

In the third pass, there will be 2 comparisons and up to 2 swaps, after which the element in position 3 is in its correct position.

In the fourth pass, there will be 1 comparison and one possible swap , after which both the elements in positions 1 and 2 are both in their correct positions.

Adding the comparisons from each pass we obtain,

\(4+3+2+1=1+2+3+4\).

In general, if the list is of size \(n\), there will be \(n-1\) passes with swaps,

\(n-1+n-2+...3+2+1 = 1+2+3+...+n-1\).

We will show later, that

\( 1+2+3+\cdots+n-1= \frac{(n-1)\cdot\ n}{2}=\frac{n^2}{2}-\frac{n}{2}\), which is \(O(n^2)\).

It is left as an exercise to verify that the insertion sort algorithm is \(O(n^2)\).

The binary search algorithm searches for a target element \(x\) in a list of \(n\) elements by comparing the middle element in the the sorted data set with the target \(x\). The algorithm stops if the middle element \(a_m\) is the target element. Otherwise the search continues with half the data set—​the half to the left if the middle element is larger than the target \(x\) or the half to the right if the middle element is smaller than the target.

The number of steps in the binary search then is the number of times we have to split the data set until we locate the target element, or determine that the target element is not in the search list after splitting down to 1 element.

The number of times we need to split the data set of size \(n\), in the worst case then, is \(p\) which is found by solving the exponential equation,

\(2^p = n\).

The algorithm then is \(O(p)\).

The solution of the exponential equation, \(2^p = n\), is in log form,

\(p=\log_2{n}\).

The binary search algorithm then is \(O(p)=O(\log{n})\).

Let \(a\) be an integer and let \(d\) be a positive integer. Suppose that \(q\) and \(r\) are integers given by the division algorithm. We refer to \(q\) as the quotient and \(r\) as the remainder. We use the following notation:

If \(b\) is an integer and \(a\) is a positive integer, the following theorem shows how we can use the division algorithm to determine whether or not \(a\) divides \(b.\)

For any positive integer \(m,\) we define \(\mathbb{Z}_{m}\) to be the set of nonnegative integers less than \(m.\) In other words, we have \[\mathbb{Z}_m = \{0,1,\dots,m-1\}.\] Let \(a\) and \(b\) be elements of \(\mathbb{Z}_m.\) We define addition in \(\mathbb{Z}_m,\) denoted \(+_m,\) as follows: \[a +_m b = (a + b) \boldsymbol{\bmod} m.\] We define multiplication in \(\mathbb{Z}_m,\) denoted \(\cdot_m,\) as follows: \[a \cdot_m b = (a \cdot b) \boldsymbol{\bmod} m.\]

Let \(a\) and \(b\) be positive integers. The largest positive integer \(d\) such that \(d\) divides \(a\) and \(d\) divides \(b\) is referred to as the greatest common divisor of \(a\) and \(b.\) The greatest common divisor of \(a\) and \(b\) is denoted by \(\gcd(a,b).\) If \(\gcd(a,b) = 1,\) we say that \(a\) and \(b\) are relatively prime.

Additionally, it is not hard to see that \(\gcd(5,3) = 1,\) and thus \(\frac{35}{7}\) and \(\frac{21}{7}\) are relatively prime. In general, we have the following theorem.

Let \(a\) and \(b\) be positive integers. The smallest positive integer \(m\) such that \(a\) divides \(m\) and \(b\) divides \(m\) is referred to as the least common multiple of \(a\) and \(b.\) The least common multiple of \(a\) and \(b\) is denoted by \(\operatorname{lcm}(a,b).\)

Additionally, we observe that \[\gcd(35,21) \cdot \operatorname{lcm}(35,21) = 7 \cdot 105 = 735 = 35 \cdot 21.\] In general, we have the following theorem.

A well-known method for computing the greatest common divisor and least common multiple of a pair of positive integers is called the Euclidean algorithm. Before describing this algorithm, we state the following theorem.

Let \(a\) and \(b\) be positive integers. We let \(r_0 = a\) and \(r_1 = b.\) Next, we use the division algorithm to find integers \(q_1\) and \(r_2,\) with \(0 \leq r_2 < r_1,\) such that \[r_0 = r_1q_1 + r_2.\]Then, if \(r_2 \neq 0,\) we again use the division algorithm to find integers \(q_2\) and \(r_3,\) with \(0 \leq r_3 < r_2,\) such that \[r_1 = r_2q_2 + r_3.\] We continue this process until we obtain a remainder of \(0\); that is, until, for some positive integer \(k,\) we have \(r_{k+1} = 0.\) Then, we have

Additionally, we can use the work from the solution to the previous example to obtain the following:

We express \(\gcd(480,174)\) as a sum of multiples of \(480\) and \(174\) as follows:

In general, we have the following theorem.

Particular values of \(x\) and \(y\) can be found using the Extended Eulcidean algorithm.

A sequence is a function from the natural numbers \(\mathbb{N}=1,2,3\ldots\), into a set \(A\). The sequence may be denoted \(a_n\) for the sequence \(a_1,\ a_2,\ldots\). Sometimes the domain of the sequence may be the set of nonnegative numbers, \(0,1,2,3\ldots\), in which case \(a_n\) would be the sequence \(a_0,\ a_1,\ a_2,\ldots\).

Sequences may be defined using explicit functions or may be defined recursively.

Sequences generated by linear functions as in Example 1 are called arithmetic sequences. Thinking recursively, they are determined by a first term and a common difference. The arithmetic sequence \(a_n=3n+1\) is the sequence whose first term is \(a_1=4\), and whose common difference is \(d=3\). As arithmetic sequences are generated by linear functions \(f\left(x\right)=dx+c\), the general arithmetic sequence is \(a_n=d\cdot n+b\), \(d\) being the common difference.

Sequences generated by exponential functions as in Example 2 are called geometric sequences. Thinking recursively, they are determined by a first term and a common ratio. The geometric sequence \(b_n=2\cdot3^n\), is the sequence whose first term is \(b_1=6\) and whose common ratio is \(r=3\). As geometric sequences are generated by exponential functions \(f\left(x\right)=a\cdot r^n\), the general geometric sequence is \( a_n=a\cdot r^n\), with \(r\) being the common ratio.

Given a sequence of numbers \( \left\{a_{n\ }\right\}=\left\{a_1,a_2,a_3,\ldots\right\}\) we are often interested in adding them up.

Adding a sequence of numbers produces what is called a series.

\( a_1+a_2+a_3+a_4\) is a finite series with 4 terms, and \( a_1+a_2+a_3+\ldots+a_n\) is a finite series up to some finite, but possibly variable number of terms \(n\).

By contrast \(a_1+a_2+a_3+\ldots\) is used to denote an infinite series.

For example, \(a_1+a_2+a_3+a_4=\sum\limits_{i=1}^{4}a_i \) which means starting at \(i=1\), we add up \(a_1\) and then increase \(i\) to 2 and add \(a_2\), and so on, all the way up to the last one at \(i=4\).

\(a_1+a_2+a_3+\ldots+a_n=\sum\limits_{i=1}^{n}a_i\)

The infinite sum is denoted \(a_1+a_2+a_3+\ldots=\sum\limits_{i=1}^{\ \infty\ }a_i\)

We begin with a recursive method for computing \(n!\) for integers \(n \geq 0\).

Recall that \(5!=5\ \times\ 4\ \times\ 3\ \times\ 2\ \times\ 1\ =\ 5\ \times\ 4!\).

In general, we may define \(n!\) recursively or inductively as

\(0!=1\)

\(n!\ =\ n\ \cdot\ (n-1)!\ \)

An implementation of the factorial procedure is given below.

As another simple example, we consider a recursive implementation of exponentiation \(b^n\) with \(n\) a nonnegative integer, \(b>0\), and \(b \neq 1\).

Consider for example \(5^4=5\ {\cdot\ 5}^3\) Hence we can recursively define exponentiation as

\(b^0=1\)

\(b^n=b\cdot\ b^{n-1}\).

A pseudocode recursive implementation of the power function or exponential function \(b^n\) is below.

Consider the arithmetic sequence, \(5, 9, 13, 17,\ldots \), which is an arithmetic sequence with first term \(a_1=5\) and common difference \(d=4\), which may be defined recursively as

\(a_1=5\)

\(a_n=4+a_{n-1}\)

The general arithmetic sequence with first term \(a_1=a\) and common difference \(d\) can be defined recursively,

\(a_1=a\)

\(a_n=d+a_{n-1}\),

and the sequence can be generated recursively using the following pseudocode.

Recall the Fibonacci sequence \(1, 1, 2, 3, 5, 8, 13 \ldots \) is defined recursively,

\(f_1=1\)

\(f_2=1\)

\(f_n=f_{n-1}+f_{n-2}\)

We provide a recursive Python implementation to compute the \(n^{th}\) Fibonacci number.

Merge Sort is a recursive sorting algorithm. The general idea is to divide a list of length \(n\) into \(n\) sublists of length \(1\), where a list of length one is considered already sorted. Subsequently, the algorithm repeatedly merges the sublists to make sorted lists until only a single list of length \(n\) is remaining. This will be the a sorted list consisting of the elements of the original list.

The picture below illustrates this with a list of length seven.

Notice that Merge Sort has complexity \(n \log{n}\). The first part of Merge Sort, similar to Binary Search which is \(O(\log{n})\), the list is repeatedly divides into two halves. The second part of Merge Sort merges \(n\) elements which occurs with complexity \(n\). Since the algorithm performs the first AND the second parts, we multiply to obtain that the complexity is \(O(n \log{n})\).

One way is the use of an adjacency matrix. The adjacency matrix \(M\) represents a graph in a table form, containing a row and column for each vertex \(v_i\). If the vertices \(v_i\) and \(v_j\) are connected by an edge \(e\), the adjacency matrix will contain a \(1\) in the \(i-th\) row and \(j-th\) column and \(0\) otherwise. Denoting by \(m_{i,\ j}\) the component of the adjacency matrix in the \(i-th\) row and \(j-th\) column, we define the adjacency matrix for the graph \(G=\left(V,E\right)\) as

\( m_{i,j}=\left\{ \begin{array}{cc} 1 & \text{if}\text{ }\left\{v_i,v_j\right\} \text{is}\text{ }\text{in}\text{ }E\text{ } \\ 0 & \text{otherwise} \end{array} \right. \)

Undirected graphs are represented using symmetric adjacency matrices while digraphs are represented by adjacency matrices that are not symmetric.

Informally an Eulerian graph is one in which there is a closed (beginning and ending with the same vertex) trail that includes all edges. To define this precisely, we use the idea of an Eulerian trail.

An Eulerian trail or Eulerian circuit is a closed trail containing each edge of the graph \(G=(V,\ G)\) exactly once and returning to the start vertex. A graph with an Eulerian trail is considered Eulerian or is said to be an Eulerian graph.

In the following, the first graph is Eulerian with the Eulerian circuit sequenced from \(1\) to \(7\). The second is not an Eulerian graph. Convince yourself of this fact by looking at all necessary trails or closed trails.

An Euler path on a graph is a path that uses each edge of the graph exactly once. The following are useful characterizations of graphs with Euler circuits and Euler paths and are due to Leonhard Euler

A cycle in a graph \(G=\left(V,E\right)\), is said to be a Hamiltonian cycle if every vertex, except for the starting and ending vertex in \(V\), is visited exactly once.

A graph is Hamiltonian, or said to be a Hamiltonian graph, if it contains a Hamiltonian cycle.

The following graph is Hamiltonian and shows a Hamiltonian cycle \(ABCDA\), highlighted, while the second graph is not Hamiltonian.

While we have the Euler Theorem to tell us which graphs are Eulerian or not, there are no comparable simple criteria to determine if graphs are Hamiltonian or not. We do have the following sufficient criterion due to Paul Dirac.

Exponential functions are of the form \(f\left(x\right)=b^x\), where \(b\) is the base and the variable \(x\) is in the exponent. The base \(b>0\) and \(b ≠ 1\). Properties of exponential functions come from properties of exponents. When the base \(b\) is greater than 1 the exponential function is increasing exponentially, as in the case \(f(x) = 2^x\).

\begin{array}{llcccccccccl} & x & -5 & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 \\ & 2^x & \frac{1}{32} & \frac{1}{16} & \frac{1}{8} & \frac{1}{4} & \frac{1}{2} & 1 & 2 & 4 & 8 & 16 & 32 \end{array}

When the base \(b\) is less than 1 the exponential function is decreasing exponentially, as in the case \(f(x) = \left(\frac{1}{3}\right) ^x\).

\begin{array}{llcccccccccl} & x & -5 & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 \\ & (\frac{1}{3})^x & 243 & 81 & 27 & 9 & 3 & 1 & \frac{1}{3} & \frac{1}{9} & \frac{1}{27} & \frac{1}{81} & \frac{1}{243} \end{array}

Logarithmic functions are the inverse functions corresponding to exponential functions and are used to solve exponential equations. For example, \(y=2^x\) is solved for \(x\) by inverting \(x=\log_2{y}\). Properties of logarithms follow from this relationship between exponentials and logarithms and properties of the exponentials.

We summarize three important properties of logarithms.

All other properties of logarithmic functions come from properties relating the logarithm as the inverse of the exponential and the equivalence of the logarithm \(a =\log_b m\) with \(b^a=m\).

When the base \(b\) is greater than 1, the logarithm function is increasing, as in the case \(f(x) = \log_2 x\).

\begin{array}{llllllcccccc} & x & \frac{1}{32} & \frac{1}{16} & \frac{1}{8} & \frac{1}{4} & \frac{1}{2} & 1 & 2 & 4 & 8 & 16 & 32 \\ & log_2 x & -5 & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 \end{array}

When the base \(b\) is less than 1, the logarithm function is decreasing exponentially, as in the case \(f(x) = \log_{\frac{1}{3}} \ x\).

\begin{array}{llllllcccccl} & x & \frac{1}{243} & \frac{1}{81} & \frac{1}{27} & \frac{1}{9} & \frac{1}{3} & 1 & 3 & 9 & 27 & 81 & 243 \\ & \log_{\frac{1}{3}} x & 5 & 4 & 3 & 2 & 1 & 0 & -1 & -2 & -3 & -4 & -5 \end{array}