GGC

1. Introduction to Python

1.1. Programming basics

Computers are programmable machines that process information by manipulating data. As the data can represent any real world information, and programs can be readily changed, computers are capable of solving many kinds of problems.

1.2. Programming Languages and Environments

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.

1.3. PythonTutor

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.

Simple Program

Use the Forward button to step through the program below and watch the data get created and modified. Notice how the arrows move to indicate what instruction the program execution is on.

1.4. Comments

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, on the same line, 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.

# This line is not Python code, it is a comment.

score = 9001 # over 9000!!!

# The next line of code is disabled because is starts with a #.
# score = 8000

1.5. Data Types

Programming is all about information processing. Information is categorized into data types. Each data type consists of a set of similar values (single pieces of data). Three basic data types are int (integer), string, and boolean. Integer values are whole numbers (without a decimal point). String values are text (sequences of characters) including punctuation, symbols, and whitespace. Unlike the other data types, there are only two Boolean values, True and False. The table below shows examples of ints, booleans, and strings.

Table 1. Basic Data Types
Data Type Example Values

int

2, -2, 0, 834529

boolean

True, False

string

"Hello World!", 'Coconut', "0", '4 + 6'

Strings and Quotes

Strings are always surrounded by quotes. Python allows either single (') or double(") quotes. Some strings may look like numbers, but as long as they are surrounded by quotes, they are treated like text. Booleans are not strings.

1.6. Variables

Variables are (virtual) boxes that store values for reuse later. A variable has a name and a current value. Each variable can only hold one value at a time. Variables are assigned a value using the single equal sign (=). As Python executes one line at a time, variables come into existence on the line where they are first assigned.

Basic Variables and Data Types

Use the Forward button to step through the program below and watch the variables get created.

Variable Names

Variables can have complex names like player1_score. In general, never start a variable name with numbers, and never use spaces.

1.7. Operators and Expressions

Int Operators and Expressions

Try to predict the variable names, values, and data types in the the code example below.

Expression Evaluation

When Python encounters a line with an expression, it always evaluates the expression first.

x = (3 + 4) * 2

Python first calculates the return value of the expression by using the standard order of operations and starting inside the parentheses. Then, Python creates the variable and stores the return value (14). The variable only stores the returned value, not the entire expression.

Boolean Operators and Expressions

Note how each expression returns a boolean value. These are called boolean expressions.

1.8. Strings and Printing

Besides creating and storing values in variables, we can also output text on a screen by calling the print() function.

Strings and print()

Try to predict the printed output. Look at the small window in the top-right as you use the Forward button.

1.9. If Statements

Python can execute or skip over a block of lines using an if statement and a boolean expression. Blocks always start with a colon (:) on the previous line and require every line to be indented with tabs or spaces.

If Statements

Notice that all un-indented lines execute, but only 1 of the blocks.

When you want to force exactly 1 of 2 blocks (as opposed to just skipping a block) you can use if else.

If Else Statements
  • No matter how you change the scores, only 1 print() executes.

  • Try making the scores the same.

1.10. While Statements

Python can execute a block of lines repeatedly using a while statement and a boolean expression. The block repeats until the boolean expression is false.

While Statements

What numbers do you think will print? Notice that without line 3, the loop would run forever.

The += operator increases a variable by a value.

1.11. Lists and Loops

When you need to consider many values at once, use a list.

List Indexing

Try index -2.

When you want to consider every value in a list, use a for loop.

For Loops With Indexes
  • What does the variable i represent?

  • What line creates variable i?

  • What line modifies it?

The range() function returns a sequence of numbers, starting from 0 by default, and increments by 1 (by default), and ends at one less than the entered number. For example, range(6) lists the numbers 0 to 5, inclusive.
For Loops Without Indexes
  • What line creates variable x?

  • What line modifies it?

Summing with Loops
  • What line creates variable g?

  • What line modifies it?

1.12. Defining Custom Functions

In the examples above we have called several functions like print() and len(). You can define your own functions using def. A function definition includes zero or more parameter variables.

Defining Functions
  • What line creates variables a, b?

  • When does that line execute?

  • How many times?

  • Where do variables a, b get their values from?

2. Logic

2.1. Propositional Logic

A proposition is a sentence that declares a fact that is either True or False.

Examples of propositions:

  • Atlanta is the capital of Iowa.

  • 1 + 1 is 2.

  • 1 + 1 is 3.

Propositional logic consists of a set of formal rules for combining propositions in order to derive new propositions.

In Python, we can use boolean variables (typically \(p\), \(q\)) to represent propositions and define functions for each propositional rule. Each rule can be implemented using the boolean operators (and, or, not) discussed in the section on operators and expressions.

2.1.1. Negation

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."

\(p\) \(\neg p\)

True

False

False

True

Negation in Python

The code below prints the truth table. Try to predict the variable names, values, and data types at different steps in the execution. Use the Forward button to check your answers.

2.1.2. Conjunction

"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.

\(p\) \(q\) \(p \land q\)

True

True

True

True

False

False

False

True

False

False

False

False

Conjunction in Python

The code below prints the truth table. Try to predict the variable names, values, and data types at different steps in the execution. Use the Forward button to check your answers.

2.1.3. Disjunction

"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.

\(p\) \(q\) \(p \lor q\)

True

True

True

True

False

True

False

True

True

False

False

False

Disjunction in Python

The code below prints the truth table. Try to predict the variable names, values, and data types at different steps in the execution. Use the Forward button to check your answers.

2.1.4. Exclusive Disjunction

"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.

\(p\) \(q\) \(p \oplus q\)

True

True

False

True

False

True

False

True

True

False

False

False

Exclusive Disjunction in Python

The code below prints the truth table. Try to predict the variable names, values, and data types at different steps in the execution. Use the Forward button to check your answers.

2.1.5. Implication

"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".

\(p\) \(q\) \(p \implies q\)

True

True

True

True

False

False

False

True

True

False

False

True

Implication in Python

Try to complete the code below by clicking edit and replacing \(#FIX ME#\). Once correctly defined, the correct truth table should print.

2.1.6. Bi-Implication

"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 "if and only if p then 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.

\(p\) \(q\) \(p \iff q\)

True

True

True

True

False

False

False

True

False

False

False

True

Bi-Implication in Python

Try to complete the code below by clicking edit and replacing \(#FIX ME#\). Once correctly defined, the correct truth table should print.

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.

2.1.7. Compound Propositions

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

Example 1

The code below reveals the truth table of the compound proposition:

\((p \land q) \lor \neg q\)

Note: \(\neg q\) is mathematical shorthand for not q.

You Try

Edit the code above to reveal the truth value of the compound proposition:

\((p \lor \neg q) \land \neg p\)

Hint: You only need to change line 10.

Example 2

Create a truth table (by hand) for the compound proposition:

\((p \land q) \implies (p \land r)\) for all values of \(p, q, r\). Hint: It should have 8 rows.

\(p\) \(q\) \(r\) \(p \land q\) \(p \land r\) \((p \land q) \implies (p \land r)\)

?

?

?

?

?

?

…​

…​

…​

…​

…​

…​

?

?

?

?

?

?

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.

Examples:

2.2. Proposition Equivalences

Two propositions are considered equivalent if they have the same truth values.

For example, consider \(\neg p \lor q\) versus \(p\implies q\).

\(p\) \(q\) \(\neg p \lor q\) \(p \implies q\)

True

True

True

True

True

False

False

False

False

True

True

True

False

False

True

True

Since the truth table in all rows is the same for the two compound propositions, they are equivalent.

Example 3

Consider the 3-predicate compound propositions below.

  1. \((p\land q) \implies r\)

  2. \((p \implies q) \land (p \implies r)\)

  3. \(p \implies (q \land r)\)

The code below reveals the truth table for 1. Modify it for 2 and 3 in order to determine which set of compound propositions are equivalent.

Hint: You only need to change line 11.

2.2.1. De Morgan’s Laws

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

\(\neg (p \land q)\equiv \neg p \lor \neg q\)

\(\neg (p \lor q)\equiv \neg p \land \neg q\)

We use the symbol \(\equiv\) to denote two statements which are logically equivalent.

Recall the truth table for the implication proposition from above.

\(p\) \(q\) \(p \implies q\) \(\neg (p \implies q)\)

True

True

True

False

True

False

False

True

False

True

True

False

False

False

True

False

You Try

Use the truth table to find a proposition that is logically equivalent to \( \neg (p \implies q) \)?

2.3. Predicates and Quantifiers

2.3.1. Predicates

A predicate is a statement involving a variable.

Examples of predicates:

  • \(x \leq 3\)

  • computer \(c\) is infected

  • country \(x\) is on continent \(y\)

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.

Example 4

Let \(P(x)\) be the predicate \(x \leq 3\). What are the truth values of \(P(5)\) and \(P(2)\)?

Example 5

Let \(Q(x,y)\) be the statement \(x-y=4\).

Edit the Python tutor below to find the truth values of \(Q(6,2)\), \(Q(1,5)\), and \(Q(-2,2)\).

2.3.2. Quantifiers

Consider the statements

  • For all integers \(x\), \(x^2\geq 0\).

  • Some student in the class has a birthday in July.

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.

Universal Quantifier \(\forall x, x + 1 \gt x\)

Let \(P(x)\) be the statement \(x + 1 \gt x\). Is this true for all integers x?

We use the example domain [-2, -1, 0, 1, 2] because code can not check all integers.
Universal Quantifier \(\forall x, x + x \gt x\)

Let \(P(x)\) be the statement \(x + x \gt x\). Is this true for all integers x?

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.

Existential Quantifier \(\exists x, x^2 = 4\)

Let \(P(x)\) be the statement \(x^2 = 4\). Is this true for at least one integer x?

Existential Quantifier \(\exists x, x^3 = 4\)

Let \(P(x)\) be the statement \(x^3 = 4\). Is this true for at least one integer x?

Again, we use the example domain [-2, -1, 0, 1, 2] because code can not check all integers.

Recall the previous example statements:

  • For all integers \(x\), \(x^2 \geq 0\).

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.

  • Some student in the class has a birthday in July.

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.

Are each of these statements true or false?

You Try

Let \(C(x)\) be the statement "\(x\) has visited Canada." where the domain consists of the students at GGC. Express each of the quantifications in English.

\(\exists x C(x)\)

\(\forall x C(x)\)

How would you determine whether each of these statements is true or false?

2.3.3. Negation of Quantifiers

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

  • "Every student in this class has taken Programming Fundamentals."

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,

  • "There is a student in this class who has NOT taken Programming Fundamentals."

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)\).

Example 6
  • Someone in the class can speak Latin.

Using quantifiers, we write this statement as \(\exists x L(x)\) where \(L(x)\) is the proposition "\(x\) speaks Latin." and the domain is the students in the class. Its negation would be \(\forall x \neg L(x)\).

  • All the students in the class can not speak Latin.

You Try

Find the negation of the statement "For all integers \(x\), \(x^2 \geq x\)."

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

  • Some dogs are big and fluffy.

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,

  • All dogs are not big or not fluffy.

2.3.4. Nested Quantifiers

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

  • For all integers \(x\), there exists an integer \(y\) such that \(x+y=0\).

This statement contains both a universal and 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

  • There exists an integer \(x\), such that for all integers \(y\), \(x+y=0\).

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.

You Try

Let \(Q(x,y)\) be the statement \(xy=0\). If the domain for both variables consists of all integers, what are the truth values of the following statements?

  • \(Q(0,3)\)

  • \(Q(6,2)\)

  • \(\forall y Q(1,y)\)

  • \(\exists x Q(x,4)\)

  • \(\forall x \exists y Q(x,y)\)

  • \(\exists x \forall y Q(x,y)\)

  • \(\forall x \forall y Q(x,y)\)

To negate nested quantifiers, repeatedly apply the rules 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)\).

Example 7
  • For all integers \(x\), there exists an integer \(y\) such that \(x=-y\).

Using quantifiers, we write this statement as \(\forall x \exists y N(x,y)\) where \(N(x,y)\) is the proposition "\(x=-y\)." and the domain of \(x\) and \(y\) is the integers. Its negation would be \(\exists x \forall y \neg N(x,y)\).

  • There exists an integer x, such that for all integers y, \(x \neq -y\).

You Try

Find the negation of the statement "Some student in the class will solve every practice problem."

Hint: Let \(x\) be a student in the class, \(y\) be a practice problem, and \(P(x,y)\) be the statement "student \(x\) has solved practice problem \(y\)".

2.4. Problem Set

1. Do some math!

3. Set Theory

3.1. Sets

3.1.1. Definitions

A set is an unordered collection of objects, called elements or members. A set is said to contain its elements. If \(x\) is an element of the set \(A,\) then we write \(x \in A\). If \(x\) is not an element of the set \(A\), then we write \(x \not\in A\).

For example, if \(S\) is the set of states in the United States, then New York is an element of \(S\) and Ontario is not an element of \(S.\) If \(E\) is the set of even integers, then \(2 \in E\) and \(3 \not\in E.\)

There are several diferent ways to describe a set. One way of describing a set is known as the roster method. This is where we list all the elements of a set between curly braces. For example, \(\{a,b,c\}\) is the set whose elements are \(a,\) \(b,\) and \(c.\)

Checking Set Membership

The code below checks to see if \(5\) and \(0\) are elements of the set \(A = \{-2,0,1,4\}.\) Since \(5 \not\in A\) and \(0 \in A,\) the code prints False followed by True.

Listing the Elements of a Set

The code below lists all of the elements of the set \(A = \{-2,0,1,4\}.\)

Another way of describing a set is the use of set builder notation. We write a set as \[\{x \in D : P(x)\}.\]This is the set of all elements \(x\) from a domain \(D\) that satisfy the predicate \(P(x).\) Consider the following set: \[\{x \in \mathbb{Z} : -2 \leq x < 4\}.\] This is the set of all integers \(x\) such that \(-2\) is less than or equal \(x\) and \(x\) is less than 4. Using the roster method, this set can be written as \[\{-2,-1,0,1,2,3\}.\] When there are too many elements in a set for us to be able to list each one, we often use ellipses (\(\dots\)) when the pattern is obvious. For example, we have \[\mathbb{Z} = \{\dots,-3,-2,-1,0,1,2,3,\dots\}.\]

Set Builder Notation

The set \(\{x \in D: P(x)\}\) can be expressed in Python as {for x in D if P(x)}. For example, the code below defines the set \(B\) as the set of positive elements of the set \(A = \{-2,0,1,4\}.\)

You Try

Match each set described using set builder notation in parts (a) through (f) with the same set described using the roster method in parts (A) through (F).

  1. \(\{x \in \mathbb{Z} : x^2 = 1\}\)

  2. \(\{x \in \mathbb{Z} : x^3 = 1\}\)

  3. \(\{x \in \mathbb{Z} : |x| \leq 2\}\)

  4. \(\{x \in \mathbb{Z} : x^2 < 4\}\)

  5. \(\{x \in \mathbb{Z} : x < |x|\}\)

  6. \(\{x \in \mathbb{Z} : (x + 1)^2 = x^2 + 2x + 1\}\)

  1. \(\{-1,0,1\}\)

  2. \(\{\dots, -3,-2,-1,0,1,2,3,\dots\}\)

  3. \(\{1\}\)

  4. \(\{\dots, -3,-2,-1\}\)

  5. \(\{-1,1\}\)

  6. \(\{-2,-1,0,1,2\}\)

3.1.2. Empty Set

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.

Listing the Elements of a Nonempty Set

Since Python interprets {} as an empty dictionary, we cannot use this notation for the empty set. Instead, we must write the empty set as follows:

set()

The function in the code below checks to see if a set is empty. If the set is nonempty, its elements are listed.

It is important to note that \(\{\}\) and \(\emptyset\) are both ways to write the empty set. However, the set \(\{ \emptyset \}\) is not the empty set; rather, it is a set which contains a single element. The single element conained in the set \(\{ \emptyset \}\) is the empty set. In general, the set \(A\) is not the same as the set \(\{ A \}.\)

3.1.3. Cardinality

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.\)

Cardinality

The cardinality of a set \(A\) can be computed in Python as follows:

len(A)

3.1.4. Equality

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.

3.1.5. Subsets

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.\)

If we let \(S = \{1,5\}\) and \(T = \{1,3,5\},\) then \(S \subseteq T,\) since each element of \(S\) is an element of \(T,\) but \(T \not\subseteq S,\) since \(3\) is an element of \(T\) that is not an element of \(S.\) If we let \(A\) be the set of professional athletes and let \(F\) be the set of professional football players, we have \(F \subseteq A,\) since every professional football player is a professional athlete, but \(A \not\subseteq F,\) since not every professional athlete is a professional football player.

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.\)

Subsets

In Python, we can check whether a set \(A\) is a subset of a set \(B\) in one of the following ways:

A.issubset(B)
A <= B.

3.1.6. Power Set

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).\)

\(\mathcal{P}(A)\) is a set whose elements are all sets.

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:

\[\begin{split} \mathcal{P}(\{ 1 \}) &= \{\emptyset, \{ 1 \}\},\\ \mathcal{P}(\mathcal{P}(\{ 1 \}) &= \mathcal{P}(\{\emptyset, \{ 1 \})\\ &= \{\emptyset, \{\emptyset\}, \{ \{ 1 \} \}, \{\emptyset, \{ 1 \}\}\}. \end{split}\]

If \(A\) is a finite set such that \(|A| = n,\) then \(\left|\mathcal{P}(A)\right| = 2^n.\)

3.2. Set Operations

We can obtain new sets by performing operations on other sets. Some of these set operations are discussed below. When performing set operations, it is often helpful to consider all of our sets as subsets of a universal set \(U.\) We can think of the universal set as the set of all of the objects under consideration.

We can represent set operations visually using Venn diagrams, named after the English mathematician John Venn. A Venn diagram will consist of a rectangle, which represents the universal set, and one or more circles, which represent the sets under consideration. We will then shade in the regions of the diagram that correspond to one or more set operations.

3.2.1. Union

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\):

Union

Note that, for any sets \(A\) and \(B,\) \[A \cup B = B \cup A.\] If we let \(A = \{1,2,3,4,5,6\}\) and \(B = \{1,3,5,7,9\},\) then \[A \cup B = \{1,2,3,4,5,6,7,9\}.\]

Union

In Python, we can compute the union of sets \(A\) and \(B\) in one of the following ways:

A.union(B)
A | B

3.2.2. Intersection

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\):

Intersection

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.

If we let \(A = \{1,2,3,4,5,6\}\) and \(B = \{1,3,5,7,9\},\) then \[A \cap B = \{1,3,5\}.\]

Intersection

In Python, we can compute the intersection of sets \(A\) and \(B\) in one of the following ways:

A.intersection(B)
A & B

3.2.3. Difference

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\):

A Subtract 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.\] If we let \(A = \{1,2,3,4,5,6\}\) and \(B = \{1,3,5,7,9\},\) then \[A \setminus B = \{2,4,6\}\] and \[B \setminus A = \{7,9\}.\]

Difference

In Python, we can compute the difference of sets \(A\) and \(B\) in one of the following ways:

A.difference(B)
A - B

3.2.4. Complement

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}\):

ComplementA

For any set \(A,\) \[\overline{A} = U \setminus A.\] Suppose that our universal set is \(U = \{0,1,2,3,4,5,6,7,8,9\},\) the set of all decimal digits. If we let \(A = \{1,2,3,4,5,6\}\) and \(B = \{1,3,5,7,9\},\) then \[\overline{A} = \{0,7,8,9\}\] and \[\overline{B} = \{0,2,4,6,8\}.\]Suppose that our universal set is \(\mathbb{Z}.\) If we let \(E\) be the set of all even integers, then \(\overline{E}\) is the set of all odd integers.

3.2.5. Multiple Set Operations

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)\):

AminusBunionCminusB

Video Example 1

Video Example 2

You Try

Draw Venn Diagrams for each of these combinations of the sets \(A\), \(B\), and \(C\).

  1. \(A \cap (B \cup C)\)

  2. \((A \cap B) \cup C\)

  3. \((\overline{A} \cap \overline{C}) \cup B\)

  4. \((B \cup C) \setminus A\)

3.3. Representing Sets as Lists

We can represent sets in Python using lists. The empty set \(\{ \}\) is represented by the empty list []. Several different lists may represent the same set. For example, the lists [2, 0, 1] and [1, 2, 2, 0, 1, 0, 1] both represent the set \(\{0,1,2\}.\)

It can be helpful for us to remove duplicate elements from a list. For example, this will be necesssary when computing the cardinality of a set.

RemoveDuplicates and Cardinality

The following code contains a function that removes duplicate elements from a set and another that computes the cardinality of a set.

For the rest of the section, we will assume that none of our lists have duplicate elements. Otherwise, we can add one or more lines to each program given below to remove duplicated elements.

We can test whether two sets are equal by testing whether the first is a subset of the second and whether the second is a subset of the first.

Subset and Equal

The followwing code contains a function that checks whether one set is a subset of another and a function that checks whether two sets are equal.

One benefit to using lists instead of sets is that Python does not allow the elements of a set to be sets, but the elements of a list can be lists. This allows us to represent the power set of a set as a list. For example, the power set of [1, 2] is

[[], [1], [2], [1,2]].

We can also represent the union, intersection, and difference of two sets.

Union

The followwing code contains a function that finds the union of two sets.

Intersection

The following code contains a function that finds the intersection of two sets.

Difference

The followwing code contains a function that finds the difference of two sets.

4. Functions

4.1. Definitions

A function, written \(f : A \rightarrow B\), is a mathematical relation with each element of a set \(A\), called the domain, being associated with a unique element of another set \(B\), called the codomain of the function.

For each element \(a \in A\), we associate a unique element \(b \in B\), the set of all such associations \((a,b)\) of such assignments is called a function, \(f\) from \(A\) into \(B\), denoted \(f : A \rightarrow B\), with \((a,b)\) used to indicate the mapping \(f: a \rightarrow b\), or \(f(a)=b\). Here, \(b\) is understood to be the image of \(a\), assigned by \(f\). The range is the set of all image values, \(f(a)\). With this notation, \(a\), is allowed to vary over all elements in the set \(A\), and often when dealing with functions whose domain is from the set of real numbers, say, typically \(x\) is used variables used in f(x)

4.2. Injective Surjective, Bijective and Inverse Functions

A function \(f\) is injective, or one to one, if every element in the range \(B\) is associated with a unique element \(a\) from the domain \(A\). This means that if \(f(m)=b\) and \(f(n)=b\), then necessarily \(m=n\).

A function \(f\) from the set \(A\) to the set \(B\) is surjective, or onto \(B\), if the image set, of \(A\) is the entire set \(B\). This means than for any element \(b \in B\) there is some element \(a \in A\) with \(f(a)=b\).

A function \(f\) is bijective if it is both injective and surjective.

A function \(f\) is invertible if the inverse of relation \(f : A \rightarrow B\) is also a function. The inverse is usually denoted \( f^{\left(-1\right)}\). For example if \((a,b)\), corresponds to \(f(a)=b\) , then \( f^{\left(-1\right)}: B \rightarrow A\), corresponds to \( f^{\left(-1\right)}(b)=a\).

The following theorem shows that invertibility of a function is equivalent to bijectivity or a function being both a one-to one function and onto function.

Theorem 3.1: A function \(f: A \rightarrow B\) is invertible if and only if \(f\) is bijective

Heuristic tip: Being able to solve an equation, amounts to being able to invert a function. Notationally, solving \(f(x) =b\), means solving for \(x\).

Using inverses \(f(x) =b\) is solved \(x=f^{\left(-1\right)}\left(b\right)\). For example if \(f\left(x\right)=x^3\) we know

\$ f^{\left(-1\right)}\left(x\right)=root(3)(x)\$

Solving \(f\left(x\right)=2\) means solving \(x^3=2\). To solve \(f\left(x\right)=2\), we use \(x=f^{-1}\left(8\right)\), which in this case means,

\$ x=f^{\left(-1\right)}\left(8\right)=root(3)(8) = 2\$

An easy check, \( f\left(2\right)=2^3=8\), and

\$ f^{\left(-1\right)}\left(8\right)=root(3)(8) = 2\$

Functions can in many cases be visualized graphically, for example when mapping from the real line, \(\mathbb{R}\) to the real line, such maps are viewed on a Cartesian plan.

We present several standard examples to illustrate the important concepts of functions, including domain, codomain, range, and invertibility.

Example the function \(f(x) =x^2\)

The function \(f(x) =x^2\), denotes the association \((a,b) =(x, x^2)\) with \(f : \mathbb{R} → \mathbb{R}\).We notice that the range is the set of real numbers [0, ∞) , \(\mathbb{R}+\), The function is not invertible, since it is not injective, because, for example, we have both, \(f(-3) =9\) and \(f(3)=9\) With \(f : \mathbb{Z} → \mathbb{Z}\) notice that the range is now \(\mathbb{N}\)

\begin{array}{lccccccccccc} & x & -5 & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 \\ & x^2 & 25 & 16 & 9 & 4 & 1 & 0 & 1 & 4 & 9 & 16 & 25 \end{array}

geometricsequence

Example the function \(f(x) =x^3\)

Cubic functions The function \(f(x) =x^3\), denotes the association \((a,b) =(x, x^3)\) with \(f : \mathbb{R} → \mathbb{R}\) also, we notice that the range is the set of all real numbers (- ∞ , ∞) , \(\mathbb{R}\). The function is bijective and so invertible. With \(f : \mathbb{Z} → \mathbb{Z}\), notice that the range, in addition to domain, is also \(\mathbb{Z}\)

\begin{array}{llcccccccccl} & x & -5 & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 \\ & x^3 & -125 & -64 & -27 & -8 & -1 & 0 & 1 & 8 & 27 & 64 & 125 \end{array}

geometricsequence

For the purposes of completeness, and for comparing how fast functions \(f(x)\) grow for large x, we present the inverse of the functions \(f(x)= x^2\), and \(f(x)= x^3\), when \(f(x):\mathbb{R}+→\mathbb{R}+\), respectively the functions\( f(x)=√x\), and \(f(x)= \) \$root(3)(x)\$.

\begin{array}{lcccccccccclll} & x & 0 & 1 & 4 & 9 & 16 & 25 & 36 & 49 & 64 & 81 & 100 & 121 & 144 \\ & √x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \end{array}

geometricsequence

\begin{array}{lcccccl} & x & 0 & 1 & 8 & 27 & 64 & 125 \\ & \sqrt[3]{x} & 0 & 1 & 2 & 3 & 4 & 5 \end{array}

geometricsequence

Example the rounding functions, the ceiling function, \( \lceil x\rceil \), and the floor function \( \lfloor x \rfloor \) .

In discrete math often we need to round real numbers to a discrete integer.

Ceiling function The ceiling function, used to compute the ceiling of \(x\), denoted, \( \lceil x \rceil \) gives the smallest integer greater than or equal to, \(x\). The ceiling function rounds up \(x\) to the nearest integer. For example, \( \lceil 3.4 \rceil =4\) and \( \lceil 3.7 \rceil =4\).

Floor function Rounding down to the nearest integer is denoted by the floor of \(x\), denoted, \( \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 ceiling and floor functions are shown below.

geometricsequence

Example the the \(max\), and \(min\), functions

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 likewise has, \(h(4) =max\) \(\left(\sqrt4,\ 4^2\right)=max(2,16)=16\).

The function \(h(x) =min(f(x),g(x))\) is similarly defined

\( 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 likewise has, \(h(4) =min\) \(\left(\sqrt4,\ 4^2\right)=min(2,16)=2\). The graphs of \(h(x) =max(\sqrt x,\ x^2)\), and \(h(x) =min(\sqrt x,\ x^2)\) are shown below

geometricsequence
geometricsequence

Example the the exponential and logarithmic functions

Properties of exponentials 1) For a>0, a ≠ 1

\(a^m.\ a^n=a^{m+n}\)

\(3^4.\ 3^5=\left(3.3.3.3.3\right).\left(3.3.3.3.3\right)=3^{4+5}=3^9\)

2) \(\frac{a^m}{a^n}=a^{m-n}\)

\(\frac{3^5}{3^2}=\frac{3.3.3.3.3}{3.3.}=3^{5-2}=3^3 \)

3) \(\left(a^m\right)^n=a^{m.n\ }\)

\(\left(3^4\right)^3=(3.3.3.3)(3.3.3.3)(3.3.3.3)=3^{4.3}=3^{12}\)

4) \(\left(a.b\right)^m=a^mb^m\)

\(\left(3x\right)^4=\left(3x\right).\left(3x\right).\left(3x\right).\left(3.x\right)=\left(3.3.3.3.\right).\left(x.x.x.x\right)=3^4.x^4\)

5) \(a^0=1\) \(1=\frac{3^5}{3^5}=3^{5-5}=3^0\)

6) \(a^{-1}=\frac{1}{a}\) \(3^{-1}=3^{0-1}=\frac{3^0}{3^1}=\frac{1}{3}\)

7)

\$ a^\frac{1}{n}=root(n)(a)\$
\$ 7 =root(3)(7).root(3)(7).root(3)(7) \text{, or, } 7^1 = 7^{1/3}.7^{1/3}.7^{1/3}\$

Exponential functions

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 exponent When the base \(b>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}

geometricsequence

When the base \(b<1\) the exponential function is decreasing exponentially, as in the case \(f(x) = (\frac{1}{3}) ^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}

geometricsequence

Logarithmic functions The logarithm functions. 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.

1) The exponential function \(f\left(x\right)=y=b^x\), written in exponential form is \(\log_b{f\left(x\right)=\log_b{y=x}}\). Its inverse is the logarithmic function, \(x=b^y\), which, is denoted \(y=\log_b{x}\). The importance of this property is in the following heuristic: Heuristic: Exponential equations are typically solved through the use of logarithms, and logarithmic equations are typically solve using the exponential form.

So for example, the exponential equation, \(2^x=5\), becomes, in logarithmic form \(x=\log_2{5}\).

2) The power rule for logarithms states that \(\log_b{m^x=x.\log_b{m}}\). Its importance lies in converting exponentiation with \(x\), to multiplication by \(x\). For example to solve \(2^x=5\), taking the logarithmic in base 10 on both sides, gives, \(\log_{10}{2^x=\log_{10}{5}}\), or \(x.\log_{10}{2=\log_{10}{5}}\), so, dividing both sides by, \(\log_{10}{2}\), gives, \(x=\frac{\log_{10}{5}}{\log_{10}{2}}\).

3) Comparing the solutions of \(2^x\), \(x=\log_2{5,}\) and \(x=\frac{\log_{10}{5}}{\log_{10}{2}}\), gives \(\log_2{5}=\frac{\log_{10}{5}}{\log_{10}{2}}\), which, essentially, is the change of base formula \(\log_b{A}=\frac{\log_a{A}}{\log_a{m}}\).

\(1+2+3+\ldots+n=\sum_{i=1}^{n}{i=\frac{n\left(n+1\right)}{2}}\)

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>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}

geometricsequence

When the base \(b<1\), the logarithm function is decreasing , 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}

geometricsequence

When the base \(b<1\) the exponential function is decreasing exponentially

Algebra of functions: If two functions \(f\left(x\right),\ g\left(x\right)\), have the same domain \(A\), then we can combine these functions using the common algebraic operations of addition, subtraction, multiplication, and division, as follows: \(\left(f+g\right)\left(x\right)=f\left(x\right)+g\left(x\right)\)

\(\left(f-g\right)\left(x\right)=f\left(x\right)-g\left(x\right)\)

\(\left(f\cdot\ g\right)\left(x\right)=f\left(x\right)\cdot\ g\left(x\right)\)

\(\left(\frac{f}{g}\right)\left(x\right)=\frac{f\left(x\right)}{g\left(x\right)},\ \ g\left(x\right)\neq0\)

Example:

Consider \(f\left(x\right)=x^2+1\), and \(g\left(x\right)=\sqrt x\) defined on \(f,\ g:R\rightarrow R\). Then the common domain is \(\ x\ \geq0\), since the square root is real valued only for \(\ x\ \geq0\).

\(\left(f+g\right)\left(x\right)=f\left(x\right)+g\left(x\right)=x^2+1+\sqrt x\) , for \( x ≥ 0\)

\(\left(f-g\right)\left(x\right)=f\left(x\right)-g\left(x\right)=x^2+1- sqrt x\) , for \( x ≥ 0\)

\(\left(f\cdot\ g\right)\left(x\right)=f\left(x\right)\cdot\ g\left(x\right)=\left(x^2+1\right)\cdot\ \sqrt x\), for \( x ≥ 0\)

\(\left(\frac{f}{g}\right)\left(x\right)=\frac{f\left(x\right)}{g\left(x\right)}=\frac{x^2+1\cdot\ }{\ \sqrt x}\), for \( x > 0\).

Notice that the domain of \(\frac{f}{g}\) is \(x>0\), because \(g\left(0\right)=\sqrt0=0\), and division by \(0\) is not defined, so \(\ x=0\), is not in the domain, and so the domain is \(x>0\).

Composition of functions.

Suppose \(g:A\rightarrow B\), and \(f:B\rightarrow C\), then the functions \( f,\ g\), can be composed to obtain a function \(h:A\rightarrow C\), denoted as follows \(h\left(x\right)=\left(f\circ g\right)\left(x\right)=f\left(g\left(x\right)\right)\) provided \(x\ \in\ A\), and \(g\left(x\right)\in B\).

Example:

Consider \(f\left(x\right)=\frac{1}{x}\) ,and \(g\left(x\right)=2x-3\), defined on \(f,g:R\rightarrow R\). Notice that \(g\left(x\right)\), is defined for all real \(x\), and \(f\left(x\right)\), is defined for all real \(x\ \neq0\).

Then \(h\left(x\right)=\left(f \circ g\right)\left(x\right)=f\left(g\left(x\right)\right)=f\left(2x+3\right)=\frac{1}{2x-3}\). Here \(x\) needs to be in the domain of \(g\left(x\right)\), or all real \(x\), and \(g\left(x\right)\) needs to be in the domain of \(f\left(x\right)\). In particular \(g\left(x\right)\neq 0\), or \(2x-3\ \neq 0\), or \(x\ \neq\frac{3}{2}\).

By contrast \(h\left(x\right)=\left(g\circ f\right)\left(x\right)=g\left(f\left(x\right)\right)=g\left(\frac{1}{x}\right)=2\left(\frac{1}{x}\right)-3=\frac{2}{x}-3\). Here \(x\), needs to be in the domain of \(f\left(x\right)\), or \(x\ \neq 0\), and \(f\left(x\right)\), needs to be in the domain of \(g\left(x\right)\), or \(f\left(x\right)\) can be any real number.

Example: Consider \(f\left(x\right)=x^3+1\), and \$g(x) =root(3)(x-1)\$ defined on on \(f,g:R\rightarrow R\). Show that \(\left(g \circ f\right)\left(1\right)=1, \left(g \circ f\right)\left(2\right)=2, \left(g\circ f\right)\left(3\right)=3\), and \(\left(g\circ f\right)\left(x\right)=x\)

Solution

Using,

\(f\left(1\right)=1^3+1=2\)

\(f\left(2\right)=2^3+1=9\)

\(f\left(3\right)=3^3+1=28\)

\(f\left(x\right)=x^3+1\)

obtain,

\( \left(g\circ f\right)\left(1\right)=g\left(f\left(1\right)\right)=g\left(2\right)=\) \$ root(3)(2-1)= root(3)(1)=1\$

\(\left(g\circ f\right)\left(2\right)=g\left(f\left(2\right)\right)=g\left(9\right)=\) \$ root(3)(9-1)= root(3)(8)=2\$

\(\left(g\circ f\right)\left(3\right)=g\left(f\left(3\right)\right)=g\left(28\right)=\) \$ root(3)(28-1)= root(3)(27)=3\$

\(\left(g\circ f\right)\left(x\right)=g\left(f\left(x\right)\right)=g\left(x^3+1\ \right)=\)\$ root(3)(x^3 +1 -1)= root(3)(x^3 )=x\$

Notice that \(g\left(x\right)\), undoes \(f\left(x\right)\), in the following sense:

\(f:1\rightarrow 2\) , and \(g:2\rightarrow 1\), or the ordered pair \(\left(1,2\right)\), corresponding to \(f\), corresponds to \(\left(2,1\right)\), for \(g\)/

\(f:2\rightarrow 9\), and \(g:9\rightarrow 2\), or the ordered pair \(\left(2,9\right)\), corresponding to \(f\), corresponds to \(\left(9,2\right)\), for \(g\)

\(f:3\rightarrow 28\), and \(g:28\rightarrow 3\), or the ordered pair \(\left(3,28\right)\), corresponding to \(f\), corresponds to \(\left(28,3\right)\), for \(g\)

\(f:x\rightarrow x^3+1\), and \(g:x^3+1\rightarrow x\), or the ordered pair \(\left(x,x^3+1\right)\), corresponding to \(f\), corresponds to \(\left(x^3+1,x\right)\), for \(g\).

The function \$ g(x))= root(3)(x-1) \$, is said to be the inverse of the function \(f\left(x\right)=x^3+1\). We have shown explicitly that

\(\left(g\circ f\right)\left(x\right)=x\). We leave it as an exercise to verify that \(\left(f\circ g\right)\left(x\right)=x.\)

We define now inverse functions.

Definition

Suppose \(f\left(a\right):A\rightarrow B\), is bijective, with \(f:a\rightarrow b\), corresponding to the ordered mapping \(\left(a,\ b\right)\) with, \(a\in A,\ b\in B\), then the inverse of \(f\left(x\right)\), is the function, denoted \(f^{-1}\left(b\right):B\rightarrow A\), with \(f^{-1}:b\rightarrow a\), corresponding to the mapping \(\left(b,a\right)\), with, \(b\in B,a\in A\).

The inverse can be similarly defined for relations in general, not bijective functions. However the bijective property is used to ensure that the inverse of a function \(f\), is also a function.

For example the following relations have inverses as given.

\(\left\{\left(-3,\ 9\right),\ \left(-2,4\right),\ \left(-1,1\right),\ \left(0,0\right),\ \left(1,\ 1\right),\ \left(2,\ 4\right),\ \left(3,9\right)\right\}\),

with inverse,

\(\left \{ \left(9,-3\ \right),\ \left(4,\ -2\ \right),\ \left(1,\ -1\right),\ \left(0,0\right),\ (1,\ 1,\ \left(4,2,\right),\ (9,3)\right \}\)

Notice that the original relation can be considered a function with domain \(A=\left\{-3,\ -2,\ -1,\ 0,\ 1,\ 2,\ 3,\right\}\), and co-domain \(B=\left\{0,\ 1,\ 4,\ 9\right\}\). However the inverse mapping, from domain \(A=\left\{0,\ 1,\ 4,\ 9\right\}\), with co-domain \(B=\left\{-3,\ -2,\ -1,\ 0,\ 1,\ 2,\ 3,\right\}\), is a relation that is not a function because of the mappings, for example, \(\left(-9,3\right), and \left(-9,\ 3\right)\).

Example:

verify that the function \(f\left(x\right)=3x+5\), from \(f:R\rightarrow R\) is bijective.

Solution: For injectivity, suppose \(f\left(m\right)=f(n)\), we want to show \(m=n\).

\(f\left(m\right)=f(n)\)

\(3m+5=3n+5\)

Subtracting 5 from both sides, gives, \(3m=3n\), and then multiplying both sides by \(\frac{1}{3}\), gives \(m=n\). To show that \(f\left(x\right)\) is surjective we need to show that any \(c\in R\), can be reached by \(f\left(x\right)\). Specifically, to show that \(f\left(x\right)\) is surjective, we need to show that for any \(c\in R\), there is a corresponding \(x\), for which \(f\left(x\right)=c\). To show this consider \(f\left(x\right)=3x+5\), equate to \(c\), and solve for \(x\).

\(f\left(x\right)=3x+5=c\).

Well, \(3x+5=c\), gives \(3x=c-5\), or \( x=\frac{c-5}{3}\). So, for any \(c\), there is an \(x\), namely, \(x=\frac{c-5}{3}\), for which \(f\left(x\right)=c\).

Example:

Find the inverse \(g\left(x\right)\), of the bijective function \(f\left(x\right)=3x+5\), for \(f,\ g:R\rightarrow R\) . Verify the inverse, and show

\(\left(f \circ g\right)\left(x\right)=x=\left(g \circ f\right)\left(x\right)\). Show specifically that \(f\left(2\right)=11\), and \(g\left(11\right)=2\).

Solution:

If \(f:x\rightarrow y\), corresponds to \((x,y)\), then the inverse \(g:y\rightarrow x\) corresponds to \((y,x)\). This means that the inverse of the relation \(y=f\left(x\right)=3x+5\), is the relation, \(x=f\left(y\right)=3y+5\).

Solving for \(y\), in \(x=f\left(y\right)\), gives \(f^{-1}(x)=y\), Solving for, \(y\), in \(x=f\left(y\right)=3y+5\), gives \(x-5=3y,\), or \(\frac{x-5}{3}=y=\ f^{-1}(x)=g(x)\).

We now verify that \(\left(f\circ g\right)\left(x\right)=x=\left(g \circ f\right)\left(x\right)\).

\(\left(f\circ g\right)\left(x\right)=f\left(\frac{x-5}{3}\right)=\ 3\left(\frac{x-5}{3}\right)+5=\left(x-5\right)+5=x\),

and, \(\left(g \circ f\right)\left(x\right)=g\left(3x+5\right)=\ \frac{(3x+5)-5}{3}=\frac{3x+5-5}{3}=\frac{3x}{3}=x\).

Finally, \(f\left(x\right)=3x+5\), and \(f\left(2\right)=3\left(2\right)+5=6+5=11\), or \(f:2\rightarrow 11\),

and, \(g\left(x\right)=\frac{x-5}{3}\) , and , \(g\left(11\right)=\frac{11-5}{3}=\frac{6}{3}=2\), or \(g:11\rightarrow 2\).

4.3. Exercises

  1. What can be said about the relation \(f:A\rightarrow B\), if

    1. \(\exists z\in B,\forall x\in A,f\left(x\right)\neq z\)

    2. \(\exists x,y\in A,\exists z\in B,\left(x\neq y\right)\bigwedge\left(f\left(x\right)=f\left(y\right)=z\right)\)

    3. \(\forall x,y\in A,\left(f\left(x\right)=f\left(y\right)\right)\ \rightarrow\left(x=y\right)\)

    4. \(\forall x,y\in A,\left(x\neq y\right)\rightarrow\left(f\left(x\right)\neq f\left(y\right)\right)\)

    5. \(\forall z\in B,\exists x,f\left(x\right)=z\)

    6. \(\exists x,y\in A,\left(f\left(x\right)=f\left(y\right)\right)\bigwedge\left(x\ \neq\ y\right)\)

  2. Use properties of logarithms to show that \(f\left(x\right)=2^x\), and \(g\left(x\right)=\log_2{x}\), from f\(,\ g:R\rightarrow R\), are inverses by verifying that \(f\left(g\left(x\right)\right)=g\left(f\left(x\right)\right)=x\).

  3. Use properties of logarithms to show that \(f\left(x\right)=10^x\), and \(g\left(x\right)=\log{x}\), from \(f,\ g:R\rightarrow R\), are inverses by verifying that \(f\left(g\left(x\right)\right)=g\left(f\left(x\right)\right)=x\).

  4. Show that the function \(f\left(x\right)=5x-3\), from \(f:R\rightarrow R\) is bijective and find its inverse.

  5. Show that the function \(f\left(x\right)=2x^3-1\), from \(f:R\rightarrow R\) is bijective and find its inverse.

  6. Consider the function \(f:\mathbb{R}\rightarrow\mathbb{Z}\), from the set of real numbers to the set of integers, defined by: \(f\left(x\right)=\left\lceil x\right\rceil\),

    1. Is the function a surjection? Explain.

    2. Is the function an injection? Explain

    3. Is the function a bijection? Explain

    4. Is the inverse mapping a function? Why or why not?

    5. Evaluate

      1. \(f\left(-2.1\right)\)

      2. \(f\left(-1.9\right)\)

      3. \(f\left(1.5\right)\)

      4. \(f\left(1.9\right)\)

      5. \(f\left(2\right)\)

      6. \(f\left(2.3\right) \)

    6. Suppose \(g\left(x\right)=2x\), with, \(f\left(x\right)=\left\lceil x\right\rceil\), evaluate,

      1. \(f\left(g\left(2.3\right)\right)\),

      2. \(g\left(f\left(2.3\right)\right)\).

  7. Consider the function \(f:\mathbb{R}\rightarrow\mathbb{Z}\), from the set of real numbers to the set of integers, defined by: \(f\left(x\right)=\left\lfloor x\right\rfloor\).

    1. Is the function a surjection? Explain.

    2. Is the function an injection? Explain

    3. Is the function a bijection? Explain

    4. Is the inverse mapping a function? Why or why not?

    5. Evaluate

      1. \(f\left(-5.1\right) \)

      2. \(f\left(-3.9\right)\)

      3. \(f\left(-3.2\right)\)

      4. \(f\left(5\right) \)_

      5. \(f\left(5.3\right)\)

    6. Suppose \(g\left(x\right)=3x\), with, \(f\left(x\right)=\left\lfloor x\right\rfloor\), evaluate

      1. \(f\left(g\left(5.3\right)\right)\)

      2. \(g\left(f\left(5.3\right)\right)\)

  8. The absolute value function \(f\left(x\right):R\rightarrow R\), gives the distance of \(x\), from the origin \(0\) and is denoted \(f\left(x\right)=|x|\). So for example \(f\left(2.5\right)=\left|2.5\right|=2.5\) , but, for example, \(f\left(-4.5\right)=\left|-4.5\right|=4.5\). Notice that if \(x geq 0\), then \(\left|x\right|=x\). However if \(x<0\), then we have to negate to find that \(\left|x\right|=\ -x\). We can state this using the notation for piecewise functions:

\$f(x) = |x|={( x, if x ≥ 0),(-x,if x < 0):}\$
  1. Graph \(f\left(x\right)=|x|\), for -\(10\ \le x\ \le10\)

  2. Evaluate

    1. \(f(-5)=|-5|\),

    2. \(f(-2.5)=|-2.5|\),

    3. \(f(3.5)=|3.5|\).

  3. Show that \(f\left(x\right)=\left|x\right|\), with \(f:R\rightarrow R\), is not injective.

  4. Show that \(f\left(x\right)=\left|x\right|\), with \(f:R\rightarrow R\), is not surjective.

  5. Consider \(g\left(x\right)=3x+2\), with \(g:R\rightarrow R\), and, \(f\left(x\right)=|x|\), find and simplify,

    1. \(\left(g\circ f\right)\left(x\right)\)

    2. \(\left(f\circ g\right)\left(x\right)\)

5. Chapter Algorithms

5.1. Definitions

An algorithm is a step-by-step process, defined by a set of instructions to be executed sequentially to achieve a specified task producing a determined output.

Examples of common discrete math algorithms include:

  • Searching Algorithms to search for an item in a data set or data structure like a tree.

  • Sorting Algorithms to sort items in a specific order.

  • Insertion and Deletion Algorithms to insert or delete item in a data structure such as a tree or list.

  • Division Algorithms such as a procedure for dividing two integers or the Euclidean Algorithm to determine the greatest common divisor between two integers.

  • Optimization algorithms such as finding the line of best fit of set of points, or the problem of finding the nearest neighbor in a set of points to a given point (here close could mean most similar according to some mathematically defined measure of closeness or similarity)

5.2. Pseudocode and Python

While the algorithms we describe are implemented in the Python programming language, we also provide the pseudocode syntax for important algorithms. Pseudocode is used to provide high level description of a program or algorithm intended to be more human understandable rather than computer or program language interpretable. Its syntax preserves the structure of the program or algorithm. It is meant to be easier to read and analyze. Often in designing an algorithm or program for language specific implementation, a pseudocode implementation or description is obtained first. In addition to coming early in the design of a computer program, pseudocode also has two other important uses:

  1. It can be used to help non-programmers understand what a program or algorithm does and how it works.

  2. It can be used for debugging purposes when a programmer is trying to debug and solve a logic error in a computer program as it is closer to human language. Defects are easier to find in a program implementation by analyzing the sequence of implementation steps in the pseudocode description.

Table 2. While Loop Example
Pseudo Code Python Code
while Expression do (1)
  statement 1 (s1)
  statement 2 (s2)
  .
  .
  .
  statement n (sn)
end (2)
1 Start block of code with do
2 End block of code with end
while Expression: (1)
  statement 1 (s1)
  statement 2 (s2)
  .
  .
  .
  statement n (sn)
(2)
1 Start block of code with :
2 End block of code with unindent

5.3. Structure of algorithms

Recall that an algorithm is a process of finite sequences of instructions used to solve a problem or obtain a result of a computation. The key features of an algorithm include:

  • Input

  • Variables

  • Data and data types

  • Instructions or statements

  • Output

5.3.1. Variable Assignment:

Variables, such as \(x,\ y,\ z,\ t,\ m,\ a_1,\ a_2,\ldots a_n \), as in algebra, can be assigned different values based on the variable data type. We use the “=” for variable assignment as in for example, \[ t=5, \] which assigns to the variable \(t\), the value 5. The variable \(x\), keeps this value unless reassigned, as in, \[t=t+3. \] In this case the variable t is now assigned the value \[ t=5+3. \] The previous example illustrates an important point about assignments, namely that the right side is always evaluated before assignment setting of variables. For example the sequence of steps,

\begin{array}{c} x=5,\\ y=3,\\ x=y, \end{array}

will have at the end of the sequence, \(x=3\) and \(y =3\).

5.3.2. Statements:

A statement is a line of code or instruction step in an algorithm or program.

5.3.3. Loops:

A while loop is a control flow statement that iterates a sequence of statements provided the Boolean expression is True or nonzero.

while Expression do
  statement 1 (s1)
  statement 2 (s2)
  .
  .
  .
  statement n (sn)
end

The loop iterates as long as the sequence of statements \((s_1\ldots s_n,)\) maintains the True or nonzero value of Expression and exits after an iteration of \((s_1\ldots s_n,)\) that changes Expression to False or zero.

While loop in Python

The Python code below uses a while loop to display or output the non-negative integers less than 11.

A for loop is a very similar control flow statement to a while loop.

for iterating_variable in sequence do
  statement 1 (s1)
  statement 2 (s2)
  .
  .
  .
  statement n (sn)
end

The most common form of the for loop is with a sequential, integer counter, \(i\).

for i = m to n do
  statement 1 (s1)
  statement 2 (s2)
  .
  .
  .
  statement n (sn)
end
For loop in Python

The Python code below uses a for loop to display or output the non-negative integers less than 11.

5.3.4. Control flow and conditional statements

The sequence in which statements can be executed in an algorithm or program can be controlled using conditional statements or logical operators. The while loop is an example of a conditional statement.

A common conditional statement is the if … then do statement.

if Expression do
  statement 1 (s1)
  statement 2 (s2)
  .
  .
  .
  statement n (sn)
end

The while loop and the if … then do statement are similar but have one important difference. The sequence of statements \(s_i\) are executed at most once within the if … then do statement but may be iterated multiple times in a while loop. The if … then do statement executes a sequence of statements, once, if the Boolean Expression is True or nonzero.

A more general variation of the if … then do statement is the if … then do … else do statement, which allows between two choices of execution statements. Its general syntax is

if Expression do
  statements (si)
else do
  statements (Si)
end

Here if the Boolean Expression is True or nonzero, the sequence of statements \((s_i)\), are executed once, otherwise the sequence of statements \((S_i)\), are executed.

if … then do … else do in Python

The Python code below uses a if else to check if a result is less than 100.

5.3.5. Output

There are a couple of ways to indicate output using pseudocode including, 1) an output statement, or 2) a print statement. For example the following both output the value of the variable count

  • output count

  • print count

Here are two pseudocode implementations of an algorithm to count the non-negative integers less than 11, the first using an output and the second a print statement.

Table 3. Output Examples
Pseudo Code Using Output Pseudo Code Using Print
count = 0
while (count < 11) do
  output "The count is:", count
  count = count + 1
end
output "Good bye! Thanks for counting."
count = 0
while (count < 11) do
  print("The count is:", count)
  count = count + 1
end
print("Good bye! Thanks for counting.")

5.3.6. Commenting

We adopt the Python syntax for commenting or annotating within code or pseudocode-- comments are denoted by beginning a line with the hash (#) character, are automatically ended by the end of line.

5.3.7. Procedures and functions.

Algorithms can be thought of as units, such as a procedure or function. They can be implemented as procedures or functions and then called repeatedly as necessary rather than replicating all of the code every time the algorithm is used. The pseudocode syntax is:

procedure Name(input parameter variables)
begin
  statements
  .
  .
  .
  return value
begin
Python Function Example

The Python syntax, for a procedure or function, is very similar to pseudo code.

5.4. Algorithmic complexity

Computer programmers are often concerned with two questions:

a) How much time does an algorithm need to complete?

b) How much memory does an algorithm need for its computation?

Big \(O\) notation is a standard way, mathematicians and computer scientists use to describe how much time and how much memory is required for an algorithm to run

Big \(O\) is typically used to analyze the worst case complexity of an algorithm. If, for example, \(n\), is the size of the input data, then Big \(O\) really only cares about what happens when your input data size, \(n\), becomes arbitrarily large and not quite as interested in when the input is small. Mathematically, we want to speak of complexity in the asymptotic sense, that \(n\) is arbitrarily large. In this asymptotic sense of large \(n\), we may ignore constants.

The size of the input complexities ordered from smallest to largest:

  • Constant Complexity: \(O(1)\)

  • Logarithmic Complexity: \(O(log (n))\),

  • Linear Complexity: \(O(n)\)

  • Linearithmic Complexity: \(O(nlog (n))\),

  • Radical complexity : \(O(\sqrt{n})\)

  • Quadratic complexity: \(O(n^2)\)

  • Cubic complexity: \(O(n^3)\),

  • Exponential complexity: \(O(b^n)\), \( b > 1\)

  • Factorial complexity: \( O(n!)\)

Radical growth is larger than logarithmic growth:

geometricsequence

Polynomial growth is larger than radical growth:

geometricsequence

Exponential growth is larger than polynomial growth:

geometricsequence

Factorial growth is larger than exponential growth:

geometricsequence

Using the graphical analysis of the growth of typical functions we observe that we have the following growth ordering,

\$1,log \ ⁡n, root(3)(n), sqrt x , n, n^2, n^3,2^n,3^n,n!, n^n\$

The asymptotic behavior for large \(n\), should be determined by the most dominant term, in the function for large \(n\). For example, \(f(x)=x^{3} + 2x^{2}-2x\) , for large \(x\), is dominated by the term \(x^3\). In this case we want to state that \(O(f(x))=x^3\). For example \(f(1000) =1.001998×10^9≈ 1×10^9 =1000^3\). For large \(x\), \(f(x) ≈x^3\), or asymptotically \(f(x)\) behaves as \(x^3\), for large \(x\). We say \(O(f(x))=x^3\) , for \(f(x)=x^3 +2x^2-2x\).

Likewise we want to say that if \(c\) is a constant that \(c \cdot f(x)\), and \(f(x)\) have the same asymptotic behavior for large \(n\), or \(O(c \cdot f(x))=O(f(x))\).

Motivated by these we define the Big \(O\) notation,

Definition of Big \(O\) notation

Suppose \(f\) and \(g\) are real valued functions from \(f(x):\mathbb{R}→\mathbb{R}\), we say \(f(x)\) is Big \(O\) of \(g(x\)), written \(f(x)\), is, \(O(g(x))\), if there exists positive integers, \(A\), and \(n\), so that \(|f(x)| ≤ A|g(x)|\) whenever \(x > n\).

To determine if a function \(f(x)\) is \(O(g(x))\), amounts to identifying the, positive constants \(A\), and \(n\), (sometimes called witnesses). That is, we must find the factor \( A\) and the point, \( k \), for which \( f(x) ≤ A g(x)\), whenever \( x > k.\)

Example:

Consider \(f\left(x\right)=2x^2 +4x\), while intuitively we may understand that the dominant term for large \(x\), is \(x^2\) so that \(f(x) = O\left(x^2\right)\), we show this formally by producing as witnesses, \(A=3\) and \(n =4\) with reference to the following graph,

geometricsequence

Example:

Show that \(f(x) =2x^3 +3x\), is \(O(x^3)\), with \(A=3\) and \(n=2\). Support your answer graphically. Solution:

Notice that \( x^3 > 3x\), when \( x ≥ 2\). This means \(2x^3 +x^3 > 2x^3 +3x \), when \(x >2 \). In other words \( 3x^3 > 2x^3 +3x\), whenever \( x>2\), confirming \(A=3\), and \(n=2\), as witnesses, and supported by the following graph.

geometricsequence

To show that a function \( f(x)\), is not \(O(g(x))\), means that no \(A\) can scale \(g(x)\), so that \( Ag(x) ≥ f(x)\) for \(x\) large enough.

Example: Show that \( f(x) = x^2\), is not \( O( \sqrt{x})\)

Solution Consider the graphs of \( \sqrt{x}\), \( 2 \sqrt{x}\), \( 3\sqrt{x}\), and the graph of \(x^2\). Notice that eventually, or for \(x\) large enough, \(x^2\) is larger than any \(A \sqrt{x}\) as in the figure below

geometricsequence

Suppose \(A>1\), is given, and fixed, then if \( f(x) = x^2\) is \( O(g(x))=O( \sqrt{x})\) , there is some \(n\) for which \(A \sqrt{x} ≥ x^2\) whenever \(x>n\). Well \( g(x) =A \sqrt{x} = x^2=f(x) \), when \( x =A^{2/3}\), but then \(A \sqrt{x} < x^2\) when \( x > A^{2/3}\), hence no such \(n\), can exist for a given fixed \(A\). For example consider \(g(x)=A \sqrt{x}\) and \( f(x) =x^2 \), when \( x= A^2\), we obtain, \( g(A^2) = A \sqrt{(A^2)}= A^2\), and \( f(A^2) = {\left ( {A}^2 \right )}^2\), and \( f(A^2)= A^4 > A^2 = g(A^2) \), when \(A>1\).

Properties of Big \(O\) notation. Suppose \(f(x)\) is \(O(F(x))\) and, \(g(x)\) is \(O(G(x))\)

  1. \(c \cdot f(x)\) is \(O(F(x))\),

  2. \( f (x )+g(x)\) is \(O(max \left ( F(x), G(x) \right )\)

  3. \( f (x ) \cdot g(x))\) is \(O(F(x) \cdot G(x))\)

We can use these properties to show for instance \( 2x^2\) is \(O\left(x^2\right)\). Likewise if \(f(x) =2x^2\), and \(g(x) =4x\), then \( 2x^2\) is \(O(x^2)\), and \( 4x\) is \(O(x)\), and the maximum gives that \(2x^2+4x\) is \( O(max(x^2, x)) =O(x^2)\).

It is true in general that if a polynomial \(f(x)\) has degree \(n\) then \(f(x)\) is \(O(x^n)\).

Fact:

\(p(x)=a_nx^n +a_{n-1}x^{n-1} +a_{n-2}x^{n-2}+\ldots +a_2x^2 +a_1x^1+a_0\), is \(O(x^n)\)

For example, if \(f(x)= x^3+1\), being, \( O(x^3)\) and \(g(x)=x^2-x\), being \(O(x^2)\) then \(f(x) \cdot g(x)\) is \(O(x^3 \cdot x^2) =O(x^5)\), which is verified explicitly by multiplying \(f(x) \cdot g(x)= (x^3+1) \cdot (x^2-x)= x^5 -x^4+x^2-x \), which clearly is \(O(x^5)\)

Example In the graph below, using a logarithmic scale, we summarize the growth ordering of important functions, including logarithmic, polynomial, exponential, and factorial.

geometricsequence

Example: Order the following functions by growth. \(n⋅log_2⁡ n\) , \(n^2\), \(n^{4/3}\). Solution: Recall the ordering,

Notice that

\(n⋅log_{2⁡}n=n×log_{2⁡}n\)

\(n^2=n×n\)

\(n^{4/3} =n×n^{1/3}\)

Using the following ordering, \(log n\), \(n^{1/3}\), \(n\), we obtain also the following ordering, \(n⋅logn\), \(n^{4/3}\), \(n^2\).

5.4.1. Exercises

  1. Give big O estimates for

    1. \(f\left(x\right)=4\)

    2. \(f\left(x\right)=3x-2\)

    3. \(f\left(x\right)=5x^6-4x^3+1\)

    4. \(f\left(x\right)=2\ \ \sqrt x+5\)

    5. \(f\left(x\right)=x^5+4^x\)

    6. \(f\left(x\right)=x\log{x}+3x^2\)

    7. \(f\left(x\right)=5{x^2e}^x+4x!\)

    8. \(f\left(x\right)=\frac{x^6}{x^2+1}\) (Hint use long division)

  2. Give big O estimates for

    1. \(f\left(x\right)=2^5\)

    2. \(f\left(x\right)=5x-2\)

    3. \(f\left(x\right)=5x^8-4x^6+x^3\)

    4. \(f\left(x\right)=\) \$4 root(3)(x)+3\$

    5. \(f\left(x\right)=3^x+4^x\)

    6. \(f\left(x\right)=x^2\log{x}+5x^3\)

    7. \(f\left(x\right)=5{x^610}^x+4x!\)

    8. \(f\left(x\right)=\frac{x^5+2x^4-x+2}{x+2}\) (Hint use long division)

  3. Show using the definition, that \(f\left(x\right)=3x^2+5x\) is \(O(x^2)\), with \(A=4\), and \(n=5\). Support your answer graphically also.

  4. Show using the definition, that \(f\left(x\right)=x^2+6x+2\) is \(O(x^2)\), with \(A=3\), and \(n=6\). Support your answer graphically also.

  5. Show using the definition, that \(f\left(x\right)=2x^3+6x^2+3\) is \(O(x^2)\). State the witnesses \(A,\ n\), and support your answer graphically also.

  6. Show using the definition, that \(f\left(x\right)=\ {3x}^3+10x^2+1000\) is \(O(x^2)\). State the witnesses \(A,\ n\), and support your answer graphically also.

  7. Show that \(f\left(x\right)=\sqrt x\), is \(O\left(x^3\right)\), but \(g\left(x\right)=x^3\), is not\(\ O(\ \sqrt x)\).

  8. Show that \(f\left(x\right)=\sqrt x, is O\left(x\right)\), but \(g\left(x\right)=x\), is not\(\ O(\ \sqrt x)\).

  9. Show that \(f\left(x\right)=\) \$root(3)(x)\$, is \(O\left(x^2\right)\), but \(g\left(x\right)=x^2\), is not $ \$O( root(3)(x))\$

  10. Show that \(f\left(x\right)=\) \$root(3)(x)\$ is \(O\left(x\right)\), but \(g\left(x\right)=x\), is not \$root(3)(x)\$.

  11. Order the following functions by growth \(x^\frac{7}{3},\ e^x,\ 2^x,\ x^5,\ 5x+3,\ 10x^2+5x+2,\ x^3,\log{x,\ x^3\log{x}}\)

  12. Order the following functions by growth \(\ 3x!,\ {10}^x,\ x\cdot\log{x},\ \log{x\cdot\log{x,\ \ }2x^2+5x+1,\ \pi^x,x^\frac{3}{2}\ },\ 4^5,\ \ \sqrt{x\ }\cdot\log{x}\)

  13. Consider the functions, \(f\left(x\right)=2^x+2x^3+e^x\log{x}\), and \(g\left(x\right)=\sqrt x+x\log{x}\). Find the best big O estimates of,

    1. \((f+g)(x)\)

    2. \((f\cdot\ g)(x)\).

  14. Consider the functions, \(f\left(x\right)=2x+3x^3+5\log{x}\), and \(g\left(x\right)=\sqrt x+x^2\log{x}\). Find the best big O estimates of

    1. \((f+g)(x)\),

    2. \((f\cdot\ g)(x)\).

  15. State the definition of \( f(x)\), being \( O(g(x))\), using logical quantifiers and, \( A \), and \( n\).

  16. Negate the definition of \( f(x)\), being \( O(g(x))\), using logical quantifiers, and then state in words what it means that \( f(x)\) is not \( O(g(x))\)

5.5. Examples of Algorithms

We now proceed to develop some algorithms beginning with algorithms for common mathematical operations. Much of mathematical notation can be considered pseudocode

5.5.1. Example — Sum Notation

Consider, for example, the sum,

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

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

A pseudocode description might be,

Procedure Sum Notation

Computes the sum of the first, \(n\), terms of the sequence \( \{a_i\} \)

Input: A positive integer, \(n\), and a sequence \( \{a_i\}\)

Output: The sum of the first \(n\) terms of the sequence \(\{a_i \}\)

procedure Sum_Notation( n, {a_1, a_2, …, a_n} )
begin
  Sum = 0
  for i = 1 to n do
    Sum = Sum + a_i
  end
  return Sum
end
Sum notation in Python

The Python code below uses a for loop to implement sum notation, adding the first \(n\) terms of a sequence, \(a=(a_i)\).

5.5.2. Example — Exponentiation

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 .

A pseudocode implementation of the algorithm might be:

Procedure Exponentiation

Computes the exponent \(b^n\)

Input: A positive integer, \(n\) and a positive base, \(b\)

Output: \(b^n\)

procedure Exponentiation(n, b)
begin
  Power = 1
  for i = 1 to n do
    Power = Power * b
  end
  return Power
end
Exponentiation in Python

The Python code below uses a for loop to implement exponentiation, multiplying,a positive base, \(b\), with itself \(n\), times.

5.5.3. Example — Factorial notation (\(n!\)).

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

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

We leave it as an exercise to complete the pseudocode for the factorial, function \(n!\), but provide the Python syntax.

Procedure Factorial

Computes \(n!\), for a positive integer, \(n\)

Input: A positive integer, \(n\)

Output: \(n! = 1 * 2 * 3 … (n-1) * (n)\)

procedure Factorial(n)
begin
  . . .
  return n!
end
Factorial (\(n!\)) in Python

The Python code below uses a for loop to implement \(n!\), by iteratively multiplying.

5.5.4. Example — Finding the minimum in a list of integers

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

The algorithm would be constructed as follows:

  1. We define a variable \(min\) and assign it to the first indexed element in the list.

  2. Traverse along the list to the next indexed element and compare that indexed element in the list with the currently assigned value of the variable \(min\). If the inspected element is smaller than the currently assigned value of \(min\), then, update the value of \(min\).

  3. Repeat the previous step if there are more elements in the list to inspect and compare.

  4. Stop when the entire list has been traversed and all elements in the list have been inspected and compared against the variable \(min\).

A pseudocode description might be.

Procedure Minimum

Computes the minimum of a set of, \(n\), integers \(\{a_1, a_2, ..., a_n\}\)

Input: A set of, \(n\), integers \(\{a_1, a_2, ..., a_n\}\)

Output: \( min(\{a_1, a_2, ..., a_n\}) \)

procedure Minimum({a_1, a_2, …, a_n})
begin
  min = a_1
  for i = 1 to n do
    if (a_i < min) then do
      min = a_i
    end
  end
  return min
end
Minimum in Python

The Python code below uses a for loop to implement an algorithm to find the minimum in a set of \(n\), integers.

5.5.5. Example — A linear Search Algorithm

A linear search algorithm involves searching for a target integer, \(x\), in a list of distinct integers \( (a_1, a_2, ..., a_n)\), and returns the location, \(i\), in the list that the target element \(x\) is found in, or returns a value indicating that the target element, \(x\), is not in the list \( (a_1, a_2, ..., a_n)\).

Procedure Linear_search

Returns the location or position of a target integer, \(x\), in a set of distinct integers, \(a\), or if \(x\) is not in the set of distinct integers, returns the value -1.

Input: \(x\), the search target integer, and a set of \(n\) distinct integers \(\{a_1, a_2, ..., a_n\}\)

Output: The location index, \(i\), of the target element, \(x\), if it is in the set of distinct integers, \(\{a_1, a_2, ..., a_n\}\) , or, \(-1\), if the \(x\) is not in \(\{a_1, a_2, ..., a_n\}\).

procedure Linear_Search(x, {a_1, a_2, …, a_n})
begin
  for i = 1 to n do
    if (ai == x) then do
      return i
    end
  end
  return -1
end
Python Linear Search Algorithm

The Python code below uses a for loop to implement the linear search algorithm, searching, for the target integer \(x\), in a list of distinct integers \(a_i\), returning the position \(i\), of the list where the target \(x\) is found or returning \(-1\), if the target is not in the list \(a_i\).

5.5.6. Example — The Bubble Sort Algorithm

The bubble sort algorithm is a simple sorting procedure. It is typically used to sort an array of \(n\) data elements in either increasing or decreasing order. We describe the bubble sort algorithm for arranging a list of \(n\) real numbers in increasing order. The algorithm compares the first two elements of the array and swaps them if they are out of order. It continues by traversing up the array comparing each pair of adjacent elements and swaps them if they are out of order until we reach the last entry in the array at location \(n\). The last entry in the array will then be the largest element of the original list. After the largest element has been sorted into position \(n\), the algorithm continues by again comparing the first two elements and swapping if they are out of order. Continue traversing the array and comparing and swapping adjacent elements that are out of order until position \(n-1\) of the array, after which the 2nd largest element is in position \(n-1\). The elements, now at positions \(n\), and \(n-1\), are sorted. Continue to sort at positions \(n-2\), then \(n-3\) until position \(1\).

A pseudocode description of the algorithm is simple:

Procedure BubbleSort

Sorts a list of, \(n\), real numbers, \(\{a_1, a_2, ..., a_n\}\) in ascending order

Input: A set of, \(n\), real numbers , \(\{a_1, a_2, ..., a_n\}\) , with \(n>1\)

Output: A sorted list \(\{a_1, a_2, ..., a_n\}\) in ascending order

procedure BubbleSort({a_1, a_2, …, a_n})
begin
  for i = 1 to n - 1 do
    for j = 1 to n - i do
      if ( aj > aj+1 ) then do
        swap aj, aj+1
      end
  end
end
Python implementation of the Bubble Sort Algorithm

The Python code below uses two for loops to implement the Bubble Sort as found in the pseudocode description.

Bubble sort example

As an example we consider explicitly the steps of the Bubble Sort Algorithm to sort \(6, 2, 5, 3, 4, 1, \) in increasing order.

First Pass

\(\left(\mathbf{6}\ \mathbf{2}\ 5\ 3\ 4\ 1\right)\rightarrow\ \left(\mathbf{2}\ \mathbf{6}\ 5\ 3\ 4\ 1\right)\ \) compare and swap

\(\left(2\ \mathbf{6}\ \mathbf{5}\ 3\ 4\ 1\right)\rightarrow\ \left(2\ \mathbf{5}\ \mathbf{6}\ 3\ 4\ 1\right)\ \) compare and swap

\(\left(2\ 5\ \mathbf{6}\ \mathbf{3}\ 4\ 1\right)\rightarrow\ \left(2\ 5\ \mathbf{3}\ \mathbf{6}\ 4\ 1\right)\ \) compare and swap

\(\left(2\ 5\ 3\ \mathbf{6}\ \mathbf{4}\ 1\right)\rightarrow\ \left(2\ 5\ 3\ \mathbf{4}\ \mathbf{6}\ 1\right)\ \) compare and swap

\(\left(2\ 5\ 3\ 4\ \mathbf{6}\ \mathbf{1}\right)\rightarrow\ \left(2\ 5\ 3\ 4\ \mathbf{1}\ \mathbf{6}\right)\ \) compare and swap

Second pass

\(\left(\mathbf{2}\ \mathbf{5}\ 3\ 4\ 1\ 6\right)\rightarrow\ \left(\mathbf{2}\ \mathbf{5}\ 3\ 4\ 1\ 6\right)\ \) compare and no swap

\(\left(2\ \mathbf{5}\ \mathbf{3}\ 4\ 1\ 6\right)\rightarrow\ \left(2\ \mathbf{3}\ \mathbf{5}\ 4\ 1\ 6\right)\ \) compare and swap

\(\left(2\ 3\ \mathbf{5}\ \mathbf{4}\ 1\ 6\right)\rightarrow\ \left(2\ 3\ \mathbf{4}\ \mathbf{5}\ 1\ 6\right)\ \) compare and swap

\(\left(2\ 3\ 4\ \mathbf{5}\ \mathbf{1}\ 6\right)\rightarrow\ \left(2\ 3\ 4\ \mathbf{1}\ \mathbf{5}\ 6\right)\ \) compare and swap

Third pass

\(\left(\mathbf{2}\ \mathbf{3}\ 4\ 1\ 5\ 6\right)\rightarrow\ \left(\mathbf{2}\ \mathbf{3}\ 4\ 1\ 5\ 6\right)\ \) compare and no swap

\(\left(2\ \mathbf{3}\ \mathbf{4}\ 1\ 5\ 6\right)\rightarrow\ \left(2\ \mathbf{3}\ \mathbf{4}\ 1\ 5\ 6\right)\ \) compare and no swap

\(\left(2\ 3\ \mathbf{4}\ \mathbf{1}\ 5\ 6\right)\rightarrow\ \left(2\ 3\ \mathbf{1}\ \mathbf{4}\ 5\ 6\right)\ \) compare and swap

Fourth Pass

\(\left(\mathbf{2}\ \mathbf{3}\ 1\ 4\ 5\ 6\right)\rightarrow\ \left(\mathbf{2}\ \mathbf{3}\ 1\ 4\ 5\ 6\right)\ \) compare and no swap

\(\left(2\ \mathbf{3}\ \mathbf{1}\ 4\ 5\ 6\right)\rightarrow\ \left(2\ \mathbf{1}\ \mathbf{3}\ 4\ 5\ 6\right)\ \) compare and swap

Fifth Pass

\(\left( \mathbf{2}\ \mathbf{1}\ 3\ 4\ 5\ 6)\rightarrow\ (\mathbf{1}\ \mathbf{2}\ 3\ 4\ 5\ 6)\right)\ \) compare and swap

5.5.7. Example — The Insertion Sort Algorithm

The insertion sort scans through each element of the list using an outer loop with a variable, say, \(i\). At each stage the list is divided into a sorted section, say the left section, and a section that is not sorted, say the right. The location up to which the list is sorted, is denoted by a pointer or index, called a key. At the current stage, the next element from the unsorted section, on the right, is inserted into its appropriate position in the sorted section on the left. The process of inserting smaller elements in the left involves shifting, larger elements to the right, using a variable, say \(j\).

A pseudocode implementation of the Insertion Sort Algorithm might be,

_____________________________________________________________________

Procedure InsertionSort: sorts a list of, n, real numbers, {a1, a2, …, an }

in ascending orders

_____________________________________________________________________

Input: A set of, n, real numbers , {a1, a2, …, an } , with n>1

_____________________________________________________________________

Output: A sorted list {a1, a2, …, an } in ascending order

_____________________________________________________________________

procedure InsertionSort ( a = {a1, a2, …, an } : n real numbers with n>1 )

begin

for i = 1 to n - 1 do

key = ai

j = i-1

while j ≥ 0 and aj > key do

aj+1 = aj

j = j-1

end

aj+1 = key

end

end

____________________________________________________________________

 

 

A Python implementation of the Insertion Sort Algorithm is given below:

Insertion sort in Python

The Python code below uses a for loop and a nested while loop to implement the Insertion Sort Algorithm.

Example—​the Insertion Sort Algorithm

As an example we consider explicitly the steps of the Insertion Sort Algorithm to sort \(6, 2, 5, 3, 4, 1, \) in increasing order. The key, boundary, between the sorted and unsorted portions is denoted by the vertical bar or pipe character.

First pass

\((\underbrace{\mathbf{6}\ |\ \mathbf{2}}\ 5\ 3\ 4\ 1)\) compare and insert

Second pass

\((2\ \underbrace{\mathbf{6}\ |\ \mathbf{5}}\ 3\ 4\ 1)\) compare and insert

\((\underbrace{\mathbf{2}\ \mathbf{5}}\ |\ 6\ 3\ 4\ 1)\) compare and do not insert

Third pass

\((2\ 5\ \underbrace{\mathbf{6}\ |\ \mathbf{3}}\ 4\ 1)\) compare and insert

\((2\ \underbrace{\mathbf{5}\ \mathbf{3}}\ |\ 6\ 4\ 1)\) compare and insert

\((\underbrace{\mathbf{2}\ \mathbf{3}}\ 5\ |\ 6\ 4\ 1)\) compare and do not insert

Fourth pass

\((2\ 3\ 5\ \underbrace{\mathbf{6}\ |\ \mathbf{4}}\ 1)\) compare and insert

\((2\ 3\ \underbrace{\mathbf{5}\ \mathbf{4}\ }|\ 6\ 1)\) compare and insert

\((2\ \underbrace{\mathbf{3}\ \mathbf{4}}\ 5\ |\ 6\ 1)\) compare and do no insert

Fifth pass

\((2\ 3\ 4\ 5\ \ \underbrace{\mathbf{6}\ |\ \mathbf{1}})\) compare and insert

\((2\ 3\ 4\ \underbrace{\mathbf{5}\ \mathbf{1}}\ |\ 6)\) compare and insert

\((2\ 3\ \underbrace{\mathbf{4}\ \mathbf{1}}\ 5\ |\ 6)\) compare and insert

\((2\ \underbrace{\mathbf{3}\ \mathbf{1}}\ 4\ \ 5\ |\ 6)\) compare and insert

\((\underbrace{\mathbf{2}\ \mathbf{1}\ }3\ 4\ \ 5\ |\ 6)\) compare and insert

\(( 1\ 2\ \ 4\ \ 5\ |\ 6)\)

5.5.8. Example — The Binary Search Algorithm

The binary search algorithm searches a sorted array \(n\) of integers for a target value \(t\). The algorithms assumes \(t\) is in the middle of the array. If it does not find \(t\) in the middle, it considers either the first half or the second half. It continues recursively splitting the search space in half until it either finds \(t\) or fails.

A pseudocode description of the algorithm is below:

Procedure BinarySearch

Searches a list of, \(n\), sorted real numbers, \(\{a_1, a_2, ..., a_n\}\).

Input: A set of, \(n\), real numbers, \(\{a_1, a_2, ..., a_n\}\) sorted in ascending order and a target value \(t\) to search for.

Output: The index (position) of \(t\) if found, otherwise -1.

procedure BinarySearch({a_1, a_2, …, a_n}, t)
begin
    L = 1
    R = n
    while L ≤ R do
        m = floor((L + R) / 2)
        if a_m < t then do
            L = m + 1
        end
        else if a_m > t then do
            R = m - 1
        end
        else then do
            return m
        end
    end
    return -1
end
Python implementation of the Binary Search Algorithm

The Python code below implements the binary search algorithm found in the pseudocode description.

5.6. Recursive Algorithms

Algorithms or procedures may invoke other procedures. A procedure that calls itself is said to be a recursive procedure.

One way to think of recursive procedures, is as procedures, which reduce tasks to instances of the same tasks with smaller numbers of inputs.

We illustrate with some basic examples. The first few examples are intended mainly to introduce the concept of recursion and are not necessarily the most efficient or intuitive ways to implement the given tasks. Recursive methods, then, are to be contrasted with iterative methods.

5.6.1. Example 1 Recursive implementation of factorial

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

Recall, for example, 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)!\ \)

A recursive implementation of the factorial procedure in pseudocode would be, to be contrasted with the iterative implementation in section (???)

_____________________________________________________________________

Procedure RFactorial: computes n!, for n, a positive integer, recursively

_____________________________________________________________________

Input: A nonnegative integer, n.

_____________________________________________________________________

Output: n! = 1*2*3…(n-1)*(n)

_____________________________________________________________________

Procedure RFactorial( n )

begin

if n==0 then do

return 1

else do

return n*Rfactorial(n-1)

end

end

____________________________________________________________________

 

A recursive implementation of the factorial function in Python is given below

Recursive implementation of factorial function, \(n!\), in Python

The Python code below implements the factorial function \(n!\), recursively.

5.6.2. Example Recursive implementation of the power function \(b^n\)

As another simple example, we consider a recursive implementation of the exponentiation \(b^n\) with \(n\) a nonnegative integer and \(b>0\) and \(b \neq 1\). Consider for example \(5^4=5\ {\cdot\ 5}^3\) Hence we can recursively define exponentiation,

\(b^0=1\)

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

A pseudocode recursive implementation of the power function or exponential function \(b^n\), would be

______________________________________________

Procedure Rexponentiation: recursively computes the

exponent bn

______________________________________________

Input: A nonnegative integer, n and a positive base

______________________________________________

Output:

______________________________________________

procedure Rexponentiation(n, b)

begin

if n==0 then do

return 1

else do

return b*Rexponentiation(n-1)

end

end

______________________________________________

 

5.6.3. Example: Recursively defined arithmetic sequences.

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,

______________________________________________

Procedure Rarithmetic: recursively computes the nth term

of the arithmetic sequence with first term, a and

common difference, d.

______________________________________________

Input: A positive integer, n and the first term, a, and

common difference, d, of an arithmetic sequence

______________________________________________

Output:

______________________________________________

procedure Rarithmetic(n, a, d)

begin

if n==1 then do

return a

else do

return d + Rarithmetic(n – 1, a, d)

end

end

______________________________________________

 

5.6.4. Recursive generation of the Fibonnacci sequence

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

\(f_1=1\)

\(f_2=1\)

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

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

Recursive implementation in Python to find the \(n^{th}\) Fibonacci number.

The Python code below uses the recursive relationship \(f_n = f_{n-1}+f_{n-2}\), to calculate the \(n^{th}\) Fibonacci number.

5.7. Algorithmic complexity

In this section we give time complexity using big 0 notation of some of the important algorithms in this section. Recall big \(O\) notation is used to quantify the worst case an algorithm performs on a data input size of n.

5.7.1. Example 1: The Linear search algorithm is \(O(n)\).

The linear search algorithm iterates across the list of \(n\) data elements. With reference to pseudocode for the linear search algorithm if the first element in the list is the target element, the algorithm stops, otherwise, move to the next element and continue repeatedly over 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.

5.7.2. Example 2: The Bubble sort and Insertion sort algorithms are both \(O(n^2)\).

we analyze the Bubble Sort algorithm beginning with a concrete list size of \(n=5\) and generalize the analysis, leaving the case of the Insertion Sort algorithm as an exercise. 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 fourt pass, there will be 1 comparisons 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+...+n-1= \frac{(n-1)\cdot\ n}{2}=\frac{n^2}{2}-\frac{n}{2}\), which is \(O(n^2)\).

5.7.3. Example 3: The Binary search algorithm is \(O(\log{n})\).

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 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, \(a_m\) 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 after splitting down to 1 element in the search and determine that the target element is not in the search list.

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 of order \(O(p)\).

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

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

The bubble sort algorithm then is \(O(p)=O(\log{n})\).

5.8. Exercises

  1. Explain why the insertion sort algorithm is \(o(n^2)\).

  2. Write a recursive procedure in pseudocode to implement the binary search algorithm.

  3. A binary string of length n is a sequence of \(0^\prime s\) and \(1^\prime s\) of length \(n\). For example all binary strings of length 2 are \(00,\ 01,\ 10,\ 11\), and all binary strings of length 3 are \(000,\ 001,\ 010,\ 011,\ 100,\ 101,\ 110,\ 111\). Write a recursive algorithm in pseudocode to generate all binary strings of length \(n\).

  4. Write a recursive procedure in pseudocode to generate the following sequence, which is a variation of the Fibonacci sequence, \begin{array}{c} a_1=1 \\ a_2=1 \\ a_n=a_{n-1}+2a_{n-2} \end{array}

  5. Write a recursive procedure in pseudocode to generate the following sequence, which is a variation of the Fibonacci sequence, \begin{array}{c} b_1=2 \\ b_2=3 \\ b_n=b_{n-1}\cdot\ b_{n-2} \end{array}

  6. Write a recursive procedure in pseudocode to generate the following sequence, which is a variation of the Fibonacci sequence, \begin{array}{c} c_1=5 \\ c_n={2c}_n+n \end{array}

  7. Recall the median of a set of numbers is the number in the middle of the ordered set of numbers. If the sorted data set \(\left\{a_1,a_2,\ldots,\ a_n\right\}\) has an odd number of elements, the median is \(a_M\), where \(M=\left\lceil \frac{n}{2}\right\rceil\). For example, the set, sorted in descending order \(a_1=10,\ a_2=10,\ a_3=7,\ a_4=6,\ a_5=2\), has median \(a_3=7\). If the sorted data set \(\left\{a_1,a_2,\ldots,\ a_n\right\}\) has an even number of elements, the median \(a_M\) is the average of \(a_\frac{n}{2}\) and \(a_{\frac{n}{2}+1}\). For example, the set, sorted in descending order \(a_1=10,\ a_2=10,\ a_3=7,\ a_4=6,\ a_5=2,\ a_6=0\), has median \(\frac{\left(a_3+a_4\right)}{2}=\frac{7+6}{2}=6.5\). Write an algorithm in pseudocode to calculate the median of a data set by first sorting in decreasing order.

  8. Give big O estimates for

    1. \(f\left(x\right)=2^5\)

    2. \(f\left(x\right)=5x-2\)

    3. \(f\left(x\right)=5x^8-4x^6+x^3\)

    4. \(f\left(x\right)=\) \$4 root(3)(x)+3\$

    5. \(f\left(x\right)=3^x+4^x\)

    6. \(f\left(x\right)=x^2\log{x}+5x^3\)

    7. \(f\left(x\right)=5{x^610}^x+4x!\)

    8. \(f\left(x\right)=\frac{x^5+2x^4-x+2}{x+2}\) (Hint use long division)

6. Counting

6.1. Counting Principles

There are three basic counting rules used in this section, one for each of the arithmetic operations of multiplication, addition and subtraction.

6.1.1. The Product Rule (and)

The Product Rule
If there are \(n\) ways event \(E\) can occur and \(m\) ways to event \(F\) can occur, where the occurance of \(E\) has no effect on \(F\), then there are \(nm\) ways \(E\) and \(F\) can occur. The product rule can be extended to more than two choices.
Examples

Example: A startup with four employee rents an office suite with seven offices. How many ways are there to assign the employees?

Solution: The first employee has 7 offices to choose from, the second has 6 offices to choose from, the third can choose from 5, and the fourth can choose from 4. By the product rule, there are \(7 \times 6 \times 5 \times 4 = 840\) ways to assign the offices.

Product Rule

What will be the value of 'counter' when the following code is run?

Example: Suppose there are 27 computers in a computer center and each computer has 15 ports. How many different ways are there to choose a specific port?

Solution: Choosing a port means you first choose a computer and then a port on that computer. Since there are 27 computers and 15 ways to choose a port on a computer, there are \(27 \times 15 = 405\) ways to choose a port.

You Try: How many functions are there from a set \(A\) with \(m\) elements to a set \(B\) with \(n\) elements?

Video Example

6.1.2. The Sum Rule (xor)

The Sum Rule
If there are \(n\) ways event \(E\) can occur and \(m\) ways event \(F\) can occur, and suppose that both events cannot occur at the same time, then there are \(n + m\) ways for \(E\) or \(F\) to occur. The sum rule can be extended to more than two choices.
Examples

Example: A student in a Capstone course can choose a project from three different professors. The professors have 3, 7, and 4 possible projects, and no projects is on more than one professor’s list. How many possible projects can the student choose?

Solution: The student can pick out a project by choosing from the first professor, the second professor, or the third professor. Since no project is on more than one list, the sum rules says that there are \(3 + 7 + 4 = 14\) projects to choose from.

You Try: If a card is drawn from a standard 52-card deck, how many ways can the card be an even number or a King?

Video Example

6.1.3. The Subtraction Rule (or)

The Subtraction Rule
Suppose event \(E\) can occur \(n\) ways, event \(F\) can occur \(m\) ways, and there are \(p\) ways that \(E\) and \(F\) can occur. Then there are \(n+m-p\) ways \(E\) or \(F\) can occur. This is called the inclusion-exclusion principle.

Example: A tech company recieves 200 applications for a position. 150 of the applicants were ITEC majors, 43 were business majors, and 25 were double majors in business and ITEC. How many application did not major in ITEC or business?

Solution: By the subtraction rule, there are \(150 + 43 - 25 = 168\) applicants that majored in ITEC or business. Thus \(200 - 168 = 32\) majored in neither of these.

Example: How many bit strings of length four start with 1 or end with 00?

Solution: A bit string of length four that starts with 1 will be of the form \(1~*~*~*\). For each \(*\) there are two choices, 0 or 1, so there are \(2^3\) bit strings of this form by the product rule. A bit string of length four that ends with 00 will be of the form \(*~*~0~0\), so there are \(2^2\) bit strings of this form. Finally, a bit string of length four that starts with 1 and ends with 00 will be of the form \(1~*~0~0\), so there are 2 bit strings of this form. By the subtraction rule there are \(2^3 + 2^2 - 2 = 8+4-2=10\) possibilities.

You Try: If a card is drawn from a standard 52-card deck, how many ways can the card be black or a face card?

Examples

Video Example

6.1.4. Exercises

  1. There are 67 math majors and 124 ITEC majors at a college.

    1. In how many ways can two representatives be picked so that one is a math major and one is an ITEC major?

    2. In how many ways can one representative be picked who is either a math major or an ITEC major?

  2. A multiple-choice test contains 20 questions, and each question has four choices.

    1. In how many ways can a student answer all of the questions on the test?

    2. In how many ways can a student answer all of the questions if she is allowed to leave some blank?

  3. How many different three-letter initials can a person have?

  4. How many different three-letter initials end with "R"?

  5. How many bit strings are there of length five?

  6. How many bit strings are there of length five that begin and end with 1?

  7. How many bit strings are there of length less than \(n\), where \(n\) is a positive integer, that start and end with 1?

  8. How many license plates can be made using three digits followed by four uppercase English letters if:

    1. Digits and letters can be repeated?

    2. Digits and letters cannot be repeated?

  9. If each student in Discrete Mathematics is a mathematics major, an ITEC major, or a double major, and a class has 5 math majors (including double majors), 23 ITEC majors (including double majors), and 7 double majors, how many students are in the class?

  10. Suppose a computer system requires a password of length no less than 7 and no more than 10 characters, and each character must be an English lowercase letter, an English uppercase letter, a digit, or one of six special characters (*, >, <, !, +, =).

    1. How many different passwords are available?

    2. Suppose a hacker can check a potential password once every nanosecond (1 nanosecond is \(1 \times 10^{-9}\) seconds). How long will it take the hacker to check every potential password?

6.1.5. The Pigeonhole Principle

A suprising number of counting problems can be solved with the so-called pigeonhole principle.

Pigeon Hole Principles
If \(n+1\) pigeons are resting in \(n\) pigeonholes then at least one pigeonhold contains more than one pigeon.
pigeons

Ten pigeons in nine pigeonholes

Examples

Example : In a group of 367 people at least two will have the same birthday because there are only 366 possible birthdays (counting February 29).

You Try: How many people, with English names, must be in a room for two of them to have a first name that starts with the same letter?

6.1.6. Exercises

  1. Show that if there are 29 students in a class at least two have last names that begin with the same letter.

  2. How many students need to be in a class in order for at least two students to receive the same grade on an exam that is graded on a scale 0 to 100 points?

  3. Show that in any set of 5 integers, there are at least two of them that have the same remainder when divided by 4.

  4. A bag contains 8 red balls and 7 blue balls.

    1. How many balls must be chosen to be sure of choosing 3 of the same color?

    2. How many must be chosen to be sure of choosing 3 red balls?

  5. Someone cleaning out their attic finds a box containing 12 rock CDs and 12 country CDs. What is the minimum number of CDs they can take out to guarantee at least one of each type?

  6. Give an argument that there are at least two people in Atlanta with the same number of hairs on their head.

6.1.7. Permutations and Combinations

Consider the first four letters of the alphabet, \(A, B, C, D\). A permutation of these letters would be an arrangment of them in different orders.

  • \(ABCD, BACD, ABDC\) are permutations of the letters taken four at a time

  • \(BDA, ABC, ABD\) are permuations of the letters taken three at a time

  • \(AB, AC, DB\) are permutations of the letters taken two at a time

Permutations of 5 objects taken 3 at a time

Try to predict what happends with the code and verify.

In general, given a set of \(n\) objects, an ordered arrangment of \(r \le n\) of them is called an \(r\)-permutation or a permutation of \(n\) objects taken \(r\) at a time. We will denote this by \(P(n,r)\). (Note that \(_nP_r\) is a commonly used notation, especially on calculators.)

Theorem
\(P(n,r) = n(n-1)(n-2) \cdots (n-r+1) = \displaystyle \frac{n!}{(n-r)!}\).
Counting Permutations

The code below calculates the number of permutations given \(n\) and \(r\). Try to predict the variable names, values, and data types at different steps in the execution. Use the Forward button to check your answers.

Examples

Video Example

Example:

If there are 10 runners in a race, how many different ways can the gold, silver, and bronze medals be awarded?

Solution: There are 10 objects (the runners), and we chosing 3 to win medals. So the number of ways they can be awarded is

\(P(10,3) = \displaystyle \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10 \times 9 \times 8 = 720\)

Alternatively, we could have used the product and noticed that there are 10 ways to award the gold, then there are 9 ways to award the silver, then 8 ways to award the brozne.

Example: How many permutations of the digits 0123456789 are there that contain the string 456?

Solution: We can regard this as a permutation of 8 objects: the string 456 and the other 7 digits. Since they can occur in any order, the solutions is

\(P(8,8) = 8! = 40320.\)

You Try: From a group of 100 workers, how many ways can there be a union President, Vice President, and Treasurer?

You Try: How many different words (including nonsense words), can be formed using the letters in 'HEROIC' where the vowels much appear together?

Now consider the letters \(A, B, C, D\) and choose three at a time where the order does not matter. That is, the choice \(ABC\) is the same choice as \(BCA\). There are only four possible ways to choose three letters without regard to order: \(ABC, ABD, ACD,\) and \(BCD\).

In general, given a set of \(n\) objects, and unordered selection of \(r\le n\) of them is an \(r\)-combination or a combination of \(n\) objects taken \(r\) at a time. We will denote this by \(C(n,r)\). (Note that \(_nC_r\) is commonly used by calculators.) \(C(n,r)\) is commonly read as '\(n\) choose \(r\)'.

Theorem
\(C(n,r) = \displaystyle \frac{P(n,r)}{r!} = \frac{n!}{r!(n-r)!}\)
Combinations of 5 objects 3 at at time

The code below calculates the number of, and lists, combinations given \(n\) and \(r\). Try to predict the variable names, values, and data types at different steps in the execution. Use the Forward button to check your answers.

Examples

Video Example 1

Video Example 2

Example: How many ways can five cards be dealt from a standard 52-card deck?

Solution: We are choosing 5 cards from 52 cards and the order does not matter, so \(C(52,5)=\displaystyle \frac{52!}{5!47!}\)

Example: How many bit strings of length \(n\) contain exactly \(r\) 0s?

Solution: Choosing the positions of the \(r\) 0s corresponds to the \(r\)-combinations of the set \(\{1, 2, 3, \dots, n\}\). Thus there are exactly \(C(n,r)\) such bit strings.

6.1.8. Exercises

  1. List all the permutations of \(\{1, 2, 3\}\).

  2. How many permutations are there of the set \(\{1, a, 2, b, 3, c\}\)?

  3. Let \(A=\{a, b, c, d\}\)

    1. List all the 3-permutations of \(A\).

    2. List all the 3-combinations of \(A\).

  4. Find the value of the following

    1. \(P(5,2)\)

    2. \(P(10,8)\)

    3. \(P(14,10)\)

    4. \(C(5,2)\)

    5. \(C(10,8)\)

    6. \(C(14,10)\)

  5. How many bit strings of length 8 contain:

    1. Exactly four 1s?

    2. At most four 1s?

    3. At least four 1s?

    4. The same number of 0s and 1s?

  6. How many permutations of the digits \(1234567\) contain:

    1. The string 234?

    2. The string 3561?

    3. The string 21 and 54?

  7. How many ways are there to choose 7 cards from a standard 52 card deck?

  8. How many ways can you be dealt a pair in a 5 card hand (2 cards of the same rank and 3 cards of a different rank)?

  9. How many ways can you be dealt a full house in a 5 card hand (2 cards of the same rank and 3 cards of the same rank)?

  10. How many license plates consist of 4 letters followed by 3 digits if:

    1. Repetition is allowed?

    2. Repetition is not allowed?

  11. Using \(C(n,r) = \displaystyle \frac{n!}{r!(n-r)!}\), evaluate the terms of this triangular table. Will you need the formula to extend the table to more rows?

\begin{array}{ccccccccccccc} &&&&&&&C(0,0)&&&&&&\\ &&&&&& C(1,0) && C(1,1) &&&&&\\ &&&&& C(2,0) && C(2,1) && C(2,2) &&&&\\ &&&& C(3,0) && C(3,1) && C(3,2) && C(3,3) &&&\\ &&& C(4,0) && C(4,1) && C(4,2) && C(4,3) && C(4,4) &&\\ \end{array}

7. Number Theory

7.1. Divisibility

Let \(a\) be a nonzero integer and let \(b\) be an integer. We say that \(a\) divides \(b\) if and only if there is an integer \(c\) such that \(b = ac.\) If \(a\) divides \(b,\) then we use the following notation: \[a \mid b.\]If \(a\) does not divide \(b,\) then we use the following notation: \[a \nmid b.\] When \(a\) divides \(b,\) we say \(a\) is a divisor of \(b\) and that \(b\) is a multiple of \(a.\)

Example

Does \(3\) divide \(12\)? Does \(5\) divide \(27\)?

Solution

Since we have \[12 = 3 \cdot 4,\]we see that \(3 \mid 12.\) However, there is no integer \(c\) such that \[27 = 5c.\]This implies that \(5 \nmid 27.\)

There are several theorems that can be proven just using the definition of divisibility given above. One such theorem is as follows.

Theorem

Let \(a\) be a nonzero integer and let \(b\) and \(c\) be integers such that \(a \mid b\) and \(a \mid c.\) Then, for any integers \(x\) and \(y,\) \[a \mid \left(bx + cy\right).\]

7.1.1. Division Algorithm

Let \(a\) be an integer and let \(d\) be a positive integer. Then, there are unique integers \(q\) and \(r,\) with \(0 \leq r < d,\) such that \[a = dq + r.\]

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:

\[\begin{split} a \boldsymbol{\operatorname{\,div\,}} d &= q,\\ a \boldsymbol{\bmod} d &= r.\\ \end{split}\]
Example

Find \(129 \boldsymbol{\operatorname{\,div\,}} 7\) and \(129 \boldsymbol{\bmod} 7.\)

Solution

We have \[129 = 7 \cdot 18 + 3.\] This implies that \[129 \boldsymbol{\operatorname{\,div\,}} 7 = 18\] and \[129 \boldsymbol{\bmod} 7 = 3.\]

If \(a\) is an integer and \(d\) is a positive integer, it is not hard to see that

\[\begin{split} a \boldsymbol{\operatorname{\,div \,}} d &= \left\lfloor \frac{a}{d}\right\rfloor,\\ a \boldsymbol{\bmod} d &= a - \left\lfloor \frac{a}{d}\right\rfloor \cdot d. \end{split}\]

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.\)

Theorem

Let \(a\) be a positive integer and let \(b\) be an integer. Then \(a \mid b\) if and only if \(b \boldsymbol{\bmod} a = 0.\)

7.1.2. Greatest Common Divisor and Least Common Multiple

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.

Example

Find the greatest common divisor of \(35\) and \(21.\) Are \(35\) and \(21\) relatively prime?

Solution

Since \(35 = 7 \cdot 5\) and \(21 = 7 \cdot 3,\) we see that \(7\) is a common divisor of \(35\) and \(21.\) It can be checked that no positive integer larger than \(7\) that divides both \(35\) and \(21.\) Thus, we see that \[\gcd(35,21) = 7.\]Since \(\gcd(35,21) \neq 1,\) we see that \(35\) and \(21\) are not 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.

Theorem

Let \(a\) and \(b\) be positive integers. Suppose that \(d\) is a positive integer such that \(d \mid a\) and \(d \mid b.\) Then, \(d = \gcd(a,b)\) if and only if \(\frac{a}{d}\) and \(\frac{b}{d}\) are relatively prime.

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).\)

Example

Find the least common multiple of \(35\) and \(21.\)

Solution

Since \(105 = 35 \cdot 3\) and \(105 = 21 \cdot 5,\) we see that \(105\) is a common multiple of \(35\) and \(21.\) It can be checked that no positive integer smaller than \(105\) is a multiple of both \(35\) and \(21.\) Thus, we see that \[\operatorname{lcm}(35,21) = 105.\]

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.

Theorem

Let \(a\) and \(b\) be positive integers. Then, we have the following: \[\gcd(a,b) \cdot \operatorname{lcm}(a,b) = ab.\]

7.1.3. The Euclidean Algorithm

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.

Theorem

Let \(a,b,r,q\) be integers with \(a=bq+r\). Then, \[\gcd(a,b) = \gcd(b,r).\]

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

\[\begin{split} \gcd(a,b) = r_k,\\ \operatorname{lcm}(a,b) = \frac{ab}{r_k}.\\ \end{split}\]
Example

Find the greatest common divisor and least common multiple of \(480\) and \(174.\)

Solution

We have the following:

\[\begin{split} 480 &= 174 \cdot 2+ 132,\\ 174 &= 132 \cdot 1 + 42,\\ 132 &= 42 \cdot 3 + 6,\\ 42 &= 6 \cdot 7 + 0. \end{split}\]

Since we have reached a remainder of 0, we are finished. The last nonzero remainder we found was \(6.\) Thus, we see that \[\gcd(480,174) = 6,\]and that \[\operatorname{lcm}(480,174) = \frac{480\cdot 174}{6} = 13920.\]

Euclidean Algorithm

Here is an implementation in Python of the Euclidean algorithm as it computes \(\gcd(a,b)\) and \(\operatorname{lcm}(a,b).\)

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

\[\begin{split} 6 &= 132 - 42\cdot 3,\\ 42 &= 174 - 132\cdot 1,\\ 132 &= 480 - 174 \cdot 2. \end{split}\]

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

\[\begin{split} 6 &= 132 - 42 \cdot 3\\ &= 132 - (174 - 132\cdot 1)\cdot 3\\ &= 132 - 174 \cdot 3 + 132 \cdot 3\\ &= 132 \cdot 4 - 174 \cdot 3\\ &= (480 - 174\cdot 2)\cdot 4 - 174 \cdot 3\\ &= 480 \cdot 4 - 174 \cdot 8 - 174 \cdot 3\\ &= 480 \cdot 4 -174 \cdot 11\\ &= 480 \cdot 4 + 174 \cdot (-11). \end{split}\]

In general, we have the following theorem.

Theorem

Let \(a\) and \(b\) be positive integers. There exist integers \(x\) and \(y\) such that \[\gcd(a,b) = ax + by.\]

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

Extended Euclidean Algorithm

Here is an implementation in Python of the Extended Euclidean algorithm as it finds integers \(x\) and \(y\) such that \(ax + by = \gcd(a,b).\)

7.2. Integer Representations

Theorem

Let \(b\) be an integer greater than 1. Any positive integer \(n\) can be expressed uniquely in the form \[n = a_kb^k + a_{k - 1}b^{k-1} + \cdots + a_1b^1 + a_0b^0,\]where \(k\) is a nonnegative integer, \(a_0,a_1,\dots,a_k\) are nonnegative integers less than \(b,\) and \(a_k \neq 0.\)

Let \(b\) be an integer greater than 1 and let \(n\) be a positive integer. The representation of \(n\) in the above theorem is referred to as the base \(b\) expansion of \(n\). We refer to \(a_k,a_{k-1},\dots,a_0,a_1\) as digits. We represent the base \(b\) expansion of \(n\) using the following notation: \[(a_ka_{k-1}\dots a_1a_0)_b.\]

The base 10 expansion of a positive integer is referred to as the decimal expansion. When expressing the decimal expansion of a positive integer, we typically omit the subscript 10.

Example

What is the decimal expansion of the positive integer with base 7 expansion \((1063)_7\)?

Solution

We have

\[\begin{split} (1063)_7 &= 1 \cdot 7^3 + 0 \cdot 7^2 + 6\cdot 7^1 + 3 \cdot 7^0\\ &=1 \cdot 343 + 0 \cdot 49 + 6 \cdot 7 + 3 \cdot 1\\ &= 343 + 0 + 42 + 3\\ &= 388. \end{split}\]

Several common bases used in computer science are base \(2\), base \(8\), and base \(16\), which are referred to as binary, octal, and hexadecimal, respectively. Binary digits are often referred to as bits. Note that, when finding the hexadecimal expansion of a positive integer, in addition to the usual digits \(0\) through \(9,\) we require an additional 6 digits. We will represent these by the letters \(\mathrm{A}\) through \(\mathrm{F}\), where \((\mathrm{A})_{16} = 10,\) \((\mathrm{B})_{16} = 11,\) \((\mathrm{C})_{16} = 12,\) \((\mathrm{D})_{16} = 13,\) \((\mathrm{E})_{16} = 14,\) and \((\mathrm{F})_{16} = 15.\)

Example

Find the decimal expansion of the positive integer whose hexadecimal expansion is \((5\mathrm{B}\mathrm{F})_{16}.\)

Solution

We have

\[\begin{split} (5\mathrm{B}\mathrm{F})_{16} &= 5\cdot 16^2 + 11 \cdot 16^1 + 15 \cdot 16^0\\ &= 5\cdot 256 + 11 \cdot 16 + 15 \cdot 1\\ &= 1280 + 176 + 15\\ &= 1471. \end{split}\]

7.2.1. Base Conversion

Let \(b\) be an integer greater than \(1\) and let \(n\) be a positive integer. In order to find the base \(b\) expansion of \(n,\) we can use the following algorithm. First, we use the division algorithm to find integers \(q_0\) and \(a_0,\) with \(0 \leq a_0 < b,\) such that \[n = bq_0 + a_0.\]Then, if \(q_0 \neq 0,\) we again use the division algorithm to find integers \(q_1\) and \(a_1,\) with \(0 \leq a_1 < b,\) such that \[q_0 = bq_1 + a_1.\] Then, if \(q_1 \neq 0,\) we again use the division algorithm to find integers \(q_2\) and \(a_2,\) with \(0 \leq a_2 < b,\) such that \[q_1 = bq_2 + a_2.\]We continue this process until we obtain a quotient of \(0\); that is, until, for some positive integer \(k,\) we have \(q_k = 0.\) Then, we have \[n = (a_ka_{k-1}\dots a_1a_0)_b.\]

Example

Find the base \(6\) expansion for \(2235\).

Solution

We have

\[\begin{split} 2235 &= 6\cdot 372 + 3,\\ 372 &= 6 \cdot 62 + 0,\\ 62 &= 6 \cdot 10 + 2,\\ 10 &= 6\cdot 1 + 4,\\ 1 &= 6 \cdot 0 + 1. \end{split}\]

Since we have reached a quotient of \(0\), we are finished. Thus, we see that \[2235 = (14203)_6.\]

Suppose we want to convert the positive integer \(n\) from hexadecimal to binary. One method would be to first convert from \(n\) from hexadecimal to decimal, and the convert the result from decimal to binary. However, we can also take advantage of the fact that \(2^4 = 16.\) This implies that we can express each hexadecimal digit of \((n)_{16}\) uniquely as a block of 4 bits as follows:

\[\begin{array}{llll} (0)_{16} = (0000)_2 & (1)_{16} = (0001)_{2}& (2)_{16} = (0010)_2 & (3)_{16} = (0011)_2 \\ (4)_{16} = (0100)_2& (5)_{16} = (0101)_2& (6)_{16} = (0110)_2 & (7)_{16} = (0111)_2\\ (8)_{16} = (1000)_2& (9)_{16} = (1001)_2& (\mathrm{A})_{16} = (1010)_2& (\mathrm{B})_{16} = (1011)_2\\ (\mathrm{C})_{16} = (1100)_2& (\mathrm{D})_{16} = (1101)_2& (\mathrm{E})_{16} = (1110)_2& (\mathrm{F})_{16} = (1111)_2. \end{array}\]

We then concatenate our blocks, removing any leading zeros if necessary.

Example

Find the binary expansion of \((4\mathrm{C}\mathrm{A}7)_{16}.\)

Solution

We have the following:

\[\begin{array}{llll} (4)_{16} = (0100)_2 & (\mathrm{C})_{16} = (1100)_2 & (\mathrm{A})_{16} = (1010)_2 & (7)_{16} = (0111)_2. \end{array}\]

Thus, we see that \[(4\mathrm{C}\mathrm{A}7)_{16} = (100110010100111)_{2}.\]

To convert \(n\) from binary to hexadecimal, we simply break up \((n)_2\) into blocks of 4 binary digits, adding a suitable number of leading zeros if necessary. We convert each block of 4 bits to hexadecimal digits and concatenate our results, removing any leading zeros if necessary.

Example

Find the hexadecimal expansion of \((110 1011 1111)_2.\)

Solution

We have the following blocks of 4 bits: \[0110,\ 1011,\ 1111.\] Since \((0110)_2 = (6)_{16},\) \((1011)_2 = (\mathrm{B})_{16},\) and \((1111)_2 = (\mathrm{F})_{16},\) we see that \[(11010111111)_{2} = (6\mathrm{B}\mathrm{F})_{16}.\]

The following table can be used to covert quickly between decimal, hexadecimal, octal binary in a similar way.

Conversion table for different bases

baseconverstion

8. Sequences, Recursive Definitions, and Induction

8.1. Sequences, Series, and Sigma Notation

We make frequent use of special sets and these are denoted with special symbols.

\(\mathbb{Z}\) …​, -2, -1, 0, 1, 2,.. . , the set of integers
\(\mathbb{Z}+\) or \(\mathbb{N}\) 1, 2, 3,.. . , the set of natural numbers or positive integers
\(\mathbb{Q}\) p/q p \(\in \) \(\mathbb{Z}\), q \(\in \) \(\mathbb{Z}\) , and q \(\neq \) 0 , the set of rational numbers
\(\mathbb{R}\), the set of real numbers
\(\mathbb{R}\)+, the set of positive real numbers
\(\mathbb{C}\), the set of complex numbers.

Other special sets will be listed as used.

8.1.1. Sequences

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.

Example 1

The sequence \(a_n=f(n)=3n+1\), is the sequence generated by the linear function, \(f(x)=3x+1\), whose first 5 terms would, be,

\(a_1=\ 3\left(1\right)+1=4,\)

\(a_2=3\left(2\right)+1=7,\)

\(a_3=3\left(3\right)+1=10,\)

\(a_4=3\left(4\right)+1=13\)

\(a_5=3\left(5\right)+1=16\)

The same sequence may be defined recursively as \(a_1=4\), and \(a_n=a_{n-1}+3\). So,

\(a_1 = 4\)

\(a_2=a_{2-1}+3=a_1+3=4+3=7\)

\(a_3=a_{3-1}+3=a_2+3=7+3=10\)

\(a_4=a_{4-1}+3=a_3+3=10+3=13\)

\(a_5=a_{5-1}+3=a_4+3=13+3=16\)

GGC
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.
Example 2 - Possible to make a PYTHON TUTOR

The sequence \(b_n=f\left(n\right)=2\cdot\ 3^n\), is the sequence generated by the exponential function, \(f\left(x\right)=2\cdot3^x\), whose first few terms would, be

\(b_1=2\cdot\ 3^1=6,\)

\(b_2=2\cdot\ 3^2=18,\)

\(b_3=2\cdot\ 3^3=54\)

\(b_4=2\cdot\ 3^4=162\)

The same sequence may be defined recursively as \(_1=6\), and \(b_n=3\cdot b_{n-1}\). So, \(b_2=3\cdot b_{2-1}=3\cdot6=18\),

\(b_3=3\cdot b_{3-1}=3\cdot18=54 \)

\(b_4=3\cdot b_{3-1}=3\cdot54=162 \)

GGC
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\), \(r\) being the common ratio.

Some sequences, like the Fibonacci sequence, are easier to generate recursively. The Fibonacci sequence, is defined recursively as,

\(f_1=1\), and, \(f_2=1\), and

\(f_n=f_{n-1}+f_{n-2}\) So , \( f_3=f_{3-1}+f_{3-2}=f_2+f_1=1+1=2\),

\(f_4=f_{4-1}+f_{4-2}=f_3+f_2=2+1=3\),

\(f_5=f_{5-1}+f_{5-2}=f_4+f_3=3+2=54\),

\(f_6=f_{6-1}+f_{6-2}=f_5+f_4=5+3=8\)

\(f_7=f_{7-1}+f_{7-2}=f_6+f_5=8+5=13\)

While, other sequences are easier to define using explicit functions.

Find the first 6 terms of the sequence, \(c_k=\frac{1}{k^2}\) generated by the function \(f(x)=\frac{1}{x^2}\).

\(c_1=f\left(1\right)=\frac{1}{1^2}=1\),

\(c_2=f\left(2\right)=\frac{1}{2^2}=\frac{1}{4}\),

\(c_3=f\left(3\right)=\frac{1}{3^2}=\frac{1}{9}\),

\(c_4=f\left(4\right)=\frac{1}{4^2}=\frac{1}{16}\),

\(c_5=f\left(5\right)=\frac{1}{5^2}=\frac{1}{25}\),

\(c_6=f\left(6\right)=\frac{1}{6^2}=\frac{1}{36}\).

GGC

8.1.2. Series and Sigma notation

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. 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.

There is a shorthand way of writing a series using sigma, or sum notation, denoted by the \(\sum\) symbol.

For example \(a_1+a_2+a_3+a_4=\sum\limits_{i=1}^{4}a_i \) which means starting at \(i=1\) and 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\).

Likewise, \(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\)

Example 3

Consider \( {a_n}=\left\{3n+1\right\}\)

\(\sum\limits_{i=1}^{4}a_i=a_1+a_2+a_3+a_4 = \left(3\times1+1\right)+\left(3\times2+1\right)+\left(3\times3+1\right)+\left(3\times4+1\right)=\sum\limits_{i}^{4}{(3i+1)}\)

\( \sum\limits_{i=1}^{n}a_i = a_1+a_2+a_3+\ldots+a_n=\left(3\times1+1\right)+\left(3\times2+1\right)+\left(3\times3+1\right)+\ldots +\left(3\times n+1\right)=\sum\limits_{i}^{n}{(3i+1)}\)

\(\sum\limits_{i=1}^{\ \infty\ }a_i=a_1+a_2+a_3+\ldots=\left(3 \times 1+1\right)+\left(3\times 2+1\right)+\left(3\times 3+1\right)+\ldots\ =\sum\limits_{i=1}^{\ \infty\ }{(3i+1)}\)

8.2. Mathematical Induction

Mathematical induction is a method of proof used to prove a series of different propositions, say \(P_1,\ P_2,P_3,\ldots P_n\). A useful analogy to help think about mathematical induction is that of climbing a ladder. It is useful to think of climbing a ladder as made up of two parts. To climb a ladder the first part involves being be able to actually step onto the ladder, or make it to the first rung (or at least some rung) of the ladder. The second part involves knowing that if we are on on some rung of the ladder we can get to the next rung of the ladder. This tells me I can climb the ladder.

GGC

Remember to climb the ladder we require two different components.

  • I can get to the first step of the ladder or be able to prove that \(P(1)\) is true. This is called the basis step.

  • In the second component, I want to know that if I’m on any given step I can climb to the next one. Proving \(P(m+1)\), assuming \(P(m)\) for general \(m\), is called the induction step.

Example 4

Let us contrast this with a specific mathematical claim.

  • \(\sum\limits_{i=1}^{n}i=1+2+...+n=\frac{n\left(n+1\right)}{2}\)

This is a sequence of statements in terms of \(n\) telling me that the sum of the first \(n\) integers is going be equal to some formula that depends on the final number \(n\) that you want to add.

When \(n=1\), there is only 1 term to add. Does \(1 \overset{?}{=}\frac{1\ \left(1+1\right)}{2}\)?

Since, \(1=\frac{2}{2}\), this formula is valid when \(n=1\).

It also checks out when \(n=2\). \(1+2=\frac{2\ \left(2+1\right)}{2}\)

We may continue with \(n=3, n=4, ….\), etc., and notice that we want to prove an infinite collection of propositions. Specifically, we want to establish this claim for every positive integer.

The propositions are indexed by the positive integers. In induction we consider a property \(P\), that depends on these values \(n\), where \(n\), is going to be positive integers. So in the previous case the property \(P(n)\) was some equality that the sum of the first \(n\) terms is equal to that formula. However, this property could vary, as long as it is indexed by \(n\). In other words the general structure of these claims is going to be a ladder with a first step, a second step, a third step and so on.

Assume the statement is true for \(P(m)\). That is \(\sum\limits_{i=1}^{m}i=1+2+...+m=\frac{m\left(m+1\right)}{2}\) (called the induction hypothesis).

Prove that this implies \(P(m+1)\) is true. That is prove \(\sum\limits_{i=1}^{m+1}i=1+2+...+m+(m+1)=\frac{(m+1)\left(m+1+1\right)}{2}=\frac{(m+1)\left(m+2\right)}{2}\)

Begin with the left side, \(1+2+...+m+(m+1)\)

We can rewrite this, as \(\frac{m\left(m+1\right)}{2}+(m+1)\) using the induction hypothesis.

Now we simplify this using algebra and show that it is the same as the right hand side.

Factoring out \((m+1) \) gives,

\(\left(m+1\right)\left(\frac{m}{2}+1\right)=\left(m+1\right)\left(\frac{m}{2}+\frac{2}{2}\right)=\left(m+1\right)\left(\frac{m+2}{2}\right)=\frac{\left(m+1\right)\left(m+2\right)}{2}\)

Which is the same as the right-hand side!

So \(1+2+...+m+(m+1)=\frac{\left(m+1\right)\left(m+2\right)}{2}\), which means we have shown \(P(m+1)\) follows from \(P(m)\).

So, by induction, \(\sum\limits_{i=1}^{n}i=1+2+...+n=\frac{n\left(n+1\right)}{2}\) for all positive integers \(n\).

Types of statements that can be proven by induction:

  • Summation formulas: Prove that 1(1!) + 2(2!) + · · · + n(n!) = (n + 1)! – 1, for all positive integers.

  • Inequalities: Prove that \(2^n < n!\) for every positive integer \(n\) with \(n ≥ 4\).

  • Divisibility: Prove that \(n^3+2n\) is divisible by 3 for every positive integer \(n\).

  • Sets: Prove that if \(S\) is a set with \(n\) elements where \(n\) is a nonnegative integer, then \(S\) has \(2^n\) subsets.

  • Algorithms: Prove that the recursively defined algorithm fac(n) returns \(n!\) for all nonnegative integers.

def fac(n)

begin
if n = 0 then
return 1
else
return n · fac(n − 1)

end

Example 5 (A Summation Formula)

Prove by mathematical induction \(1·1!+2·2!+3·3!+···+n· n!=\underset{k=1}{\overset{n}{\sum }}k\left( k!\right) =\left(n+1\right)!-1\)

Solution:

For each integer \(n\), let \(P(n)\) be the statement \(P(n):\sum\limits_{k=1}^{n} k\left( k!\right) =\left(n+1\right)!-1\)

To prove using induction, we need

  • Base case: \(P(1)\) is true

  • Inductive step: For all integers \(m>0\), if \(P(m)\) is true, then \(P(m+1)\) is true.

Base Case: Substitute \(n=1\) into \( \sum\limits_{k=1}^{n}k(k!)=\left(n+1\right)!-1\)

\( \sum\limits_{k=1}^{1} (k)k!\overset{?}{=}\left(1+1\right)!-1\)

Simplify both sides to check for validity: 1==1, therefore the base case is true.

Begin the inductive step by assuming P(m) for some integer m>0.

Assume \(P(m):\sum\limits_{k=1}^{m}k(k!)=\left(m+1\right)!-1\) for some integer m>0.

Write down the left hand side of P(m+1):

\(P(m+1):\sum\limits_{k=1}^{m+1}k(k!)\)

Extract (m+1) (m+1)! from the summation,

\(\sum\limits_{k=1}^{m+1} k(k!)=\sum\limits_{k=1}^{m}kk!+(m+1)!(m+1)\)

Apply the induction hypothesis by replacing

\(\sum\limits_{k=1}^{m}k(k!)\) with (m+1)!-1,

\(\sum\limits_{k=1}^{m+1}k(k!)=((m+1)!-1)+(m+1)!(m+1)\)

Simplify the result:

\(\sum\limits_{k=1}^{m+1}k(k!)=-1+2\left(m+1\right)!+\left(m+1\right)!m\)

\(=-1\ +(m+1)(2+m)=(m+2)!\ -1\ =((m+1)+1)!-1\)

Express the result in terms of m+1,

\(\sum\limits_{k=1}^{m+1}k(k!)=((m+1)+1)!-1\)

Therefore, the inductive step has been verified \(\sum\limits_{k=1}^{m+1}k(k!)=((m+1)+1)!-1\)

Example 6: (Another Summation Formula)

Prove the proposition that the sum of the first n odd numbers is \(n^2\); that is,

\(1+3+5+···+2n-1=\sum_{k=1}^{n} (2k-1) =n^2\) for n a positive integer \(n\in\mathbb{Z}\)

Solution:

For each integer n, let P(n) be the statement \(\sum_{k=1}^{n} \left(2k-1 \right)=n^2\) \(P\left(n\right):\sum_{k=1}^{n} \left(2k-1 \right)=n^2\)

Consider the following properties: base case: P(1) is true inductive step: For all integers m>0, if P(m) is true, then P(m+1) is true. If the above properties hold, then for each n\(\in\mathbb{Z}\) where n>0, the statement P(n) is true Substitute n=1 into \(\sum_{k=1}^{n} (2k-1)=n^2\)

\(\ \sum_{k=1}^{1} (2k-1)\overset{?}{=}1^2 \)

Simplify both sides to check for validity:

1=1,

therefore the base case is true and the inductive step can be taken Begin the inductive step by assuming P(m) for some integer m>0 Assume for some integer m>0

\(P(m):\ \sum_{k=1}^{m} (2k-1)=m^2\)

Write down the left-hand side of P(m+1):

\(LHS\ P(m+1):\ \sum_{k=1}^{m+1}{(2k-1)}\)

Extract \( (m+1)-1\) from the summation,

\(\sum_{k=1}^{m+1} (2k-1)=\sum_{==1}^{m}{(2k-1)}+(2(m+1)-1)\)

Apply the induction hypothesis by replacing,

\(\sum_{k=1}^{m}{(2k-1)}\), with \(m^2\)

\(\sum_{k=1}^{m+1} \left(2k-1\right)=m^2 +(2(m+1)-1)=m^2+2m+2-1\)

\(=m^2+2m+2\ =m^2 +2m+2(m+1)^2\)

Simplify the result expressing the result in terms of m+1:

\(\sum_{k=1}^{m+1} {(2k-1)}={(m+1)}^2\). In other words,

\(\sum_{k=1}^{m} {(2k-1)}=m^2\),

implies

\(\sum_{k=1}^{m+1} {(2k-1)}=(m+1)^2\)

Therefore, the inductive step has been verified.

Example 7: (Inequality)

Prove that \(n! > 3^n\) for every positive integer n with n > 6.

Solution:

Since the base case value must be greater than 6, the base case value will be set to the next integer after 6: The base case value is n=7,

\(7!\overset{?}{=}3^7\) Simplify both sides to check for validity: \(5040>2187\), therefore the base case is true and the inductive step can be taken, Begin the inductive step by assuming P(m) for some integer m>6. Assume,

\(P(m):\ m!>3^m,\)

for some, integer m>6.

We want to show this implies P(m+1) or,

\(P(m+1):\ (m+1)!>3^{m+1}\), Write down the left hand side of

\(LHS \ P(m+1) : (m+1)!\)

Factor out m+1 from (m+1)!:

\((m+1)!=m! (m+1)\)

Using the induction hypothesis, \( m!>3^m\) , then,

\( m!(m+1)>3^m(m+1)\),

\(\left(m+1\right)!>3^m\left(m+1\right)\),

Using m+1>3, then

\(3^m (m+1)>3^m3\)

Combining exponents, \(3^m 3=3^{m+1}\)

\((m+1)!>3^{m+1}\)

\(m!>3^m\) implies \((m+1 )!>3^{m+1}\)

GGC
Example 8: (Divisibility)

Prove the following using the principle of mathematical induction:\(n^2 + n\) is even (or divisible by 2 ), for n > 0.

Solution:

Since the base case value must be greater than 0, the base case value will be set to the next integer after 0: For each integer n, let P(n) be the statement \(n^2 + n\) is divisible by 2. Consider the following properties: base case: P(1) is true

inductive step: For all integers m > 0, if P(m) is true, then P(m + 1) is true

If the above properties hold, then for each n \(\in\mathbb{Z}\) 0, where \(n>0\) the statement\(P(n)\)is true n^2+n is divisible by 2 if and only if \(\left(n^2+n\right)mod2=0\).

Prove \(\left(n^2+n\right)mod2=0\), for n>0 f or n>0.

Substitute n = 1 into \(\left(n^2+n\right)mod2=0\): \(1 + 12 mod 2 \overset{?}{=}0\)

Simplify both sides to check for validity: 2 mod 2 = 0 therefore the base case is true and the inductive step can be taken

Begin the inductive step by assuming P(m) for some integer m > 0: Assume \(P(m):\ \left(m^2+km\right)mod2=0\) for some integer m>0 Write down the left hand side of P(m+1):\(LHS\ P(m+1):\ \left(m+1\right)+\left(m+1\right)^2\)

Expand \(\left(m+1\right)+\left(m+1\right)^2=m^2+2m+m+2\) Isolate \(m^2+m\) as its own term: \(=\left(m^2+m\right)+\left(2m+2\right)\)

Factor 2 from 2m+2: \(=\ \left(m^2+m\right)+2\ \left(m+1\right)\) The induction hypothesis states that \(m^2+m\) is divisible by 2: \(\left(m^2+m\right)mod2=0\)

2 (m+1) has 2 as a factor, explicitly, so :\(\left(2\left(m+1\right)\right)mod2=0\) \(\left(m^2+m\right)mod2=0\) implies \(\left(\left(m+1\right)+\left(m+1\right)^2\right)mod2=0\) Therefore, the inductive step has been verified The left and right term each have 0 as a remainder when divided by 2: Since both terms are divisible by 2, the entire expression is also divisible by 2 The inductive step was shown to be true, and thus the claim has been verified: Answer: Therefore, \(n^2+n\) is divisible by 2, for n>0 has been proven true

Example 9: (Another Divisibility)

Prove the following using the principle of mathematical induction: \(8^n -3^n\) is divisible by 5, for any positive integer n>0.

Solution:

Since the base case value must be greater than 0, the base case value will be set to the next integer after 0: The base case value is n=1 For each integer n, let P(n) be the statement \(8^ n-3^n\) is divisible by 5. Consider the following properties: base case: P(1) is true inductive step: For all integers k>0, if P(m) is true, then P(m+1) is true

If the above properties hold, then for each n \(\in\mathbb{Z}\) where n>0, the statement P(n) is true \(8^n -3^n\) is divisible by 5 if and only if \((8^n -3^n) mod 5=0\): Prove \((8^n -3^n) mod 5=0\), for n>0 Substitute n=1 into \((8^n -3^n) mod 5=0\):\((8-3)mod5\overset{?}{=}0\) Since \(8- 3 = 5\) and 5 is divisible by 5.

Simplify both sides to check for validity: 0=0, therefore the base case is true and the inductive step can be taken

Begin the inductive step by assuming P(m) for some integer k>0: Assume \(\left(8^m -3^m\right)mod5=0\) for some integer \(m>0\)

Write down the left hand side of P(m+1), \(LHS\ P(m+1):8^{m+1} -3^{m+1}\)

For \(a^{m+1}\ -b^{m+1}+1\), subtract and add \(ba^k\): \(=8^{m+1} -3{\times8}^m +3\times8^m -3^{m+1}\)

Group into two terms:\(=\left(8-3\right)8^m +3\left(8^m -3^m\right)\), \(\left(8^m \left(8-3\right)\right)+\left(3\left(8^m -3^m\right)\right)\): Determine if each of these terms is divisible by 5 8-3=5: and \((5\times8^m)+(3(8^m-3^m)\)

\(8^5 5\) has 5 as a factor, explicitly:\(\left(5{\times8}^m\right)mod5=0 \)

The induction hypothesis states that \(8^m -3^m\) is divisible by 5: \(\left(3\left(8^m -3^m\right)\right)mod5=0\). The left and right term each have 0 as a remainder when divided by 5: Since both terms are divisible by 5, the entire expression is also divisible by 5 \(\left(8^m -3^m\right)mod5=0\ implies\ \left(8^{m+1}\ -3^{m+1}\ \right)mod5=0\): Therefore, the inductive step has been verified The inductive step was shown to be true, and thus the claim has been verified:

Therefore, pass:[\(8^n -3^n\)] is divisible by 5, for pass:[\(n>0\)] has been proven true.

8.3. Strong Induction

Recall the idea behind mathematical induction, prove that a proposition, \(P\left(m\right)=P_m\) is true for a base step, say \(P_1\), then prove the inductive step. This involves proving that \(P_m\), implies \(P_{m+1}\). Strong induction is a generalized version of induction, where in the inductive step we assume \(P_1, P_2,\ldots, P_m\) is true and show these together imply \(P_{m+1}\) is true.

Strong version of Mathematical Induction:

  • (1) Prove the first statement \(P_1\). (Or the first several \(P_r\), if needed.)

  • (2) Given any integer \(m ≥ 1\), prove \(P_1\bigwedge{P_2\bigwedge{\ P_3\bigwedge{\ldots\bigwedge{P_m,\ }}}}\) implies \(P_{m+1}\)

Algorithmically:

  • Base Case: Prove that \(P_{1,\ }P_2\ ,\ldots,\ P_r\), are all true.

  • Inductive Hypotheses: Assume, \(P_{1,\ }P_2\ ,\ldots,\ P_m\)are all true for some \(m ≥ 1\),

  • Inductive step: Assuming, \(P_{1,\ }P_2\ ,\ldots,\ P_m\) are all true for some \( m ≥ 1\), prove that \(P_{m+1}\) is true.

Example 10 - Recurrence Relations

Consider the sequence \(\left\{a_n\right\}\), defined as a a recurrence relation,

\(a_1=5\), and \(a_2=13\), and \(a_{n+2}=5a_{n+1}-6a_n\), for all \(n \geq 1\).

Prove that \(a_n=2^{n} +3^{n}\).

Solution

Base case: Consider the case \(n=1\), \(a_1=5=2^{1} +3^{1}\), and \(a_2=13=2^2 +3^2=4+9\).

Induction hypothesis: Assume \(a_1,\ a_2,..a_m\) are all given by \(a_m=2^m + 3^m\).

We want to show that \(a_{m+1}=2^{m+1} +3^{m+1}\).

Well, \( a_{m+1}=5a_m-6a_{m-1}\), using the definition of the recurrence relation.

By the inductive hypothesis, \(a_m=2^m+3^m\), and \(a_{m-1}=2^{m-1} +3^{m-1}\).

\( a_{m+1}=5\left(2^m +3^m \right)-6\left(2^{m-1} +3^{m-1}\right)\).

Consider then,

\[\begin{split} 5\left(2^m+ 3^m \right)-6\left(2^{m-1} +3^{m-1}\right) &=5\times 2^m +5\times 3^m -6\times 2^{m-1} -6\times 3^{m-1}\\ &=5\times 2^m+5\times 3^m-3\times 2\times 2^{m-1}-2\times 3\times 3^{m-1}\\ &=5\times\ 2^m+5\times 3^m-3{\times 2}^m-2\times 3^m\\ &=\left( 5\times 2^m-3\times 2^m \right) + \left( 5 \times 3^m -2\times 3^m \right)\\ &=\left(5-3\right) \times 2^m + \left(5-3\right) \times 3^m\\ &=2\times\ 2^m+3\times 3^m\\ &=2^{m+1} + 3^{m+1} \end{split}\]

So \(a_{m+1}=2^{m+1} + 3^{m+1}\) and therefore, \(a_n=2^n +3^n\) for all \(n \geq 1\).

8.4. Exercises

Prove using induction.

  1. For all \(n ≥ 1\) prove that \(1+2+3+\ldots+n=\sum_{i=1}^{n}i=\frac{n\left(n+1\right)}{2}\)

  2. For all \(n ≥ 1\), prove that \({23}^n-1\) is divisible by 11.

  3. Prove by mathematical induction that \(7\) divides \(2^{4n+2} + 3^{2n+1}\) for all nonnegative integers \(n\).

  4. Prove that for any \(n ≥ 1\), and \(x ≥ 0\), , \(\left(1+x\right)^n\geq1+nx\).

  5. For all \(n ≥ 5\) prove that, \( 2^n>n^2\).

  6. Prove by induction that a set \(A\) with cardinality \(|A|=n\), has \(2^n\), subsets.

  7. Prove by induction, that there are \(3^n\), numbers in base 3 (using the digits 0 ,1, 2) made up of \(n\) digits.

  8. Prove by induction, that there are \(4^n\), numbers in base 4 (using the digits 0 ,1, 2, 3,) made up of \(n\) digits.

  9. State the principle of induction using a conditional logical statement.

  10. Prove, by induction that the sum of the first \(n\), Fibonacci numbers is \(f_1+f_2+\ldots+f_n=\sum_{i=1}^{n}{f_i=f_{n+2}-1}\)

  11. Prove, by induction that the sum of the squares of the first \(n\), Fibonacci numbers is \(f_1^2+f_2^2+\ldots+f_n^2=\sum_{i=1}^{n}{f_i^2=f_n\cdot\ f_{n+1}\ }\)

9. Graph Theory

Graphs are discrete mathematical structures that have many applications in a diversity of fields, including chemistry, network analysis, algorithms, and social sciences.

9.1. Introduction and basic definitions

We begin with some basic terminology.

9.1.1. Undirected and directed graphs

A graph, \(G=\left(V,\ E\right)\), is a structure consisting of a set of objects called vertices, \(V\), and a set of objects called edges, \(E\). An edge \(e\in\ E\), is denoted in the form \(e=\left\{x,y\right\}\), where the vertices \(x,y\in\ V\). The two vertices \(x,y\) connected by the edge \(e=\left\{x,y\right\}\), are said to be adjacent, with \(x\) , and \(y\), called the endpoints. Sometimes the edge, \(e\), may be written in shorthand as, \(xy\).

Example—​An undirected graph.

The graph shown has vertex set, \(V=\left\{A,\ B,\ C,\ D,\ E,\ F\right\}\), and edge set \(E=\{\{A,C\},\{A,D\},\{B,D\}\{B,F\},\{C,F\},\{D,F\},\{F,E\}\}\)

graph1

A directed graph (or digraph) is an extension of the definition of a graph in which the edges are recognized to be ordered.

Example—​A directed graph.

The graph, \(G=(V,E)\), with vertex set ,\(V=\{A,B,C,D,E,F\}\) , and edge set, \(E=\{\{A,C\},\{D,A\},\{B,D\}\{F,B\},\{C,F\},\{D,F\},\{G,E\}\}\), with edge set considered as ordered is a directed graph and shown below.

graph2

9.1.2. Degree of a vertex

The degree of a vertex \(v \in V\), denoted \(d(v)\) is the number of edges in the graph, \(G\), containing the vertex \(v\).

Example—​degree.

The degrees of each of the vertices in the undirected graph, \(G\), with vertex set, \(V={A,B,C,D,E,F,G}\), and edge set \(E=\{\{A,C\},\{A,D\},\{B,D\}\{B,F\},\{C,F\},\{D,F\},\{F,G\}\), shown below, are,

\(d\left(A\right)=2\)

\(d\left(B\right)=2\)

\(d\left(C\right)=2\)

\(d\left(D\right)=3\)

\(d\left(E\right)=1\)

\(d\left(F\right)=4\)

Notice that the total sum of all the degrees, \(d\left(A\right)+\ d\left(B\right)\ +\ d\left(C\right)+\ \ d\left(D\right)\ \ +d\left(E\right)+\ d\left(F\right)=14\) , is twice the number of edges, \(\left|E\right|=7\), in the graph. This is true in general and we state this result as theorem, often called the handshaking lemma and leave the proof as an exercise.

9.1.3. Theorem—​Handshaking lemma

The sum of the degrees of the vertices of a graph \(G=\left(V,\ E\right)\) is equal to twice the number of edges in \(G\), or,

\(\sum_{v\in V}{d\left(v\right)=2\ \left|E\right|}\).

A useful consequence of this, to keep in mind, is that the sum of the degrees of a graph is always even.

9.2. Representing graphs.

In addition to the vertex, edge representation of graphs there are alternative ways to represent a graph especially for computing.

9.2.1. The adjacency matrix

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 then, 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. \)

Example—​Giving the adjacency matrix of a graph

The graph with vertex set, \(V=\left\{A,\ B,\ C,\ D,\ E,\ F\right\}\), and edge set, \(E=\{\{A,C\},\{A,D\},\{B,D\}\{B,F\},\{C,F\},\{D,F\},\{F,E\}\}\)

has adjacency matrix,

\begin{matrix}A&0&1&1&0&0&0\\C&1&0&0&0&1&0\\D&1&0&0&1&1&0\\B&0&0&1&0&1&0\\F&0&1&1&1&0&1\\E&0&0&0&0&1&0\\\ &A&C&D&B&F&E\\\end{matrix}

Example—​Obtaining the graph from the adjacency matrix

The graph with adjacency matrix,

\begin{matrix}a&0&1&1&1\\c&1&0&1&1\\d&1&1&0&1\\b&1&1&1&0\\\ &a&c&d&b\\\end{matrix}

is the graph shown below.

graph3

9.2.2. The adjacency matrix for directed graphs

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

Example of adjacency matrices for an undirected graph and for a directed graph.

In the figure below the first graph is undirected while the second is a digraph.

graph4

Their adjacency matrices are respectively,

\( \left(\begin{matrix}0&1&1&0\\1&0&1&0\\1&1&0&0\\0&0&0&0\\\end{matrix}\right) \) and, \( \left(\begin{matrix}0&1&0&0\\0&0&1&0\\1&0&0&0\\0&0&0&0\\\end{matrix}\right). \)

9.3. Weighted graphs

A weighted graph is one in which each edge \(e\) is assigned a nonnegative number, \(w(e)\), called the weight of that edge. Weights are typically associated with costs, or capacities of some type like distance or speed. The adjacency matrices for weighted graphs are very similar to those for graphs that are not necessarily weighted, and instead of using a, \(1\) to represent an edge between two vertices, say \(v_i\), and \(v_j\), we place the the weight of the edge \(w(e)\) in position \(m_{i,j}\), of the adjacency matrix as show in the following two examples.

Consider first the following weighted undirected graph.

graph5

Its adjacency matrix is, \( \left(\begin{matrix}0&2&5&0\\2&0&3&0\\5&3&0&1\\0&0&1&0\\\end{matrix}\right). \)

By contrast, the directed weighted graph, below,

graph6

has adjacency matrix \( \left(\begin{matrix}0&2&0&0\\0&0&3&0\\5&0&0&1\\0&0&0&0\\\end{matrix}\right). \)

9.4. Subgraphs

A graph \(H=(V_1,E_1)\), is said to be a subgraph of the graph \(G=(V,\ E)\), if \(V_1\subseteq V\) , and \(E_1\subseteq E\).

9.4.1. The subgraph formed by removing or deleting a vertex from a graph

If the vertex \(v\in V\) belongs to the graph \(G=(V,E)\), we denote by \(G-v\), the subgraph, obtained from G, by removing the vertex \(v\), and all edges in \(E\), adjacent to the vertex \(v\). Below is shown a graph \(G\), and the subgraph, \(G-d\) formed by removed the vertex \(d\).

graph7

9.4.2. The induced subgraph

A natural generalization of the subgraph obtained by removing a vertex, is the subgraph obtained by removing multiple vertices and the edges associated with the removed vertices. The subgraph obtained is called the subgraph induced by removing those vertices.

Below is a graph \(G(V,E)\), and the subgraph obtained by \(V-\{a,d\}\), called the induced graph, \(G-\{a,d\}\), with a slight abuse of notation

graph8

9.5. Connectivity, Eulerian Graphs and Hamiltonian graphs

We begin this section with some terminology relating to connectivity and traversal of graphs.

9.5.1. Terminology

A walk, on a graph \(G=v\left(V,E\right)\) is a finite, non-empty, alternating sequence of vertices and edges, of the form, \(v_0e_1v_1e_2\ldots e_nv_n\), with vertices \(v_i\in V\) and edges, \(e_i\in E\).

A trail is a walk that does not repeat an edge, ie. all edges are distinct.

A path is a trail that does not repeat a vertex.

A cycle is a non-empty trail in which the only repeating vertices are the beginning and ending vertices, \(v_0=v_n\).

In the graphs below the first shows a trail \(CFDBFE\). It is not a path since the vertex \(F\) is repeated. The second shows a path \(CADFB\) and the third a cycle \(CADFC\).

graph9

A graph is connected if there is a path from each vertex to every other vertex.

The graph below is not connected,

graph10

and has adjacency matrix,

\( \left(\begin{matrix}0&1&1&0&0\\1&0&1&0&0\\1&1&0&0&0\\0&0&0&0&1\\0&0&0&1&0\\\end{matrix}\right). \)

9.5.2. Eulerian Graphs

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 preciesly 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 and returns 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.

graph11

9.5.3. Hamiltonian Graphs

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 \(2^{nd}\) graph is not Hamiltonian.

graph12

9.6. PythonTutor Example 1.1

Simple Program

Use the Forward button to step through the program below and watch the data get created and modified. Notice how the arrows move to indicate what instruction the program execution is on.

9.7. Exercises

GGC