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.
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.
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.
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
Expression Evaluation
When Python encounters a line with an expression, it always evaluates the expression first.
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. 
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.
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.
When you want to force exactly 1 of 2 blocks (as opposed to just skipping a block) you can use if else.
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.
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.
When you want to consider every value in a list, use a for loop.
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. 
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.
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 
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 
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 
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 
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 
2.1.6. BiImplication
"It is raining outside if and only if it is a cloudy day."
Let \(p\) and \(q\) be propositions. The biimplication 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, biimplication requires \(q\) to be True only when \(p\) is True. In other words, biimplication 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 
It is important to contrast implication with biimplication. 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 biimplication 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 twoway 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.
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.
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. 
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.
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.
The Existential Quantifier, \(\exists\), represents the statement "there exists", "for some", "at least one". When it comes before a statement, it means the statement is true for at least one value in the domain.
Recall the previous example statements:

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?
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)\).
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.
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)\).
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.\)
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\}.\]
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.
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.\)
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.\)
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\):
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\}.\]
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\):
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\}.\]
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\):
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\}.\]
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}\):
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)\):
Video Example 1
Video Example 2
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.
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.
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.
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 oneto 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
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,
An easy check, \( f\left(2\right)=2^3=8\), and
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}
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}
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}
\begin{array}{lcccccl} & x & 0 & 1 & 8 & 27 & 64 & 125 \\ & \sqrt[3]{x} & 0 & 1 & 2 & 3 & 4 & 5 \end{array}
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.
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
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^{mn}\)
\(\frac{3^5}{3^2}=\frac{3.3.3.3.3}{3.3.}=3^{52}=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^{55}=3^0\)
6) \(a^{1}=\frac{1}{a}\) \(3^{1}=3^{01}=\frac{3^0}{3^1}=\frac{1}{3}\)
7)
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}
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}
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}
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}
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(fg\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(fg\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)=2x3\), 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}{2x3}\). 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 \(2x3\ \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)(x1)\$ 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)(21)= 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)(91)= 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)(281)= 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)(x1) \$, 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 codomain \(B=\left\{0,\ 1,\ 4,\ 9\right\}\). However the inverse mapping, from domain \(A=\left\{0,\ 1,\ 4,\ 9\right\}\), with codomain \(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=c5\), or \( x=\frac{c5}{3}\). So, for any \(c\), there is an \(x\), namely, \(x=\frac{c5}{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 \(x5=3y,\), or \(\frac{x5}{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{x5}{3}\right)=\ 3\left(\frac{x5}{3}\right)+5=\left(x5\right)+5=x\),
and, \(\left(g \circ f\right)\left(x\right)=g\left(3x+5\right)=\ \frac{(3x+5)5}{3}=\frac{3x+55}{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{x5}{3}\) , and , \(g\left(11\right)=\frac{115}{3}=\frac{6}{3}=2\), or \(g:11\rightarrow 2\).
4.3. Exercises

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

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

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

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

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

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

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


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

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

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

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

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

Is the function a surjection? Explain.

Is the function an injection? Explain

Is the function a bijection? Explain

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

Evaluate

\(f\left(2.1\right)\)

\(f\left(1.9\right)\)

\(f\left(1.5\right)\)

\(f\left(1.9\right)\)

\(f\left(2\right)\)

\(f\left(2.3\right) \)


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

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

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



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

Is the function a surjection? Explain.

Is the function an injection? Explain

Is the function a bijection? Explain

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

Evaluate

\(f\left(5.1\right) \)

\(f\left(3.9\right)\)

\(f\left(3.2\right)\)

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

\(f\left(5.3\right)\)


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

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

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



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)=\left2.5\right=2.5\) , but, for example, \(f\left(4.5\right)=\left4.5\right=4.5\). Notice that if \(x geq 0\), then \(\leftx\right=x\). However if \(x<0\), then we have to negate to find that \(\leftx\right=\ x\). We can state this using the notation for piecewise functions:

Graph \(f\left(x\right)=x\), for \(10\ \le x\ \le10\)

Evaluate

\(f(5)=5\),

\(f(2.5)=2.5\),

\(f(3.5)=3.5\).


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

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

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

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

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

5. Chapter Algorithms
5.1. Definitions
An algorithm is a stepbystep 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:

It can be used to help nonprogrammers understand what a program or algorithm does and how it works.

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.
Pseudo Code  Python Code  



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.
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
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.
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 nonnegative integers less than 11, the first using an output and the second a print statement.
Pseudo Code Using Output  Pseudo Code Using Print 



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
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:
Polynomial growth is larger than radical growth:
Exponential growth is larger than polynomial growth:
Factorial growth is larger than exponential growth:
Using the graphical analysis of the growth of typical functions we observe that we have the following growth ordering,
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^22x\).
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) ≤ Ag(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,
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.
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
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))\)

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

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

\( 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_{n1}x^{n1} +a_{n2}x^{n2}+\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^2x\), 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^2x)= x^5 x^4+x^2x \), 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.
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

Give big O estimates for

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

\(f\left(x\right)=3x2\)

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

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

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

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

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

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


Give big O estimates for

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

\(f\left(x\right)=5x2\)

\(f\left(x\right)=5x^84x^6+x^3\)

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

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

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

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

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


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.

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.

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.

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.

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

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

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

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

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

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

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,

\((f+g)(x)\)

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


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

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

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


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

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

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

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 … (n1) * (n)\) 

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:

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

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

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

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

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

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 \(n1\) of the array, after which the 2nd largest element is in position \(n1\). The elements, now at positions \(n\), and \(n1\), are sorted. Continue to sort at positions \(n2\), then \(n3\) 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 

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, {a_{1}, a_{2}, …, a_{n} }
in ascending orders
_____________________________________________________________________
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 InsertionSort ( a = {a_{1}, a_{2}, …, a_{n} } : n real numbers with n>1 )
begin
for i = 1 to n  1 do
key = a_{i}
j = i1
while j ≥ 0 and a_{j} > key do
a_{j+1} = a_{j}
j = j1
end
a_{j+1} = key
end
end
____________________________________________________________________
A Python implementation of the Insertion Sort Algorithm is given below:
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. 

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\ (n1)!\ \)
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…(n1)*(n)
_____________________________________________________________________
Procedure RFactorial( n )
begin
if n==0 then do
return 1
else do
return n*Rfactorial(n1)
end
end
____________________________________________________________________
A recursive implementation of the factorial function in Python is given below
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^{n1}\).
A pseudocode recursive implementation of the power function or exponential function \(b^n\), would be
______________________________________________
Procedure Rexponentiation: recursively computes the
exponent b^{n}
______________________________________________
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(n1)
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_{n1}\)
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_{n1}\),
and the sequence can be generated recursively using the following pseudocode,
______________________________________________
Procedure Rarithmetic: recursively computes the n^{th} 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_{n1}+f_{n2}\)
We omit the pseudocode and provide a recursive Python implementation to compute 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 \(n1\), passes with swaps,
\(n1+n2+...3+2+1 = 1+2+3+...+n1\).
We will show later, that
\( 1+2+3+...+n1= \frac{(n1)\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

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

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

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

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_{n1}+2a_{n2} \end{array}

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_{n1}\cdot\ b_{n2} \end{array}

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}

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.

Give big O estimates for

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

\(f\left(x\right)=5x2\)

\(f\left(x\right)=5x^84x^6+x^3\)

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

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

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

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

\(f\left(x\right)=\frac{x^5+2x^4x+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.
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 52card 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+mp\) ways
\(E\) or \(F\) can occur. This is called the inclusionexclusion 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+42=10\) possibilities.
You Try: If a card is drawn from a standard 52card deck, how many ways can the card be black or a face card?
Examples
Video Example
6.1.4. Exercises

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

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

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


A multiplechoice test contains 20 questions, and each question has four choices.

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

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


How many different threeletter initials can a person have?

How many different threeletter initials end with "R"?

How many bit strings are there of length five?

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

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

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

Digits and letters can be repeated?

Digits and letters cannot be repeated?


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?

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 (*, >, <, !, +, =).

How many different passwords are available?

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 socalled pigeonhole principle.
Pigeon Hole Principles
If \(n+1\) pigeons are resting in \(n\) pigeonholes then at least one pigeonhold contains more than one pigeon.

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

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

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?

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

A bag contains 8 red balls and 7 blue balls.

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

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


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?

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
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(n1)(n2) \cdots (nr+1) = \displaystyle \frac{n!}{(nr)!}\).

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!}{(103)!} = \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!(nr)!}\)

Examples
Video Example 1
Video Example 2
Example: How many ways can five cards be dealt from a standard 52card 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

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

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

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

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

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


Find the value of the following

\(P(5,2)\)

\(P(10,8)\)

\(P(14,10)\)

\(C(5,2)\)

\(C(10,8)\)

\(C(14,10)\)


How many bit strings of length 8 contain:

Exactly four 1s?

At most four 1s?

At least four 1s?

The same number of 0s and 1s?


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

The string 234?

The string 3561?

The string 21 and 54?


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

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)?

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)?

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

Repetition is allowed?

Repetition is not allowed?


Using \(C(n,r) = \displaystyle \frac{n!}{r!(nr)!}\), 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.\)
There are several theorems that can be proven just using the definition of divisibility given above. One such theorem is as follows.
7.1.1. Division Algorithm
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}\] 
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.\)
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.
Additionally, it is not hard to see that \(\gcd(5,3) = 1,\) and thus \(\frac{35}{7}\) and \(\frac{21}{7}\) are relatively prime. In general, we have the following theorem.
Let \(a\) and \(b\) be positive integers. The smallest positive integer \(m\) such that \(a\) divides \(m\) and \(b\) divides \(m\) is referred to as the least common multiple of \(a\) and \(b.\) The least common multiple of \(a\) and \(b\) is denoted by \(\operatorname{lcm}(a,b).\)
Additionally, we observe that \[\gcd(35,21) \cdot \operatorname{lcm}(35,21) = 7 \cdot 105 = 735 = 35 \cdot 21.\] In general, we have the following theorem.
7.1.3. The Euclidean Algorithm
A wellknown method for computing the greatest common divisor and least common multiple of a pair of positive integers is called the Euclidean algorithm. Before describing this algorithm, we state the following theorem.
Let \(a\) and \(b\) be positive integers. We let \(r_0 = a\) and \(r_1 = b.\) Next, we use the division algorithm to find integers \(q_1\) and \(r_2,\) with \(0 \leq r_2 < r_1,\) such that \[r_0 = r_1q_1 + r_2.\]Then, if \(r_2 \neq 0,\) we again use the division algorithm to find integers \(q_2\) and \(r_3,\) with \(0 \leq r_3 < r_2,\) such that \[r_1 = r_2q_2 + r_3.\] We continue this process until we obtain a remainder of \(0\); that is, until, for some positive integer \(k,\) we have \(r_{k+1} = 0.\) Then, we have
\[\begin{split} \gcd(a,b) = r_k,\\ \operatorname{lcm}(a,b) = \frac{ab}{r_k}.\\ \end{split}\] 
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.
Particular values of \(x\) and \(y\) can be found using the Extended Eulcidean algorithm.
7.2. Integer Representations
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_{k1},\dots,a_0,a_1\) as digits. We represent the base \(b\) expansion of \(n\) using the following notation: \[(a_ka_{k1}\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.
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.\)
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_{k1}\dots a_1a_0)_b.\]
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:
We then concatenate our blocks, removing any leading zeros if necessary.
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.
The following table can be used to covert quickly between decimal, hexadecimal, octal binary in a similar way.
Conversion table for different bases
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.
Sequences generated by linear functions as in Example 1 are called arithmetic sequences. Thinking recursively, they are determined by a first term and a common difference. The arithmetic sequence \(a_n=3n+1\), is the sequence whose first term is \(a_1=4\), and whose common difference is \(d=3\) As arithmetic sequences are generated by linear functions \(f\left(x\right)=dx+c\), the general arithmetic sequence is \(a_n=d\cdot n+b\), \(d\) being the common difference. 
Sequences generated by exponential functions as in Example 2 are called geometric sequences. Thinking recursively, they are determined by a first term and a common ratio. The geometric sequence \(b_n=2\cdot3^n\), is the sequence whose first term is \(b_1=6\), and whose common ratio is \(r=3\). As geometric sequences are generated by exponential functions \(f\left(x\right)=a\cdot r^n\), the general geometric sequence is \( a_n=a\cdot r^n\), \(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_{n1}+f_{n2}\) So , \( f_3=f_{31}+f_{32}=f_2+f_1=1+1=2\),
\(f_4=f_{41}+f_{42}=f_3+f_2=2+1=3\),
\(f_5=f_{51}+f_{52}=f_4+f_3=3+2=54\),
\(f_6=f_{61}+f_{62}=f_5+f_4=5+3=8\)
\(f_7=f_{71}+f_{72}=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}\).
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\)
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.
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.
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.
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\)
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\)
Prove the proposition that the sum of the ﬁrst n odd numbers is \(n^2\); that is,
\(1+3+5+···+2n1=\sum_{k=1}^{n} (2k1) =n^2\) for n a positive integer \(n\in\mathbb{Z}\)
For each integer n, let P(n) be the statement \(\sum_{k=1}^{n} \left(2k1 \right)=n^2\) \(P\left(n\right):\sum_{k=1}^{n} \left(2k1 \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} (2k1)=n^2\)
\(\ \sum_{k=1}^{1} (2k1)\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} (2k1)=m^2\)
Write down the lefthand side of P(m+1):
\(LHS\ P(m+1):\ \sum_{k=1}^{m+1}{(2k1)}\)
Extract \( (m+1)1\) from the summation,
\(\sum_{k=1}^{m+1} (2k1)=\sum_{==1}^{m}{(2k1)}+(2(m+1)1)\)
Apply the induction hypothesis by replacing,
\(\sum_{k=1}^{m}{(2k1)}\), with \(m^2\)
\(\sum_{k=1}^{m+1} \left(2k1\right)=m^2 +(2(m+1)1)=m^2+2m+21\)
\(=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} {(2k1)}={(m+1)}^2\). In other words,
\(\sum_{k=1}^{m} {(2k1)}=m^2\),
implies
\(\sum_{k=1}^{m+1} {(2k1)}=(m+1)^2\)
Therefore, the inductive step has been verified.
Prove that \(n! > 3^n\) for every positive integer n with n > 6.
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}\)
Prove the following using the principle of mathematical induction:\(n^2 + n\) is even (or divisible by 2 ), for n > 0.
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
Prove the following using the principle of mathematical induction: \(8^n 3^n\) is divisible by 5, for any positive integer n>0.
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^ n3^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\):\((83)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(83\right)8^m +3\left(8^m 3^m\right)\), \(\left(8^m \left(83\right)\right)+\left(3\left(8^m 3^m\right)\right)\): Determine if each of these terms is divisible by 5 83=5: and \((5\times8^m)+(3(8^m3^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.
8.4. Exercises
Prove using induction.

For all \(n ≥ 1\) prove that \(1+2+3+\ldots+n=\sum_{i=1}^{n}i=\frac{n\left(n+1\right)}{2}\)

For all \(n ≥ 1\), prove that \({23}^n1\) is divisible by 11.

Prove by mathematical induction that \(7\) divides \(2^{4n+2} + 3^{2n+1}\) for all nonnegative integers \(n\).

Prove that for any \(n ≥ 1\), and \(x ≥ 0\), , \(\left(1+x\right)^n\geq1+nx\).

For all \(n ≥ 5\) prove that, \( 2^n>n^2\).

Prove by induction that a set \(A\) with cardinality \(A=n\), has \(2^n\), subsets.

Prove by induction, that there are \(3^n\), numbers in base 3 (using the digits 0 ,1, 2) made up of \(n\) digits.

Prove by induction, that there are \(4^n\), numbers in base 4 (using the digits 0 ,1, 2, 3,) made up of \(n\) digits.

State the principle of induction using a conditional logical statement.

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

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\}\}\)
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.
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, \(\leftE\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\ \leftE\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 \(ith\) row and \(jth\) column and \(0\) otherwise. Denoting by \(m_{i,\ j}\) the component of the adjacency matrix in the \(ith\) row and \(jth\) 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.
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.
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.
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,
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 \(Gv\), 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, \(Gd\) formed by removed the vertex \(d\).
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
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, nonempty, 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 nonempty 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\).
A graph is connected if there is a path from each vertex to every other vertex.
The graph below is not connected,
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.
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.