Discrete Math

Remember: Please read the text linked above before reading the material below.

The most basic way to describe a set is as a collection of unique elements. These elements could be numbers, letters, or any object.

While sets are not ordered, sometimes it is easiest to describe a set by enumerating (listing) the objects it holds, separated by commas, inside a set of brackets.

For example, a set containing the integers between 1 and 10 can be described as written, or it can be described by writing

$${ 1, 2, 3, ..., 9, 10}$$

Since this is a small list, we could also write all the numbers. But imagine a set containing numbers from 1 to 2000. ${ 1, 2, 3, ..., 1999, 2000}$ is much more concise than trying to write all 2000 values. Likewise, if we wanted to describe all positive integers, we might say:

$${1, 2, 3, 4, ...}$$

We leave off the last number, since there is no "last" integer.

The cardinality of a set is the number of elements it contains. Finite sets are sets that have a finite cardinality. For example, our first set has a cardinality of 10, and therefore it is a finite set. The set we have just defined has infinitely many elements. The cardinality of this set is infinite, making it an infinite set.

This way to describe sets work for simple operations on infinite sets, and for most finite sets, but consider this set description:

$${1, 2, 4, ... }$$

This set could describe powers of 2, but it could also describe the sequence given by adding an increasing value to the previous number. 1 + 1 = 2, 2 + 2 = 4, and therefore, the next value would be 4 + 3 = 7. It is important when describing sets to only use enumeration when it is obvious what set it describes.

Mathematicians have developed set notation, which describes a set, or a combination of sets, using mathematical symbols.

Set-Builder Notation can help us construct sets. This is done by defining a variable (or sometimes multiple variables), then creating a mathematical statement with this variable. For any value of this variable, if the statement is true, this value is in the set. Usually the variable(s) and statement are separated by a pipe (|) or the abbreviation s.t., which stands for "such that."

For example, if we want to create our powers of two set, we could write

$${x | x = 2^k \text{ for some integer } k}$$

$x = 2$ is true, since we can choose $k = 1$, while $x = 3$ is false, since we cannot find an integer $k$ for which $3 = 2^k$.

This writing is still more complicated than we would like it to be. It would be nice to represent this in only variables. For this, we will need to learn some more general set notation.

To denote that some value or variable is in a set, we use the symbol $\in$. For example, if value x is in set A, we can say

$$x \in A$$

It is standard in mathematics to represent sets as uppercase letters. This helps to distinguish them from variables that may represent values.

We also have some common sets, which have specific letters that represent them. We use a fancy font or some extra lines in the letters to denote these sets. For example, $\mathbb{N}$ from the list below represents the Natural numbers, while N represents nothing (unless you've defined a set N).

Set Name	Set Symbol	Set Description
Integers	$\mathbb{Z}$	The set containing all integers, positive and negative. These numbers are the numbers which are not fractions.
Natural Numbers	$\mathbb{N}$	The set containing positive integers.
Rational Numbers	$\mathbb{Q}$	The set containing all numbers that can be represented as fractions. All numbers of the form $\frac{a}{b}$, where $a$ and $b$ are integers.
Real Numbers	$\mathbb{R}$	The set containing all real numbers. This includes any non-imaginary number.
Empty Set	$\emptyset$	The set containing no elements

For most of these sets, the cardinality is infinity. We'll come back to these cardinalities later, as we'll find there are a few types of infinity. However, the empty set is considered to have cardinality of zero.

Now that we have some extra notation, we can combine our set notation knowledge with our logical statement knowledge to get

$${x | (\exists k \in \mathbb{Z}), x = 2^k }$$

For a set of powers of two. It can be read "x such that, for some integer k, x is equal to 2 to the k power." We could, if we wished, add to the left hand side that x is an integer as well. Sometimes this helps when there are multiple conditions on x.

Check your understanding: One of the following is the set of all postive real numbers, and the other is a set of all negative real numbers. Try reading the notation to determine which set is which.

$${x \in \mathbb{R}| x > 0 }$$

$${x \in \mathbb{R}| x < 0 }$$

Check your answer

The first is positive real numbers and the second is negative real numbers. This is a good reminder that 0 is neither positive nor negative.

Think about it: Try using set-builder notation to define a set containing only even numbers. As a hint: remember that all even numbers are divisible by 2, and so can be written as 2 times some integer.

Subsets

Applied Discrete Structures, Chapter 6.1-6.3

Remember: Please read the text linked above before reading the material below.

Consider two sets A and B. Set A is a subset of set B if for every element in A, the same element is in B. Mathematically,

$$A \subseteq B = \forall x \in A, x \in B$$

Note this allows A to be a subset of itself! This is called an improper subset, and gives an intuition as to proving set equality.

If we want to prove two sets, A and B, are equal, we can prove that A is a subset of B and that B is a subset of A. This is similar in idea to proving two numbers are equal by showing $a \leq b$ and $b \leq a$. We'll visit this idea more after defining some operations.

Any subset that isn't improper is called a proper subset.

Think first: Given this definition of subset, is the empty set a subset of any sets?

We actually can show the empty set is a subset of all sets. Since it contains no elements, all of its elements are in any set in existance, including the empty set itself.

Given that we have a set that is the subset of all sets, we also define the Universe as the set that is the superset of all sets. In other worse, all sets defined are subsets of the Universe.

The Universe is usually defined by context. It might be all numbers, all letters, all integers, or some other set depending on the problem being discussed. The Universe should be defined in most operations on sets, so these operations themselves can be defined.

Intersection, Union, Difference, and Complement

Chapter 1.2

Remember: Please read the text linked above before reading the material below.

The operation where a Universe is most important is the Complement. The complement of a set is all elements of the universe that are not in the set.

a venn diagram of A complement

The intersection of two sets is the set of all elements they have in common. If two sets have no elements in common, the intersection will be the empty set. Sets which have no elements in common are called disjoint.

a venn diagram of intersection

The union of two sets is the set of all elements they contain. This combines all elements into one set, making sure there are no duplicates since sets must contain unique elements.

a venn diagram of union

The difference of two sets is all elements of the first set that are not in the second set. This can be denoted two ways.

$$B - A$$

$$B / A$$

a venn diagram of set difference (B - A)

Check your understanding: Which of these operations are commutative?

Check your answer

Union and difference are commutative. Complement is only completed on one set, and for difference, the order of the sets matters.

We can combine these operations to create similar identities to the logical laws.

Identity	Name
$A \cup B = B \cup A$	Commutative Law (union)
$A \cap B = B \cap A$	Commutative Law (intersection)
$(A \cup B) \cup C = A \cup (B \cup C)$	Associative Law (union)
$(A \cap B) \cap C = A \cap (B \cap C)$	Associative Law (intersection)
$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$	Distributive Law
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$	Distributive Law
$A \cup \emptyset$ = A	Identity Law
$A \cap U = A$	Identity Law
$(A^c)^c = A$	Double Complement
$A \cup A = A$	Idempotent Law
$A \cap A = A$	Idempotent Law
$(A \cup B)^c = A^c \cap B^c$	DeMorgan's Law
$(A \cap B)^c = A^c \cup B^c$	DeMorgan's Law
$A - B = A \cap B^c$	Set Difference Law

Check your understanding: Try drawing a picture of one of the identities. First draw the left side, then draw the right side. Do your pictures match?

Check your answer

Your answer here depends on your decision, but if your two drawings don't match, try starting again.

To prove these identities, and other relations between sets, we can use subset proofs. We start with an arbitrary element in one side of the identity, and show it exists in the other. This proves a subset relation between the two sets. If we can also show the opposite direction, we have proved equality, as mentioned earlier.

For example, if we wish to prove $A - B = A \cap B^c$

We start by assuming an arbitrary $x \in A - B$

By definition of difference, this means $x \in A$ and $x \not\in B$

$x \not\in B$ means $x \in B^c$ by definition of complement.

$x \in A$ and $x \in B^c$ means $x \in A \cap B^c$ by definition of intersection.

Since $x \in A - B$ implies $x \ in A \cap B^c$,

$A - B \subseteq A \cap B^c$

Now we need to complete the other direction.

Assume we have an arbitrary $x \in A \cap B^c$

By definition of intersection, $x \in A$ and $x \in B^c$.

Since $x \in B^c$, $x \not\in B$ by definition of complement.

$x \in A$ and $x \not\in B$ means that $x \in A - B$ by definition of set difference.

Since $x \in A \cap B^c$ implies $x \in A - B$,

$A \cap B^c \subseteq A - B$

Now we have $A - B \subseteq A \cap B^c$ and $A \cap B^c \subseteq A - B$, which means

$A \cap B^c = A - B$

Think about it: Try completing a subset proof on one of the other identities listed above. The identities involving complement can be tricky, so if you want a challenge, try one of those!

Cartesian Product

Chapter 1.3

Remember: Please read the text linked above before reading the material below.

The cartesian product of two sets is all combinations of an element of the first set with an element of the second. Usually these combinations are denoted using an ordered pair. In set terms, this is

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

The above notation, similar to one version of a multiplication symbol, is how we represent the cross product.

For example, if A = {r, o, b}, and B = {o, p, e}, the cartesian product of A and B is

$$A \times B = {(r, o), (r, p), (r, e), (o, o), (o, p), (o, e), (b, o), (b, p), (b, e)} $$

The cardinality of the cross product of two sets is just the product of their cardinalities. In our example, we had a set of size 3, and another set of size 3, so their cross product had 9 elements.

Check your understanding: What would the Cartesian product of $B \times A$ in this case? Is it the same as $A \times B$? In what cases would it be the same, and when would it be different?

Check your answer

$B \times A$ will be ${ (o, r), (p, r), (e, r), (o, o), (p, o), (e, o), (o, b), (p, b), (e, b) }$

Note that this is not the same as $A \times B$. These ordered pairs are different.

We can also compute the cross product for multiple sets, and show that the cardinality is still just the product of all set cardinalities.

Think about it: Consider sets A, B, C, and D, which all contain 0 and 1. What would their cross product ($A \times B \times C \times D$) contain? How many elements are there in the cross product? Is there an easy way to describe all the ordered sets of four?

Power Set

Chapter 1.3

Remember: Please read the text linked above before reading the material below.

The power set of a set is the set of all possible subsets. This includes the empty set, and the set itself since this is not a set of all proper subsets.

For example, if set A = {k, i, b, o }

The powerset of A is {{}, {k}, {i}, {b}, {o}, {k, i}, {k, b}, {k, o}, {i, b}, {i, o}, {b, o}, {k, i, b}, {k, b, o}, {k, i, o}, {i, b, o}, {k, i, b, o }}

The cardinality of a powerset is 2 to the power of the cardinality of the original set. We'll revisit why this is the case when we discuss counting.

Think about it: Consider the set A containing only 0 and 1 again. What would the power set of this look like? How many elements would it contain? How is this set different from the cross product of A with itself?

Review: Relations

Mathematical Relations denote what relationships exist between objects of two sets. Next week, we will discuss the relationship between relations and functions.

Readings

Please read this first before moving on to the documents here on Anchor. As a reminder, and for reference, specific chapters are referenced at the beginning of the section for which they are relevant. Feel free to go back to the text(s), or review it if there's been a break since you last read the material. The readings on Anchor have some information in common with the text(s). This is to ensure you see the information from some different perspectives.

Mathematical Definition

Chapter 6.1

Remember: Please read the text linked above before reading the material below.

A relation is any subset of the cross product of two sets. The relation will contain all ordered pairs that are related. Note that relations are sometimes directional. An element a may be related to b, but this doesn't mean b is related to a. We sometimes denote a relation as $aRb$, meaning $a$ relates to $b$.

A simple example. Let set A = { m, a, t, h }, and set B = {1, 2, 3 }

A simple relation could be ${(m, 1), (m, 3), (t, 1)}$

We could also define a relation by a rule. We could have a relation that states that consonents are related to even numbers, and vowels are related to odd numbers. In our sets, this would result in the relation

$${ (m, 2), (a, 1), (a, 3), (t, 2), (h, 2) }$$

We can also define relations on a set to itself. It's quite common to define a relation on sets like the integers or real numbers. For example, we can define a relation that states that every integer is related to the next consecutive integer.

$${... (-3, -2), (-2, -1), (-1, 0), (0, 1), (1, 2), (2, 3), ... }$$

Check your understanding: Create your own example of a relation. What two sets are you pulling the relations from? Does your relation have infinitely many elements or only a finite number of elements?

Check your answer

The answer here depends on the relation you made. If you created a relation on finite sets, you should only be able to make a finite number of relations. If you have an infinite set, you could make infinitely many relations or finitely many relations.

Visual Representations

Chapter 6.1 and 6.2

Remember: Please read the text linked above before reading the material below.

We can represent relations using a diagram. This only works well for small examples, but can help visualize the relation and relation properties.

An example of a relation

Properties of Relations

Chapter 6.3

Remember: Please read the text linked above before reading the material below.

There are a few important properties of relations. These properties help us to classify relations, and will help in our definition of equivalence relation later.

Note that these properties are defined for a relation on a single set. We will not discuss what happens for a relation on two different sets.

Symmetric

A symmetric relation requires that if a is related to b, then b is related to a. Basically, this ensures no directional relations.

An example of a symmetric relation

Reflexive

A reflexive relation requires that every element in the set is related to itself.

An example of a reflexive relation

Transitive

A transitive relation states that if a is related to b, and b is related to c, then a is related to c. It is similar to the idea of transitivity present in other parts of mathematics.

The first image example of a relation is transitive. The symmetric example is not.

Check your understanding: Is the reflexive relation pictured above transitive?

Check your answer

Yes! Since this is a simple relation, it also happens to be transitive.

Antisymmetric

A relation is antisymmetric if a relating to b and b relating to a implies that a=b. In other words, there are only directional relations (including those that point to themselves).

Irreflexive

A relation is irreflexive if no element is related to itself.

It may seem on first glance that symmetric is the opposite of antisymmetric and reflexive is the opposite of irreflexive. However, there are relations which are both symmetric and antisymmetric ($R_1$). There are also relations which are neither symmetric nor antisymmetric ($R_2$). There are relations that are neither reflexive nor irreflexive as well($R_3$).

Think first: Can you come up with a simple relation that is both symmetric and antisymmetric? What about one that is neither reflexive nor irreflexive?

Let $A = {1, 2, 3}$

$$R_1 = {(1,1), (2,2), (3,3) }$$

An image representation of $R_1$

$$R_2 = { (1,2), (2, 1), (3, 1) }$$

An image representation of $R_2$

$$R_3 = { (1,1), (2,2)}$$

An image representation of $R_3$

You cannot assume that if a set is symmetric, then it is not antisymmetric, or vice versa. The same applies to reflexive and irreflexive. Make sure to refer back to the definitions when identifying which properties apply to relations.

Let's look at some familiar relations and practice.

Consider $aRb$ if $a < b$ (a is less than b).

This is not symmetric. $1 < 2$, but $2 \not< 1$.

This is not reflexive. $1 \not< 1$.

This is transitive. If $a < b$ and $b < c$, then $a < c$.

This is antisymmetric. There is no case where $a < b$ and $b < a$, the first part of the implication is never satisfied.

This is irreflexive. $a < b$ implies that $a \not= b$.

Now consider $a \leq b$ instead.

Think first: What changes?

It becomes reflexive, and irreflexive is no longer true. Antisymmetric is still true since when $a \leq b$ and $b \leq a$, this requires that $a = b$.

Consider the relation $aRb$ when $a = b$

Check your understanding: What properties hold for this relation? Which properties fail? Where is it different from $a \leq b$?

Check your answer

This is reflexive, symmetric, and transitive. It is also antisymmetric, just like $a \leq b$. This relation is also clearly not irreflexive. So it has the same properties as $a \leq b$, except that it is now also symmetric!

Equivalence Relations

Chapter 6.3

Remember: Please read the text linked above before reading the material below.

You should notice that for equality (of real numbers), the relation is reflexive, symmetric, and transitive. Any relation that has these three properties is known as an equivalence relation.

Let's look at some other equivalence relations.

Let R be a relation on the set of integers. aRb when a and b have the same remainder when they are divided by 7.

This is reflexive, since any number will have the same remainder as itself when divided by 7.

This is symmetric since numbers will always have the same remainder when dividing by 7. The order we say them in does not matter.

This is transitive. Let a and b have the same remainder k. If bRc, then c also has remainder k. Since a and c have remainder k, then aRc.

7 is not a special number, we could replace it with any other positive integer and still have an equivalence relation. This is how equivalence under modulus is defined, which we will re-visit in a few weeks.

A silly example would be a relation defined on people, where two people are related if they have the same last name.

In Geometry, one equivalence relation would be a relation on triangles where two triangles are related only if they are similar to each other.

Check your understanding: Try proving to yourself that one of the relations mentioned above is an equivalence relation. Remember, you need to show that it is symmetric, reflexive and transitive.

Check your answer

Your answer here depends on the relation chosen, but just be sure to show that it is symmetric, reflexive, and transitive, as we did in the example above.

A special example of a relation that is not an equivalence relation is the empty relation on a non-empty set. This relation is symmetric and transitive, since there are no numbers to compare in the relation. However, this is not reflexive since there are numbers in the set which are not related to each other.

LaTeX

LaTeX is a system for mathematical typesetting. It formats mathematical statements alongside text in a neat, easily-readable manner.

Readings

These texts are recommended, but not required. It may contain useful information, or information stated in a different way.

Document Features

I would recommend trying these commands out as you read. Copy-paste them into a new LaTeX document!

To get started, create an Overleaf account, and click New Project, then Blank Project. Whenever you edit the LaTeX on the left hand side, you'll need to click the compile button to see your changes.

LaTeX files have the extension .tex, and these are the files to be edited. When compiled properly, using either Overleaf or a LaTeX compiler downloaded onto your machine, a PDF document will be created.

A LaTeX document can come in many forms, and needs a document type. Overleaf does this automatically. The top of many .tex files has the following command:

\documentclass{article}

Which specifies that the document is an article. There are other types, but this is more advanced than is necessary for a Discrete Math course.

Underneath the document type, packages can be added. This works similarly to programming packages. They allow for better commands, the addition of certain symbols, or some other addition that will improve the quality of the person writing the document, or the appearance of the document itself. The \usepackage command is needed to include a specific package. Overleaf automatically includes the graphicx package to allow for adding images to a document.

\usepackage{graphicx}

Underneath any packages, the title, author, and date of the document is often specified. To make these appear in the document, the \maketitle command is used inside the document.

\title{Example Title} \author{Kiera Gross} \date{January 2024}

All commands mentioned, with the exception of the \maketitle command, exist in the Preamble portion of a .tex file. These must all be placed before the \begin{document} command, which should contain the actual contents of the document to be displayed. This is why the \maketitle command exists inside the document. It tells the compiler to add these features to the final PDF.

\begin{document}

\maketitle

\end{document}

There is an end to the document as well. Be sure to place any content between the beginning and end of the document.

Basic Text Features

The last part of LaTeX that Overleaf automatically creates is a section. Use the \section command to separate into a new section of the document.

\section{Introduction}

This is more useful for research papers, but will appear in homework documents to separate questions.

Typing sentences in LaTeX seems normal until a paragraph is needed. To create separate paragraphs, use two newlines, or a double backslash.

Paragraph one here. \\

Paragraph two here.

Experiment with both. Note that the indentation may be different depending on the method chosen.

Italics, Bold, and Underline can all be done in LaTeX documents with simple commands.

\textit{Italic text}

\textbf{Bold text}

\underline{Underlined text}

LaTeX, in a fashion more similar to programming languages, allows in-line comments. Using the percent symbol (%) before any block of text will remove the text from the final PDF, only to be seen in the .tex file.

% this sentence would be a comment in a LaTeX file

Advanced Text Features

The \begin command is not limited to beginning the document. This can also be used to create lists. Using enumerate creates a numbered list, while itemize creates a bulleted list. For both, use the begin and end commands, and use the \item command for each item in the list.

\begin{enumerate}

\item first item

\item second item

\end{enumerate}

\begin{itemize}

\item first bullet point

\item second bullet point

\end{itemize}

Tables can be done similarly, with the tabular used in the begin and end commands. rows are separated by a double backslash. Columns are separated by an ampersand (&). Directly after the begin command, specify the justification of each column (left (l), center (c), or right (r)), and whether lines should be drawn between them (using the pipe symbol: |). For lines between rows, use \hline after the double backslash.

\begin{tabular}{ l | c c }

corner & item 1 & item 2 \\

\hline

row 2 & row 2, item 1 & row 2, item 2 \\

row 3 & row 3, item 1 & row 3, item 2

\end{tabular}

New LaTeX users should try changing different aspects of the table to see what happens.

For images, we need the graphicx package mentioned earlier, as well as the image file. When using Overleaf, this file must be uploaded to the project. Then use the begin and end command with figure as the input. Inside the figure, include your image using the \includegraphics command with the name of the file. Do not include the extension (.png, .jpeg, etc)!

\begin{figure}

\includegraphics{ImageNameWithoutExtension}

\caption{Add a caption here.}

\end{figure}

This will add the image to the document. LaTeX may place this image in an odd spot, as it wants to optimize the way the document looks. There are some additional commands that can be added to fix the size and location of the image. For a challenge, try finding how to center an image, how to set it to a specific size, and how to make it appear on the document where it appears in the .tex file.

To include hyperlinks in LaTeX documents, the hyperref package is needed.

\usepackage{hyperref}

Remember to put this in the preamble. Then, in the document, the \href command can be used.

\href{overleaf.com}{This is a Link}

The way links look by default can be odd, but changing the style is more advanced. There is documentation on how this might be done. Try finding one that would make links appear in a similar manner to most of the internet.

Math Mode

Everything mentioned so far deals with adding text to a document. However, LaTeX's appeal is that it can format mathematical statements. To write mathematical statements, we must enter "math mode," which tells LaTeX that the text should be made into symbols rather than displaying as-is. There are three main ways to do this. One is to use double dollar signs ($).

$$ x = y $$

This will appear in math mode. Even with a simple statement, there is some difference between x = y in math mode and in text mode.

The other method is to use the begin and end commands with equation as input.

\begin{equation}

x = y

\end{equation}

This will also enter math mode, but it will also identify this particular math as an equation, and add a number as a label.

Another way to specify an equation without having a number appear is to use a backslash with brackets (\[ \])

\[ x = y \]

All methods have their uses, but it is overall more common to see the dollar signs in use for simple assignments.

Mathematical Notation

Most necessary mathematical notation will be provided in the first assignment. However, I recommend you experiment with different commands before attempting the assignment. Start with simple mathematical notation. How are fractions created in LaTeX? Exponents? Can you re-write some old problems or portions of the textbook using LaTeX?

In general, as is true in most of computer science, when you do not know how to do something, consult some documentation. Overleaf provides nice tutorials, and they often appear as the first result on a search engine for any LaTeX-related queries.

Detextify is a useful tool if you cannot remember the name of the symbol you desire. Draw the symbol, and this service will attempt to find similar symbols. Be sure to use the package next to the symbol you choose before attempting to use the command in your LaTeX document! The app will also include whether the command is to be used in math mode or text mode.

Week 1: Self-Guided Problems

When you come to class, be ready to discuss these questions, and bring any additional questions you still have after this exercise!

For the first week only, this Self-Guided exercise is due by Friday. All other Self-Guided Problem Sets will be due before class starts.

Submitting Your Work

Your work must be submitted to Anchor for degree credit and to Gradescope for grading.

For any work completed outside of GitHub or Gradescope:

Typeset your work in LaTeX.

You should use \begin{enumerate} to create a numbered list, and your solutions to each problem should match with the corresponding number on the assignment.
For example, if an assignment has 10 numbered problems, your enumerate should have 10 \item commands, with your solution(s) to problem 1 under the first \item, problem 2 under the second and so on.
If you skip a problem, just leave the \item blank, otherwise the numbers of your solutions will not match the assignment document.

Compile into a PDF. This can be done easily through an Overleaf account, otherwise you will need to install LaTeX.
Submit the pdf to Gradescope via the appropriate submission link for the course.
Upload the pdf to Anchor using the form below.

Note: Anchor submissions can occur at any time during the term, but it is critical that you upload all of your work to Anchor before the last day of the term. Gradescope submissions must be submitted before the deadline (or the late deadline, if applicable).

It is required that all assignments are submitted as a PDF generated from a LaTeX document.

Assignments submitted in any other form will earn zero credit.

Self-Guided Problems cannot be submitted late for any reason

This is due to the fact we discuss them in the class. Be sure to stay on top of these Self-Guided problems, and remember it is better to turn in an incomplete set than an empty one.

Relevant Links

Overleaf Tutorial, Detextify

Problems

Create an account with Overleaf. Then create a new document. What are the commands Overleaf includes for you? What do they do?
Try importing some math-related packages. Here are some examples:
- \usepackage{amsmath}
- \usepackage{amsfonts}
- \usepackaged{amssymb}
What are some example notations you can use from these packages?
Try finding a mathematical symbol using a search engine, by searching for it by name. Try finding a mathematical symbol using Detextify, by drawing it.
a. Which is easier?

b. Did you need any additional packages to support the symbol?

Try typesetting a simple mathematical expression twice, using 2 different ways to enter math mode.
a. What’s the difference?

b. Are there any specific situations where you would choose one over another?

c. How can you handle text in mathematical expressions?
Try creating a numbered list of items and a bulleted list of items.
How do you create separate paragraphs in LaTeX?

Homework Set 1

Submitting Your Work

Your work must be submitted to Anchor for degree credit and to Gradescope for grading.

For any work completed outside of GitHub or Gradescope:

Typeset your work in LaTeX.

You should use \begin{enumerate} to create a numbered list, and your solutions to each problem should match with the corresponding number on the assignment.
For example, if an assignment has 10 numbered problems, your enumerate should have 10 \item commands, with your solution(s) to problem 1 under the first \item, problem 2 under the second and so on.
If you skip a problem, just leave the \item blank, otherwise the numbers of your solutions will not match the assignment document. Here is an example Overleaf document showcasing this format.

Compile into a PDF. This can be done easily through an Overleaf account, otherwise you will need to install LaTeX.
Submit the pdf to Gradescope via the appropriate submission link for the course.
Upload the pdf to Anchor using the form below.

Note: Anchor submissions can occur at any time during the term, but it is critical that you upload all of your work to Anchor before the last day of the term. Gradescope submissions must be submitted before the deadline (or the late deadline, if applicable).

It is required that all assignments are submitted as a PDF generated from a LaTeX document.

Assignments submitted in any other form will earn zero credit.

[5 points] Why do we pronounce the X in LaTeX differently than one might expect in English?
[10 points] Add an XKCD comic to your document. You should add the comic as an image, and add a link to the XKCD site to credit the creators. The link should be clickable in the final PDF.
[10 points] If you had a truth table in a CSV file, and wished to transfer it into LaTeX, would you re-write it by hand or create a program that would typeset the table for you? If you would re-write it, explain why. If you would create a program, write some pseudocode.
[5 points] Create an example of each of the following in LaTeX: A fraction, an exponent, the greek letter $\sigma$ (sigma), uppercase $\Sigma$ (sigma), and an expression with at least two variables.
[10 points] Create a truth table for the following expression: $\neg (p \vee q) \wedge r$.
[10 points] Show that the following expressions are equivalent:

$$(p \vee q) \rightarrow \neg r$$

$$\neg r \vee (\neg p \wedge \neg q)$$

[10 points] Use a subset proof to show that $(A \cap B) \cup (B \cap C) \equiv B \cap (A \cup C)$.
[10 points] Write the following in mathematical notation: Set A contains ordered pairs of integers such that these pairs add to 10 or multiply to 16.
[10 points] Give an example of an equivalence relation, and prove that it is an equivalence relation.
[10 points] Create an Antisymmetric relation on ${1,4,9,16,25}$.
[10 points] If a relation is not reflexive, does that mean it is irreflexive? If this is true, prove it. If it is false, provide a counterexample.

Sequences and Functions

This week, we'll cover sequences and functions. While some material should be review from Mathematical Thinking, we will cover some new topics in these fields.

By the end of the week, you should be able to:

Identify and solve arithmetic and geometric sequences/series.
Recall other methods to solve series.
Analyze simple functions.
Determine the type and inverse of simple functions, as well as their compositions.
Prove a function is injective, surjective, or bijective.
Prove a set is countable.

Readings

Applied Discrete Structures, Chapters 2.1-2.2, 7.1-7.3

Sequences

Sequences, like sets, are a mathematical structure. They allow us to talk about numbers in sequence, as the name implies.

Readings

Please read this first before moving on to the documents here on Anchor. As a reminder, and for reference, specific chapters are referenced at the beginning of the section for which they are relevant. Feel free to go back to the text(s), or review it if there's been a break since you last read the material. The readings on Anchor have some information in common with the text(s). This is to ensure you see the information from some different perspectives.

Discrete Mathematics: An Open Introduction, Chapter 2.1-2.2

Sequence Definition

Chapter 2.1

Remember: Please read the text linked above before reading the material below.

A sequence is an ordered list of objects. We'll only be discussing numerical sequences here. The sequence of natural numbers could be written:

$$0, 1, 2, 3, ...$$

In fact, we usually use the natural numbers as indices when writing out a general sequence. We do this because, in mathematical terms, a sequence is a function from the natural numbers to a value.

$$a_0, a_1, a_2, a_3, ...$$

If we want to discuss the $k$th item in a sequence, we sometimes say $a_{k-1}$.

Check your understanding: Why is the kth item $a_{k-1}$?

Check your answer

Just like indexes on a list, we have the problem that we start our labels at $0$ but verbal labels start at $1$ (the first item).

Likewise, to refer to the whole sequence we put one representative in parentheses.

$$(a_n)$$

We only do this with variables. We can do this to refer to a series if we have defined what $a_n$ is, usually in terms of previous members of the sequence, or some other mathematical statement.

For example, if we want the sequence of square numbers,

$$a_n = n^2$$

Or if we want a sequence where each number is two more than the previous number,

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

Note that we should define $a_0$ for each sequence as well, so we can tell where it starts.

Check your understanding: if $a_0 = 0$ and $a_n = a_{n-1} + 2$, what types of numbers are in this sequence? There should be a good name that refers to the numbers listed here. What happens when $a_0 = 1$ instead?

Check your answer

For the first sequence, we get the positive even numbers (plus zero).

The second sequence gives the positive odd numbers.

Since a sequence is a function, any function that has a domain of the natural numbers can be easily transformed into a sequence. For example,

$$a_n = 2n + 3$$

Would be a sequence where each value are integer values of the function $f(x) = 2x + 3$. Note that $a_0$ is defined already.

Check your understanding: what would $a_0$ be for this sequence?

Check your answer

Since it's the natural numbers, the first $x$ value is $0$, and our $a_0 = 2 \cdot 0 + 3 = 3$

We can also define sequences in terms of other sequences. This is the idea behind partial sums.

Pretend there is a Kibo course where students learn five new topics each week. The sequence of topics learned per day would simply be

$$5, 5, 5, 5, ...$$

However, what if we want to measure how much a student has learned so far?

On the first day, they learn 5 topics.

On the second day, they learn 5 more topics, for a total of $5 + 5 = 10$. This is a partial sum of our initial sequence. We add the first term to the second to get the second day total.

And this continues, each day $5$ topics are added.

$$5, 5+5, 5+5+5, 5+5+5+5, ...$$

A sequence of partial sums is created by taking the sum of $a_0$ to $a_{n-1}$ for the $n$th term of the sequence.

Check your understanding: If our initial sequence is the odd numbers, what does the sequence of partial sums look like? Try finding a few terms, and see if you can spot the pattern.

Check your answer

$1 = 1$

$1 + 3 = 4$

$1 + 3 + 5 = 9$

$1 + 3 + 5 + 7 = 16$

These are the square numbers! The partial sum sequence would be:

$1, 4, 9, 16, 25, ... $

Sequence Versus Series

A series is defined as being the sum of each term in a sequence. For example, if we have the sequence of the positive integers, the series would be the sum of the posititive integers, which would be infinite. In general, many infinite series may end up resulting in an infinite answer, however, some have a solution! If we have a finite sequence, there should be a finite answer, though how easy this is to compute depends on the series.

These terms are related, and it is easy to get them confused, especially since they are similar sounding words. However, a sequence should never contain a sum, and a series should usually have some final answer when computed (which may be infinity).

Special Sequences

Chapter 2.2

Remember: Please read the text linked above before reading the material below.

There are two main types of sequences that have very nice ways to solve for the nth term, or for the sum of the sequence.

Arithmetic Sequences

An arithmetic sequence is a sequence where each term is $k$ more than the previous term. This $k$ is known as the common difference. An arithmetic sequence can be defined by the initial term ($a_0$) and the common difference.

Earlier, we defined a sequence

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

Let's consider this sequence with $a_0 = 1$. The common difference will be $2$, since this is what we add to each term. This would give us the sequence of positive odd numbers! So, it turns out that odd numbers are an arithmetic sequence.

Check your understanding: How could we transform this series to instead get the sequence of positive even numbers?

Check your answer

Let $a_0 = 2$. Note that $0$ is not positive, so we can't include it.

In general, an arithmetic sequence can be written:

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

However, there's an easier way of finding the $a_n$th term.

Notice:

$a_1 = a_0 + k$

$a_2 = a_1 + k = (a_0 + k) + k = a_0 + 2k$

$a_3 = a_2 + k = (a_0 + 2k) + k = a_0 + 3k$

A pattern begins to appear. We should be able to reason through this as well. At the $a_n$ term, $k$ has been added $n$ times in total since the start. So,

$$a_n = a_0 + nk$$

Notice that this is not the $n$th term, but the $n+1$st term, since we start at $a_0$.

If we wish to find the final solution to an arithmetic series, this is simple. Add the terms. However, a long series could prove a challenge.

Let us start with the simple example of the sequence of positive integers up to $n$

$$1, 2, 3, 4, ... , n-1, n$$

If we start adding from the start of this sequence, there seems to be no pattern in the results, other than adding one more than one was added previously. This doesn't help us for a general case, like the one given above.

However, addition is commutative, we can add these terms in any order.

We can notice if we take terms from the front and back of the sequence, the sum is always $n+1$, so we rearrange the series to sum it:

$1 + n$ + $2 + (n-1)$ + $3 + (n-2)$ + ...

Our next task is to find how many $n + 1$ terms we have.

If we're taking from both sides, when we stop, we'll be at the middle of the sequence. Half of the sequence will be before this point, and half will be after. We will have created a group once per term on the left hand side of this midpoint, so in total, there should be $\frac{n}{2}$ of these $n + 1$ terms.

Therefore, our total should be $\frac{(n + 1)n}{2}$

This gives us the closed form sum of a finite arithmetic series from $1$ to $n$ with common difference $1$. A closed form is just a single expression that is the solution to an expression with a much longer form.

$$1 + 2 + 3 + ... + (n-1) + n = \sum_{i=1}^n i = \frac{(n + 1)n}{2}$$

Another way to view this process is to think of writing our series backwards:

$$n + (n-1) + (n-2) + ... + 2 + 1$$

This is still the same as our original, we just moved around additions again!

If we add this series to our original series, matching the terms together, we find that same phenomenon of the $n+1$ sum.

$$n + (n-1) + (n-2) + ... + 2 + 1$$ $$+ 1, 2, 3, 4, ... , (n-1), n$$ $$(n+1) + (n+1) + (n+1) + ... + (n+1) + (n+1)$$

Here, it may be easier to see that there are $n$ of these $n+1$ terms, since there's one for every member of the sequence.

However, we've added our sum to itself, so our answer is $2$ times more than what it should be, and we get the same closed form as before: $\frac{(n+1)n}{2}$

Think about it: How can we expand this closed form to any arithmetic series? Try finding the closed form of the sum of even numbers from $2$ to $n$. This has a common difference of two instead of one. What happens there?

And what happens if you try to find the sum starting from some other value, like $4$ instead of $1$ in our original sequence with common difference $1$?

If you get stuck, try computing a few of the series and seeing if you notice a pattern in the answers other than the common difference. Compare these answers to each other, and to the answers we would get for the series we solved above. Stick to positive integer terms in your experiments, we'll get to fractions and negative terms after the next topic.

Geometric Sequences

A Geometric sequence is a sequence where each term is $k$ times the previous term. This $k$ is known as the common ratio. A Geometric sequence can be defined by the first term and the common ratio.

Instead of adding $2$, if we start at $1$, and multiply by $2$ to form each term, we get the sequence of powers of $2$:

$$1, 2, 4, 8, 16, 32, ... $$

Check your understanding: What happens if the starting number is changed to a $2$? A $3$? A $0$?

Check your answer

$2$: the sequence shifts forward by one value. These should still be powers of $2$

$3$: Every power of two is just multiplied by a single $3$.

$0$: All the terms would be zero. Boring!

In general, a geometric sequence can be written:

$$a_n = ka_{n-1}$$

With a defined $a_0$ term.

To find the $n$th term, let's think about the sequence from the start.

The first term will be $a_0$

$a_1 = ka_0$

$a_2 = ka_1 = k(ka_0) = k^2a_0$

$a_3 = ka_2 = k(k^2a_0) = k^3a_0$

For the $a_n$th term, we will have

$a_n = k^na_0$

Similar to the arithmetic sequence, this is the $n+1$st term in the sequence as a whole, since we start at $a_0$.

If we wish to find the closed form of the geometric series, we need to be even more clever than before.

Let's consider the powers of two up to $2^n$

$1 + 2 + 4 + ... + 2^{n-1} + 2^n$

We can't match terms from both ends this time, but we can do other things to the entire series if we undo the changes at the end.

Consider the same series, multiplied by $2$

$2 + 4 + 8 + ... + 2^n + 2^{n+1}$

This series has almost all the same terms! Let's call our series $S$. This makes the second series we found $2S$.

If we subtract our original series from the new series, all terms but two will cancel with each other! The last term of the second series and the first term of the first.

$2S - S = 2^{n+1} - 1$

If we want to know what $S$ is, we can solve algebraically

$S(2-1) = 2^{n+1} - 1$

$S = \frac{2^{n+1} - 1}{2 - 1}$

This answer for the series of powers of two should make sense for those familiar with binary. Adding every power of two up to $2^n$ would represent a $1$ in each digit. If $1$ was added, it would turn into the next power of $2$, $2^{n+1}$. Therefore the value is $2^{n+1} - 1$.

Think about it: How would this change for powers of three? What would we multiply the series by in the first step? What is the general form for a series for $b$ to a power? What would change if the starting term was different?

Infinite Arithmetic and Geometric Sequences

These have been closed forms for finite series. What if we want the sum of an infinite series? How can we tell if the sum should result in infinity or a finite value?

Infinite arithmetic series always turn out to be infinite in their final sum, unless the common difference is zero, and our first term is also zero. This should make sense, as there is no number we can add an infinite amount of times that wouldn't result in infinity, even if it was slow to reach infinity.

For geometric series, we can multiply by a common ratio between $-1$ and $1$. This will ensure the terms shrink as the series continues.

We can find the closed form in a similar way to the finite version. We'll have $S$ and $kS$, where $k$ is the common ratio. Because there are infinite terms, now the "last" term of $kS$ will also cancel, since each term in $kS$ is also present in $S$. The first term, $a_0$, in $S$ will be the only term that is not present in the other series.

$kS - S = -a_0$

Multiplying by $-1$ on both sides,

$S - kS = a_0$

$S(1-k) = a_0$

$S = \frac{a_0}{1-k}$

This is the closed form for a geometric series.

This should make sense from our finite closed form. The $2^{n+1}$ term grows because $2 > 1$. If the base of the exponent, let's call it $k$, was a fraction, as $n$ increases, $k^n$ becomes smaller until it is practically $0$.

Of the terms left, if the top and bottom of the fraction are multiplied by $-1$, we are left with the first term on top, and $1 - 2$ in the denominator, where $2$ is the common difference.

There is no real difference in the equation for an infinite geometric series, we just assume that $k^n$ vanishes as $n$ increases.

Oscillating Sequences

It is frustrating that we cannot find a closed form for arithmetic series, and we can for geometric, but only under specific terms.

An Oscillating sequence cycles between values. This means an infinite series is either infinite, since it is either true that this cycle adds to a value, which will continue summing to infinity, or it's undefined if the cycle sums to zero, since we'd have to know that the infinite series ends on the last term of the cycle, or know the last term on which it ends, which we can't say.

For finite sums, finding a closed form can be difficult, since it will depend what point of the cycle the sum ends. It takes more consideration than the arithmetic or geometric sums do, but it is possible.

Think about it: Start with the oscillating series that cycles over $1, 2, 3$. So this sequence is $1, 2, 3, 1, 2, 3, ...$. Find the sum for $1$ term, $2$ terms, all the way up to $12$ terms. Is there a pattern? How would you describe the sum for the $n$th term?

Telescoping Sums

One last special series involves adding and subtracting terms. Specifically, a telescoping series is a series where these terms which are added and subtracted cancel each other out, except for the first and last term. For example, consider

$1 + 2 - 2 + 3 - 3 + 4 - 4 + ... + 9 - 9 + 10$

This makes closed forms very simple! The final answer for this series in particular will be $1 + 10 = 11$. If the series continues up to $n$, the resulting sum will be $n + 1$.

While not mathematically interesting when viewed in this way, finding a telescoping sum in a problem can make computation simple.

In general, it takes a sharp intuition to solve telescoping sum problems, as they are not always obvious.

Consider the sum of numbers where the $n$th term has the value

$\frac{1}{n(n+1)}$

This can be re-written as a telescoping series!

$\frac{1}{n(n+1)} = \frac{1}{n} - \frac{1}{n+1}$

So the sum of this series will simply be $1 - \frac{1}{n+1}$, since all terms in the middle will cancel.

Sequence Rules: Convergence

What does it feel like to invent math?

We've found that some series have closed forms for an infinite number of terms, and some don't. If an infinite series has one, non-infinite solution, it is called convergent. If it does not, it is called divergent.

There are some rules and tests we can use to test if a series is convergent. These are beyond the scope of the course, but curious students may research this topic to see some interesting examples of convergent series.

The series $1 - 1 + 1 - 1 + 1 + ...$ diverges, since it cannot be determined whether the value will be $1$ or $0$. The series $1 + 2 + 3 + 4 + ...$ and $1 + 1 + 1 + 1 + ...$ also diverge since they are infinite. The series $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + ...$ is called the Harmonic series, and is known to be divergent.

However, $1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \frac{1}{5} - ...$ converges to a strange value, $\ln{(2)}$.

It can be very hard to tell which series are convergent or divergent, but it is important to consider this before completing any math with series, as ignoring the convergence and divergence of series can have some interesting results.

Breaking Sequence Rules

What does it feel like to invent math?

To come up with values that "make sense" in the normal idea of mathematics, we must stick to the rules of series. However, when we don't follow these rules, some interesting math appears. Watch the following 3Blue1Brown video on the topic. You may have to pause or rewind the video to think about what the narrator is saying.

This math is not the typical math most people encounter, however, it is a valid field with some interesting applications. Often, even the math that makes no sense at first becomes applicable to real life scenarios.

In our exercises, we will stick to simpler series, but the ideas behind this different math are interesting enough to discuss.

Functions

Functions have slightly different definitions in programming versus mathematics. Mathematical functions allow us to define specific relations and discuss what properties these relations might have.

Readings

Please read this first before moving on to the documents here on Anchor. As a reminder, and for reference, specific chapters are referenced at the beginning of the section for which they are relevant. Feel free to go back to the text(s), or review it if there's been a break since you last read the material. The readings on Anchor have some information in common with the text(s). This is to ensure you see the information from some different perspectives.

Applied Discrete Structures, Chapter 7.1-7.3

Function Definitions

Chapter 7.1

Remember: Please read the text linked above before reading the material below.

The basic idea of a function is that every possible input is turned into exactly one output. This is the basic structure any function must follow.

Think about it: Which of the following are functions?

Inputting a student name, and the output gives the student's ID.

Inputting a grade, and the output is a student who earned that grade.

Inputting an email address, and the output is the student associated with the email.

Inputting a course name, and the output is a student in the course.

We typically denote functions with an $f$ symbol (or occasionally other letters), with the input in parentheses directly after. For example, $f(2)$ would indicate what the function output is, for an input of 2.

If we already know the answer, we can say what it is! If our function is simply to multiply the input by 2, then we know $f(2) = 4$.

We can also use this to define our function. So for any input $x$, we know the output will be simply $2x$, so we can write

$$f(x) = 2x$$

Check your understanding: This function will end up outputting only even numbers when integers are the input values. Can you change the function to make it output only odd numbers with integer-valued inputs?

Check your answer

$f(x) = 2x + 1$ or $f(x) = 2x - 1$ are the simplest answers, though there could be others!

Functions and Relations

A function can also be defined as a relation, where each element of the first set is related to exactly one element of the second set. For example, from our student function above, we have the relation from the set of students to the set of email addresses, where a student is related to their email address. We can complete pictures as we did with previous relations.

An example of a function as a relation diagram

Domain and Co-domain

When defining functions under relations, we say that every element of the first set is related to some element in the second. We call the first set the domain and the second set the codomain. Note that we only specify that every element of the domain must be useable by the function, the codomain can have elements that are not outputs of the function.

Remember the function $f(x) = 2x$.

Since we're dealing with numbers, we could define the domain as the Integers or the Real Numbers. If we do this, we'll likely define the codomain as the same, even though we know the output will be only even numbers. When we define a numerical function, we usually use our set notation to describe what domain and codomain we will be using. Since a function is a relation from the domain to the codomain, this is usually denoted with an arrow between.

$f: \mathbb{R} \rightarrow \mathbb{R}, f(x) = 2x$

$f: \mathbb{Z} \rightarrow \mathbb{Z}, f(x) = 2x$

Check your understanding: Which of these functions is only defined on even integers?

Check your answer

The second is defined only on the integers, and is therefore only defined on even integers. It's the only one to guarantee even numbers as output as well.

Notice for the other function, I could let $x = \frac{1}{2}$, and it would output 3, which is certainly not even.

The image above and below both depict this type of function, however, the one below might be misleading, as it does not include all values in the codomain. It is not immediately clear that the one above is for the function $f(x) = 2x$, since it cuts off before $4$ and $6$, so neither diagram is perfect, which is why we use notation rather than images.

Another example of a function as a relation diagram

Image and Range

As noted prior, $f(x)$ for any given function represents the value it takes in the codomain. $f(x)$ is known as the image of x under $f$.

The collection of images for all possible $x$ in the domain is known as the range of a function.

Think first: The range will be a subset of the codomain, since it's the set of images under the function. Is there a simpler way you could describe the range of a function?

We can also think of the range as all possible outputs of the function.

An annotated diagram of a function as a relation diagram

Multiple-Variable Functions

Chapter 7.1

Remember: Please read the text linked above before reading the material below.

We can also define functions that take in multiple values. For example, consider the simple function:

$$f(x, y) = x + y$$

We still need to be careful that each input maps to only one output. However, each input is now not just a single value. The input $(1, 2)$ is different from $(2, 1)$, so if these were to result in different values, this would still be an acceptable function.

Think about it: What multi-variable functions exist in real life?

Injective, Surjective, Bijective Functions

Chapter 7.2

Remember: Please read the text linked above before reading the material below.

Functions can fall into a few important categories.

Injective functions require that every input maps to a unique output, that is, no two inputs result in the same output. Mathematically, we write that

$$f(a) = f(b) \rightarrow a = b$$

An example of an injective function

To prove a function is injective, we must prove this statement is true. In general this involves simply starting with $f(x) = f(y)$, and doing operations on both sides until $x = y$.

Consider the function $f(x) = 3x + 1$

$f(a) = f(b)$

$3a + 1 = 3b + 1$

$3a = 3b$

$a = b$

This function is injective.

Surjective functions are functions whose outputs cover the entire codomain. Mathematically, we write that

$$\forall y \in B, \exists x \in A \text{ s.t. } y = f(x)$$

Note: s.t. is a common mathematical abbreviation for such that

An example of a surjective function

Where $A$ is the domain and $B$ is the codomain. Surjective functions require that the range is equal to the codomain. Typically this is proven by starting with $y = f(x)$ and doing operations until there is a an ending statement of $x = g(y)$ where $g(y)$ is expression in terms of $y$ that would fall inside the domain of the function, no matter what value of $y$ is chosen.

Consider the function $f(x) = 3x + 1$, where the domain and codomain are the real numbers.

$y = 3x + 1$

$y - 1 = 3x$

$\frac{y - 1}{3} = x$

If $y$ is a real number, then $\frac{y - 1}{3}$ is a real number.

This function is surjective.

As a note, the images shown for injective and surjective were carefully drawn so that the injective function was not surjective (it misses the first point), and the surjective function was not injective (it doubles up on a point).

Bijective functions are functions that are both injective and surjective. These functions are very special, as they show a relationship between the domain and the codomain that we will explore in the next section.

Check your understanding: Consider all functions of the form $y = ax + b$, where $a$ and $b$ are integers, and the function's domain and codomain are the real numbers. Show this type of function is always bijective.

Check your answer

We'll use c and d to avoid confusion between variables.

$f(c) = f(d)$

$ac + b = ad + b$

Subtract $b$

$ac = ad$

Divide by $a$

$c = d$

Therefore, this function is injective.

$y = ax + b$

$y - b = ax$

$\frac{y - b}{a} = x$

If $y$ is a real number, then $\frac{y - b}{a} = x$ is also a real number.

Therefore, the function is surjective.

Since it's injective and surjective, it's bijective.

Cardinality and Countability

Chapter 7.2

Remember: Please read the text linked above before reading the material below.

When a function is Bijective, it means that every element of the domain maps to a unique input of the codomain. As these are sets, this implies that the size (cardinality) of these sets is the same.

We can use this to prove a concept called countability. We define an infinite set as countable, or countably infinite, if it there is a bijective function from the natural numbers to the set. It's called countability as the natural numbers are also known as the counting numbers, as they are the numbers we typically use when counting.

Sets which are infinite, but not countably infinite are called uncountable.

In mathematics, we have a concept around different sizes of infinity. One of these sizes is countably infinite. Think about the difference between the infinity of the natural numbers and the infinity of the real numbers. There are infinite real numbers between each set of numbers in the natural numbers, so in some sense, it makes them different sizes of infinity.

The following is a fun TedEd video about Hilbert's Hotel, a thought experiment which highlights how little we understand infinity. Please watch it and bring any questions you have to class!

We can show the positive even numbers (plus zero) are countable using the function $f(x) = 2x$

Showing it's injective:

$f(x) = f(y)$

$2x = 2y$

$x = y$

Showing it's surjective:

$y = 2x$

$x = \frac{y}{2}$

Since $y$ is even, $\frac{y}{2}$ is always a natural number.

So this function is bijective.

The output is all even numbers, and thus the positive even numbers plus zero are countable!

Check your understanding: Can you prove that the positive odd numbers are countable?

Check your answer

The proof here is almost exactly the same as the one above, just with $f(x) = 2x - 1$ or $f(x) = 2x + 1$.

However, we need to be careful. If we consider the natural numbers starting at $0$, as we typically do in this course, we'll use $f(x) = 2x + 1$, and if we consider them to start at $1$, we need to use $f(x) = 2x - 1$. If we swap these, we either include $-1$, or don't include $1$.

We proved in a previous Check your understanding that functions of this form were always bijective, we just need to adjust it to the integers and odd integers (rather than real numbers to real numbers), and it will also be bijective.

The tricky part is that in surjective, if you have $\frac{y - 1}{2}$ this will be an integer if $y$ is an odd integer.

Since it's bijective and outputs the odd integers, the positive odd integers are countable.

Think about it: The rational numbers are countable. Can you figure out how this is true? What sort of function would allow us to prove this?

Composition

Chapter 7.3

Remember: Please read the text linked above before reading the material below.

We can input values into functions, but we can also input functions into functions. This is known as function composition. We denote this as

$g(f(x)) = g \circ f(x)$

This will form a new function, with the domain being the domain of $f$, and the codomain being the codomain of $g$. Note that for this to work, the range of $f$ needs to fall within the domain of $g$.

A diagram of function composition

For example,

$f(x) = x^2$

$g(x) = x + 1$

$f \circ g(x) = f(g(x)) = f(x+1) = (x+1)^2$

Note that this is not necessarily the same as the other way around:

$g(f(x)) = g(x^2) = x^2 + 1$

Think about it: Are there any functions you can think of where $f(g(x)) = g(f(x))?$

Inverse

Chapter 7.3

Remember: Please read the text linked above before reading the material below.

For functions which are injective, we can calculate the function's inverse function. This function, when composed with the original, gives the value $x$, in either order. The inverse function "undoes" a function. We denote this as follows:

$$f^{-1}(x)$$

The inverse function can also be thought of by turning the direction of the arrows in a set diagram.

A diagram of an inverse function

We need the function to be injective, so the inverse function will have unique values for every input. We can calculate the inverse function by swapping the $x$ and $y$ values, then solving for $y$.

For example,

$f(x) = 3x + 1$

$y = 3x + 1$

$x = 3y + 1$

$x - 1 = 3y$

$\frac{x - 1}{3} = y$

$f^{-1}(x) = \frac{x - 1}{3}$

Think about it: What do you think happens when we take the composition of a function with its inverse? That is, what is $f(f^{-1}(x))$? Does this change if the composition is swapped?

This gives us a more mathematical definition of an inverse function, and is typically what you'll see in math texts.

Think about it: The text states only bijective functions can have an inverse. Why do you think this is a requirement?

Permutation

Chapter 7.3

Remember: Please read the text linked above before reading the material below.

A function can map a set to itself. When this function is also bijective, this is called a permutation, as the function "rearranges" the values of the set.

Typically, we think about permutations with finite sets, but we can apply it to infinite sets as well.

This operation is not as important or common as others, but is good to know.

Floors and Ceilings

The floor and ceiling function are special functions that can be performed on numbers. This may be review, but is important to know for this week and moving forward.

Floor

The floor function takes a number ($x$) as input and outputs the greatest integer less than or equal to the input. In math terms,

$$\lfloor x \rfloor = y \text{, } x-1 < y \leq x$$

Check your understanding: What is $\lfloor 5 \rfloor$? What about $\lfloor 5.2 \rfloor$ or $\lfloor 5.7 \rfloor$? How is this different from rounding?

Check your answer

These are all $5$! Flooring always rounds down the number, rather than the typical rounding up for values closer to the next integer.

When values are negative, it can be a little confusing at first to apply the floor function.

$$\lfloor -5.2 \rfloor = -6$$

Remember: the negative integer less than $-5.2$ is $-6$. $-5$ is actually greater than $-5.2$.

Check your understanding: What happens when you floor $\frac{n}{2}$ for $n = 1, 2, 3, ..., 10$? What about $\frac{n}{3}$?

Check your answer

$\lfloor \frac{n}{2} \rfloor = 0, 1, 1, 2, 2, 3, 3, 4, 4, 5$

It seems we get a sequence of values, each appearing twice (except for zero). This may be useful later...

$\lfloor \frac{n}{3} \rfloor = 0, 0, 1, 1, 1, 2, 2, 2, 3, 3$

Now we have triples, and zero only appears twice.

Think about it: Can you describe what happens when we take $\lfloor \frac{n}{k} \rfloor$ over the positive integers, for any integer $k$?

Ceiling

The ceiling function takes a number ($x$) as input and outputs the smallest integer greater than or equal to the input. In math terms,

$$\lceil x \rceil = y \text{, } x \leq y < x+1 $$

Instead of always rounding down, this is always rounding up. The examples used in the Check Your Understanding would now be all $6$s instead of all $5$s.

Likewise, for the negative numbers, the higher number will be the opposite of the positive integers. $\lceil -5.2 \rceil$ will be $-4$.

Check your understanding: What happens to $\frac{n}{2}$ and $\frac{n}{3}$ when we apply ceiling to the first $10$ positive integers?

Check your answer

$\lceil \frac{n}{2} \rceil = 1, 1, 2, 2, 3, 3, 4, 4, 5, 5$

Now the sequence of values has no zero, so all terms are doubled!

$\lceil \frac{n}{3} \rceil = 1, 1, 1, 2, 2, 2, 3, 3, 3, 4$

Now we have triples, and once again, no zero.

Think about it: How is the ceiling of $\frac{n}{k}$ different from the floor for the sequence of positive integers, when $k$ is an integer?

Week 2: Self-Guided Problems

When you come to class, be ready to discuss these questions, and bring any additional questions you still have after this exercise!

Submitting Your Work

Your work must be submitted to Anchor for degree credit and to Gradescope for grading.

For any work completed outside of GitHub or Gradescope:

Typeset your work in LaTeX.

You should use \begin{enumerate} to create a numbered list, and your solutions to each problem should match with the corresponding number on the assignment.
For example, if an assignment has 10 numbered problems, your enumerate should have 10 \item commands, with your solution(s) to problem 1 under the first \item, problem 2 under the second and so on.
If you skip a problem, just leave the \item blank, otherwise the numbers of your solutions will not match the assignment document.

Compile into a PDF. This can be done easily through an Overleaf account, otherwise you will need to install LaTeX.
Submit the pdf to Gradescope via the appropriate submission link for the course.
Upload the pdf to Anchor using the form below.

Note: Anchor submissions can occur at any time during the term, but it is critical that you upload all of your work to Anchor before the last day of the term. Gradescope submissions must be submitted before the deadline (or the late deadline, if applicable).

It is required that all assignments are submitted as a PDF generated from a LaTeX document.

Assignments submitted in any other form will earn zero credit.

Self-Guided Problems cannot be submitted late for any reason

This is due to the fact we discuss them in the class. Be sure to stay on top of these Self-Guided problems, and remember it is better to turn in an incomplete set than an empty one.

Problems

Consider a sequence where the first two terms are 1 and 2.

What would be the next term if it was an arithmetic sequence?
What would be the next term if it was a geometric sequence?

Create your own sequence that starts with 1 and 2. What is the rule for each term in the sequence? Is there a closed form solution for the $n$th term of your sequence? What about the sum up to the $n$th term?
Write code in the language of your choice to calculate the $n$th term of the sequence defined by $$a_n = a_{n-1} + 3, a_0 = 0$$

In two different ways:

Using a for loop to compute from $a_0$ to $a_n$
Using the closed form for the expression.

Try running the code both ways for $n = 1, 100, 10,000,$ and $1,000,000$.

Is there a significant time difference between the two methods? If there is, at what point do you notice a difference?
Does the countability of a set imply anything about the span of the set? That is, the difference between the smallest and the largest values? What about uncountable sets?
Prove f(x) is bijective. $$f(x) = \frac{3}{2}x + 6$$
Show g(x) is not bijective $$g(x) = 7x^4$$
What are some indicators that a function is bijective? Are there any indicators that a function is not bijective?

Homework Set 2

Submitting Your Work

Your work must be submitted to Anchor for degree credit and to Gradescope for grading.

For any work completed outside of GitHub or Gradescope:

Typeset your work in LaTeX.

You should use \begin{enumerate} to create a numbered list, and your solutions to each problem should match with the corresponding number on the assignment.
For example, if an assignment has 10 numbered problems, your enumerate should have 10 \item commands, with your solution(s) to problem 1 under the first \item, problem 2 under the second and so on.
If you skip a problem, just leave the \item blank, otherwise the numbers of your solutions will not match the assignment document. Here is an example Overleaf document showcasing this format.

Compile into a PDF. This can be done easily through an Overleaf account, otherwise you will need to install LaTeX.
Submit the pdf to Gradescope via the appropriate submission link for the course.
Upload the pdf to Anchor using the form below.

Note: Anchor submissions can occur at any time during the term, but it is critical that you upload all of your work to Anchor before the last day of the term. Gradescope submissions must be submitted before the deadline (or the late deadline, if applicable).

It is required that all assignments are submitted as a PDF generated from a LaTeX document.

Assignments submitted in any other form will earn zero credit.

[35 points] Find the closed form for the following series, up to the $n$th term. If the infinite series has a finite solution, write it down.

a. 1 + 4 + 7 + 10 + 13 + ...

b. $a_n = 3 \cdot a_{n-1}$, $a_0 = 2$

c. 5 + 17 + 29 + 41 + 53 + ...

d. $a_n = a_{n-1} + 4$, $a_0 = -1$

e. $\frac{1}{2} + \frac{1}{6} + \frac{1}{18} + \frac{1}{54} + \frac{1}{162} + ... $

f. -15 + -13 + -11 + -9 + -7 + ...

g. $\frac{1}{5} - \frac{1}{35} + \frac{1}{245} - \frac{1}{1715} + \frac{1}{12005} - ...$
[5 points] Is the Fibonacci sequence an arithmetic sequence? Explain your answer.
[5 points] Is the sequence $a_n = 2^n$ a geometric sequence? Explain your answer.
[5 points] Which of the following is true:
- Functions are a subset of sequences.
- Sequences are a subset of functions.
- Functions are a subset of relations.
- Relations are a subset of functions.
- None of these are true.
[10 points] Are all linear functions bijective? Prove or disprove.
[10 points] Are all quadratic functions bijective? Prove or disprove.
[10 points] Are all polynomial functions bijective? Prove or disprove.
[10 points] Prove that the set of all odd integers is countable.

Recurrence Relations

This week, we'll cover recurrence relations. First, we'll discuss logarithms and summation notation to ensure we can compute the solutions to recurrence relations. Then, we'll discuss recurrence relations, and how they relate to sequences and recursive code.

By the end of the week, you should be able to:

Understand and use summation notation/big pi notation.
Evaluate simple logarithms and apply basic logarithmic rules.
Identify recursive problems.
Solve simple recursive problems.
Recall methods of solving harder recursive problems.

Summation Notation

Summation Notation is an important piece of mathematical notation that allows us to express summations quickly.

Summation Notation

Summation Notation is used to describe a sequence of terms which are added together. This is done using at least one variable, where each term is a function of this variable, and the lowest and highest values of the variable are stated. It uses the capital greek letter Sigma, an S for sum.

The following summation denotes the sum of the first $10$ positive integers.

$$\sum_{k=1}^{10} k$$

Here, the variable is $k$, the lowest value it takes is $1$, and the highest value it takes is $10$. When read out loud, we would say "the sum from $k$ equals 1 to $k$ equals 10 of $k$."

You can also do summations over multiple variables, or summations of summations. For example,

$$\sum_{k=1}^{10}\sum_{j=1}^{5}k^j$$

Gives the sum of the first $10$ positive integers, each to the value of the first $5$ numbers. We do the inner sum first, then the outer, just like nested loops.

$$\sum_{k=1}^{10}\sum_{j=1}^{5} k^j = 1^1 + 1^2 + 1^3 + 1^4 + 1^5 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + ... + 10^1 + 10^2 + 10^3 + 10^4 + 10^5$$

Note that in this case, we can swap the summations and still have the same sum, just ordered differently.

$$\sum_{j=1}^{5}\sum_{k=1}^{10} k^j = 1^1 + 2^1 + ... + 10^1 + 1^2 + 2^2 + ... + 1^5 + 2^5 + ... + 10^5$$

If we want to denote an infinite series, we can set the top bound to infinity.

$$\sum_{k=1}^{\infty} k$$

Check your understanding: What does this sum represent? What is its value?

Check your answer

This is simply the sum of the natural numbers, which is infinite.

In LaTeX, we use \sum to use summation notation, and sub/super-scripts for the bounds on the variable.

Think about it: What would $\sum_{k=1}^{10} 1$ be?

Capital Pi Notation

There is a lesser-known notation for multiplying many things in a row. Instead of a big sigma, we use a big pi symbol.

$\prod_{k=1}^{10} k = 1 \cdot 2 \cdot ... \cdot 10$

Check your understanding: What's the value of $\prod_{k=1}^{10} 2k$?

Check your answer

$2^{10} \cdot 10!$

Logarithms

Logarithms are the inverse operation to exponents. They are important to know when instead of multiplying by the same term many times, we are dividing by the same term many times.

Logarithm Definition

We define logarithms as follows:

$\log_b{(x)} = y \Longleftrightarrow b^y = x$

We consider $b$ to be the base of the logarithm.

For example, $\log_2{(8)} = 3$, since $2^3 = 8$

Think first: What is $\log_2{(1)}$?

$\log_2{(1)} = 0$, since $2^0 = 1$

We can also take the logarithm of fractions.

$\log_2{(\frac{1}{8})} = -3$, since $2^{-3} = \frac{1}{8}$

Exponent Rules to Logarithm Rules

Since logarithms are based on exponents, all exponent rules apply. When we multiply numbers, we add the exponents, so

$\log{(m\cdot n)} = \log{(m)} + \log{(n)}$

Likewise, division would be subtraction instead.

Since logarithm is an inverse operation, it can cancel out exponents. When we want to "undo" addition, we subtract. For multiplication, we divide. For exponents, we can use logarithms.

$$16 = 2^x$$

$$\log_2{(16)} = \log_2{(2^x)}$$

$$4 = x$$

Check your understanding: If you had $16 = \log_2{(x)}$, how would you solve for $x$? Be careful that you put things in the right spots. We want $x$ to come out in the end, and we know $y = \log_2{(x)}$.

Check your answer

Make both sides an exponent of $2$

$2^{16} = 2^{\log_2{(x)}}$

The log and the base $2$ will cancel, leaving only $x$ on the right hand side.

$x = 2^{16}$

This should make sense as $\log_2{(2^{16})} = 16$

Think about it: Do you know any other rules with exponents? How would they translate to logarithms?

Recurrence Relations

Recurrence relations are related to the idea of recursive functions. Here, we discuss the mathematical structure of recrrences and how to solve them, as well as some applications of recurrence relations.

Readings

Please read this first before moving on to the documents here on Anchor. As a reminder, and for reference, specific chapters are referenced at the beginning of the section for which they are relevant. Feel free to go back to the text(s), or review it if there's been a break since you last read the material. The readings on Anchor have some information in common with the text(s). This is to ensure you see the information from some different perspectives.

Applied Discrete Structures, Chapter 8.1, 8.3-8.4

Discrete Mathematics: An Open Introduction, Chapter 2.4

Examples of Recurrence Relations

Chapter 8.1

Remember: Please read the text linked above before reading the material below.

In the last module, we discussed some particular sequences. The geometric and airthmetic sequences are technically both recurrence relations, since they are defined by a reference to themselves.

The Fibonacci sequence is perhaps one of the most popular recurrence relations. This relation is special as it references itself twice. Each term in the sequence is the sum of the two previous terms, where the first two terms are $0$ and $1$ (or $1$ and $1$ depending on who you ask).

$$1, 1, 2, 3, 5, 8, 13, 21, ... $$

To write this in the form of a recurrence relation, we say

$$f_0 = 1, f_1 = 1$$

$$f_n = f_{n-1} + f_{n-2}$$

Check your understanding: What does the fibonacci sequence look like if the first two terms were $1$ and $2$ instead of $1$ and $1$? How much of a difference does this make? What about starting with $2$ and $3$? $3$ and $4$?

Check your answer

$1$ and $2$ already exist in the fibonacci, this would just move everything up by one.

Similarly, with $2$ and $3$ everything would get moved up by $2$.

However, $4$ is not in the fibonacci sequence, so this would be different.

$3, 4, 7, 11, 18, 29, 47, 76, ... $

A lesser known variant is the Tribonacci sequence, which takes the sum of the last three terms instead.

$$t_0 = 1, t_1 = 1, t_2 = 2$$

$$t_n = t_{n-1} + t_{n-2} + t_{n-3}$$

Check your understanding: Write out the first $10$ terms of this sequence. How different is it from the Fibonacci sequence?

Check your answer

$1, 1, 2, 4, 7, 13, 24, 44, 81, 149, ... $

It's quite different, from the moment the recurrence starts.

Iteration

Chapter 8.1

Remember: Please read the text linked above before reading the material below.

Just like programming, many recurrsive relations can be evaluated iteratively rather than recursively. However, there is no such thing as "iterative relations." Instead, this can be a method used in solving recurrence relations.

Recurrence Relations

Chapter 8.3

Remember: Please read the text linked above before reading the material below.

Recurrence relations are simply sequences for which almost all terms are defined by previous terms of the sequence. The arithmetic and geometric sequences, the fibonacci sequence, and the tribonacci sequence are all examples of recurrence relations. However, these do not cover all the potential ways a recurrence relation can be created or defined.

A recurrence relation could reference a term farther back than the one before it, and the sequences can include negative values:

$$r_0, r_1, r_2 = 1$$

$$r_n = 3r_{n-3} - r_{n-2}$$

$$1, 1, 1, 2, 2, 1, 4, 5, -1, 7, 16, -10, ...$$

You can also perform different types of operations, like raising to a power, taking a logarithm, a root, or any other mathematical operation.

$$r_0 = 1$$

$$r_n = (r_{n-1} + 1)^2$$

$$1, 4, 25, 676, 458329$$

A relation is not a recurrence relation if it does not reference itself. Not all sequences are recurrence relations. For example, the sequence of square numbers is not a recurrence relation, since it depends on the index of each term, not a function on any prior term.

Check your understanding: Create one recurrence relation, and one sequence that is not a recurrence relation.

Check your answer

Answers will vary, but remember that a recurrence relation must meaningfully reference itself.

Solving Recurrence Relations: Linear Recurrence Relations

Chapter 8.3

Remember: Please read the text linked above before reading the material below.S

The chapter above details exactly how linear recurrences (those which are only made up of ) can be solve. The most important part of this is the idea behind the method. There are many problems in mathematics that can be reduced to solving for the roots of an equation.

The same applies here. When we transform a recurrence into a function, the roots can be converted into a solution using a clever bit of math.

Solving Recurrence Relations: Intuition

One method of solving a recurrence relations involves knowing or guessing the final solution. If you have the closed form, or believe you have the closed form, you can plug this in for the terms in the recurrence for $r_n$. If the final result matches the expected form for $r_n$, then the solution is correct! If not, some information could be gathered.

Suppose I tell you the solution to the below recurrence is $\log_2{(n)}$, for $n = 2^k$.

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

We can plug in $T(\frac{n}{2}) = \log_2{(\frac{n}{2})}$

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

Let's let $n = 2^k$

$$T(2^k) = \log_2{(\frac{2^k}{2})} + 1 = \log_2{(2^{k-1})} = 1 = k - 1 + 1 = k = \log_2{(2^k)}$$

We've now shown that this solution works, since we didn't pick any specific value for $n$.

Check your understanding: What do you think the solution might be for $T(n) = T(\frac{n}{3}) + 1$, where $n = 3^k$? Check your answer using this substitution method.

Check your answer

This is simply $\log_3{(n)}$. The substitution method is very similar to the one above, just replacing mentions of base $2$ with base $3$.

Solving Recursive Problems Iteratively

Discrete Mathematics: An Open Introduction, Chapter 2.4

One way we can guess at a final solution is to iteratively substitute in the value of the right hand side. We can see what pattern forms, and use it to find a solution.

For example, we might have

$$T(1) = 1$$ $$T(n) = 2T(n-1) + 1$$

If we substitute $T(n-1) = 2T(n-2) + 1$, we'll have

$$T(n) = 2(2T(n-2) + 1) + 1$$

Check your understanding: Why is $T(n-1) = 2T(n-2) + 1$?

Check your answer

This is just the definition of the recurence, replacing $n$ with $n-1$

Likewise, $T(n-2) = 2T(n-3) + 1$

$$T(n) = 2(2(2T(n-3) + 1) + 1) + 1$$

Think first: Do you see a pattern here? What would this look like if we kept going until $T(n-k)$ was the term on the right side?

We should note that the number of $2$s is the same as the number being subtracted from $n$. We should also note that there are parentheses every time. Let's look at the form we just created, when the $2$s are distributed.

$$T(n) = 2(2(2T(n-3) + 1) + 1) + 1 = 2^3T(n-3) + 2^2 + 2^1 + 1$$

I kept these $2$s as powers for a reason.

Think first: if you didn't before, do you see the pattern now?

We should get

$$T(n) = 2^kT(n-k) + 2^{k-1} + 2^{k-2} + ... + 2^2 + 2^1 + 1$$

Note that when $k = n-1$, $T(n-k) = T(n-(n-1)) = T(1)$, which is our base case of $1$.

So, when we iterate down to the lowest level, we'll have

$$T(n) = 2^{n-1}\cdot 1 + 2^{n-2} + 2^{n-3} + ... + 2^2 + 2^1 + 1$$

As we know from the series content, the sum of powers of $2$ is $2^n - 1$.

Thus, we get our solution! If we wanted to double check, we could substitute this value in, and see if it holds.

$$T(n) = 2T(n-1) + 1 = 2(2^{n-1} - 1) + 1 = 2^n - 1$$

Think about it: Can you come up with a general solution for $T(n) = bT(n-1) + 1$, where $b$ is some real number?

Solving Recurrence Relations: Other Methods

There are many methods out there for solving recurrence relations. However, they tend to be application-specific, and a little harder, require a background in calculus, or are weirder than the methods above. A good project could discuss the Master Theorem, which is a general set of rules for solving certain recurrence relations.

Recurrence and Recursion

Recursive code can be often described using a recurrence relation.

def fibonacci(n): if n == 0 or n == 1: return 1 else: return fibonacci(n-1) + fibonacci(n-2)

The code above will calculate the $n$th fibonacci number. We should be able to see that the base case translates to the first term(s) of the sequence, and the recurrence is seen in the recursive call.

Simply take the name of the function, and replace it with a capital letter. If you set it equal to the recursive call (with the same changes made), you should get a recurrence relation.

Check your understanding: Find a recursive function you wrote, or one on the internet. Can you write a recurrence relation based on this function? Is there a simple, closed form solution to this recurrence?

Check your answer

Answers will vary, but you can test the time of the function by running multiple times with larger values and timing how long it takes to run, or you can test the values you get by running the function multiple times and comparing to your mathematical answers.

Applications: Analysis of Algorithms

Chapter 8.4

Remember: Please read the text linked above before reading the material below.

Recurrence relations are often used to describe how an algorithm runs, as many algorithm are recursive in nature. From this recurrence relation, we can determine about how long an algorithm will run, given an input of size $n$. The reading above gives an analysis of the Binary Search algorithm using recurrence relations.

Examples of Recurrence Relation Problems

Other than Fibonacci, there are a few more famous recurrence relation problems. It can sometimes be difficult to see how a problem can be solved recursively.

Think about it: Try to think about each problem presented. What are some indications that the problem is recursive?

Number of Ways to Step

Suppose you are climbing a Mayan pyramid. These have many stairs, so you wish to save time. You can take one stair at a time, or you can skip some steps. The height of the stairs and the length of your legs mean you can either skip one or two steps when climbing the pyramid. How many different ways could you climb this structure, starting at the bottom?

First, we notice that once you make your decision on your first step size, you will have a number of stairs left based on the step you took. However, when this is accounted for, the same problem remains: what size will your next step be? This problem is recursive in nature.

Let $M(n)$ be the number of ways to climb $n$ stairs. Then, if you step once, you'll have $n-1$ stairs to climb ($M(n-1)$), if you skip a step, there will be $n-2$ steps ($M(n-2)$), and if you skip $2$ steps, there will be $n-3$ stairs left to climb ($M(n-3)$). Since we're counting the total number of ways to climb these stairs, we can simply add these values together.

The last step is to consider the starting values, which are really considering cases of a small number of stairs. If there are less than $3$ stairs, we can't skip $2$ steps, so let's consider $n = 1, 2, $ and $3$.

If there is $1$ step left, we can only climb the one step in one way. If there are two steps, we can either skip the middle one or climb them both, meaning $2$ ways in total. If there are $3$ steps, we can either skip $2$ and be done, or we can skip $2$, then climb $1$, climb $1$, then skip $2$, or simply climb them one at a time, leaving $4$ ways in total.

Our final recurrence is:

$$M(1) = 1, M(2) = 2, M(3) = 4$$

$$M(n) = M(n-1) + M(n-2) + M(n-3)$$

Which we'll notice is a Tribonacci-like recurrence.

Parenthesizing Multiplications

Suppose you have a list of things to multiply:

$$x_0 \cdot x_1 \cdot x_2 \cdot ... \cdot x_n$$

However, you want to determine how many ways you can parenthesize this multiplication. In how many ways can these be grouped? We consider an expression fully grouped if each set of parentheses have at most two terms in them. A term could be something inside a set of parentheses, or could be an $x_i$. For example:

$$ (x_1 \cdot ( ( x_2 \cdot x_3) \cdot x_4) \cdot x_5) $$

Is fully parenthesized. If any were removed, it wouldn't be.

Taking a look at the simplest examples:

One $x$ value on its own just needs a set of parentheses around it. The same for a set of two.

For a set of three, we can split the first term away, or the last term away to create one set. Then another set of parentheses around the whole thing.

In general, if we have $n$ $x$ values, we can split this into two smaller groups, then parenthesize these groups. We can split anywhere from just after the first value, to just before the last value, so any of the $n-1$ spots in between.

Let $S$ be our set of multiplications, with $S_{i, j}$ representing the subset of $S$ from the $i$th term to the $j$th term. We can show our recurrence is this:

$$ S(n) = 1, \text{ for } n = 1, 2$$ $$ S(n) = (S_{1,1} \cdot S_{2, n}) + (S{1, 2} \cdot S_{3, n}) + ... + (S_{1, n-1} \cdot S_{n, n}) $$

Where $n$ is the number of $x$ values in the multiplication. We multiply in each step since for each combinations of the first term, we can pair this with all combinations of the second. Then we add all of our cases of where we split.

Check your understanding: Try to find the first few values of this recurrence (at least up to 10).

Check your answer

$1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862$

Think about it: Do these numbers make sense? You should notice a rapid growth in the value of $S(n)$. Does that align with the problem?

The Towers of Hanoi

The Towers of Hanoi is a problem based on a number of disks of decreasing size placed on one of three pegs. Watch the video below to learn more about it and understand its recursive nature.

Think about it: From the code given, can you write the recurrence relation for towers of Hanoi? Does this solve to $2^n - 1$, as expected from this video?

The second part of this video talks about a constrained version of this problem. It involves ternary and graphs, which we will visit again in later weeks. For now, focus on the recursive nature of the problem.

Think about it: If this is ternary, instead of binary, what happens to the solution? Can you figure out what the recurrnce looks like in this constrained case?

Week 3: Self-Guided Problems

When you come to class, be ready to discuss these questions, and bring any additional questions you still have after this exercise!

Submitting Your Work

Your work must be submitted to Anchor for degree credit and to Gradescope for grading.

For any work completed outside of GitHub or Gradescope:

Typeset your work in LaTeX.

You should use \begin{enumerate} to create a numbered list, and your solutions to each problem should match with the corresponding number on the assignment.
For example, if an assignment has 10 numbered problems, your enumerate should have 10 \item commands, with your solution(s) to problem 1 under the first \item, problem 2 under the second and so on.
If you skip a problem, just leave the \item blank, otherwise the numbers of your solutions will not match the assignment document.

Compile into a PDF. This can be done easily through an Overleaf account, otherwise you will need to install LaTeX.
Submit the pdf to Gradescope via the appropriate submission link for the course.
Upload the pdf to Anchor using the form below.

Note: Anchor submissions can occur at any time during the term, but it is critical that you upload all of your work to Anchor before the last day of the term. Gradescope submissions must be submitted before the deadline (or the late deadline, if applicable).

It is required that all assignments are submitted as a PDF generated from a LaTeX document.

Assignments submitted in any other form will earn zero credit.

Self-Guided Problems cannot be submitted late for any reason

This is due to the fact we discuss them in the class. Be sure to stay on top of these Self-Guided problems, and remember it is better to turn in an incomplete set than an empty one.

Problems

Identify whether each of the following is recurrence or just a sequence.

$a_n = 2a_{n-1} + 2$
$a_n = 2a_{\frac{n}{2}}$
$a_n = a_{n-2} + a_{0}$
$a_n = a_0 + a_1 + a_2$

Solve the following recurrence relations. For the first three, assume $R(0) = 1$, for the last, assume $R(0) = k$:

$R(n) = 5R(n-1)$
$R(n) = bR(n-1)$, where $b$ is an integer.
$R(n) = 5R(n-1) + 1$
$R(n) = bR(n-1) + k$, where $b$ is an integer, and $k$ is an integer.

For one of these, show your solution is true by plugging in the closed form value of $R(n-1)$ on the right-hand side, and using algebraic steps that end in the closed form for $R(n)$.
Write a recursive function for 1 example from problem 1, and 2 examples from problem 2. Take a screenshot of the code, and include it in your submission.
Try solving the problem 1 relation by inputting different values of n into your code. Do you believe there's a closed form solution? If so, what is it?
Compare your solution to the problem 2 relations by testing multiple n values with your code. Does your closed form line up with your code?

Homework Set 3

Submitting Your Work

Your work must be submitted to Anchor for degree credit and to Gradescope for grading.

For any work completed outside of GitHub or Gradescope:

Typeset your work in LaTeX.

You should use \begin{enumerate} to create a numbered list, and your solutions to each problem should match with the corresponding number on the assignment.
For example, if an assignment has 10 numbered problems, your enumerate should have 10 \item commands, with your solution(s) to problem 1 under the first \item, problem 2 under the second and so on.
If you skip a problem, just leave the \item blank, otherwise the numbers of your solutions will not match the assignment document. Here is an example Overleaf document showcasing this format.

Compile into a PDF. This can be done easily through an Overleaf account, otherwise you will need to install LaTeX.
Submit the pdf to Gradescope via the appropriate submission link for the course.
Upload the pdf to Anchor using the form below.

Note: Anchor submissions can occur at any time during the term, but it is critical that you upload all of your work to Anchor before the last day of the term. Gradescope submissions must be submitted before the deadline (or the late deadline, if applicable).

It is required that all assignments are submitted as a PDF generated from a LaTeX document.

Assignments submitted in any other form will earn zero credit.

[15 points] Determine whether the following problems are recursive problems.

a. $R(0) = 1$, $R(1) = 1$, $R(n) = 2R(n-1) + R(n-2)$

b. $R(1) = 0$, $R(n) = 5R(n-1)$

c. $R(0) = 0$, $R(n) = n$

d. $R(1) = 1$, $R(n) = 2R(\frac{n}{2}) + 5$

e. $R(1) = 1$, $R(n) = R(1)$
Solve the following recurrence relations:

a. [5 points] $R(0) = 3$, $R(n) = 3R(n-1)$

b. [10 points] $R(0) = k$, $R(n) = bR(n-1)$, where $b$ and $k$ are integers.

c. [5 points] $R(1) = 0$, $R(n) = R(\frac{n}{5}) + 1$, where $n$ is always of the form $n = 5^k$

d. [10 points] $R(1) = 0$, $R(n) = R(\frac{n}{b}) + c$, where $n$ is always of the form $n = b^k$, and $b, c$ are integers.
[35 points] Show that the following recursive relations have the closed forms given.

a. $R(1) = 1$, $R(n) = R(n-1) + 2n-1$. Closed form: $n^2$

b. $R(1) = 1$, $R(n) = \frac{n}{n-1}R(n-1)$. Closed form: $n$

c. $R(1) = 1$, $R(n) = R(n-1) + n$. Closed form: $\frac{n(n+1)}{2}$

d. $R(0) = 1$, $R(1) = 1$, $R(n) = 2R(n-1) - R(n-2)$. Closed form: $1$

e. $R(1) = 5$, $R(n) = 5R(\frac{n}{2})$, where $n = 2^k$. Closed form: $5^{k+1}$

f. $R(1) = 1$, $R(n) = R(\frac{n}{2}) + n$, where $n = 2^k$. Closed form: $2n-1$

g. $R(1) = 0$, $R(n) = R(\frac{n}{2}) + \log_2{(n)}$, where $n = 2^k$. Closed form: $\frac{k(k+1)}{2}$
[10 points] Write a recursive function for one of the problems in problem 2. Capture your code here, either by copying it to the LaTeX document, or inserting it as an image.

Proofs

This week, we'll cover the four main proof types: inductive, direct, contrapositive, and contradiction. We'll also discuss how to get started proving a statement, and common pitfalls in proofs.

By the end of the week, you should be able to:

Write inductive, direct, contradiction, and contrapositive proofs.
Analyze a problem and decide which proof technique is the best fit.
Evaluate simple faulty proofs and identify the mistakes.
Combine proof techniques with casework when necessary.

Proof Methods and Techniques

In mathematics, it is important to prove that something is true, rather than assume. Proofs require a deep understanding of logical thinking and intuition, one that helps with systematically solving problems.

Readings

Please read this first before moving on to the documents here on Anchor. As a reminder, and for reference, specific chapters are referenced at the beginning of the section for which they are relevant. Feel free to go back to the text(s), or review it if there's been a break since you last read the material. The readings on Anchor have some information in common with the text(s). This is to ensure you see the information from some different perspectives.

Discrete Mathematics: An Open Introduction, Chapter 3.2

Applied Discrete Structures Chapter 3.7

General Proof Basics

All proofs start with the word proof. It indicates to the reader that the official proof is begining.

The contents of a proof will be different, depending on the claim being proven and the style of proof. Each step should logically follow from the line before it, though exactly what this means can vary. Some textbooks contain proofs which have large leaps in logic between steps, sometimes even large enough that homework may involve proving that the logical leap is valid.

In general, this is not good practice. A proof should be readable by a colleague, with no missing gaps or steps left to be proven. Each line should directly follow or reference a previous line, and some reason should be given that each line is true. Usually, a definition, theorem, or property will suffice.

Once the proof is complete, there are a few ways to denote the end. QED is a common ending, standing for "quod erat demonstrandum," a latin phrase that means "which was to be demonstrated. Sometimes people will write the English translation, or a similar sentiment such as "As desired." If you want to be sure people know where a proof ends, you can use a box, either a filled in or empty box. This is another common proof ending, and one that is not ambiguous.

In LaTeX, you can use the \begin{proof} and \end{proof} commands, and this box, along with the starting Proof will be created for you.

Induction

Chapter 3.7

Remember: Please read the text linked above before reading the material below.

Induction proofs tend to be a starting point for most stdents discovering proofs for the first time. They have a set structure that is easy to replicate. The idea behind inductive proofs also follows a recursive or iterative structure, which can be less difficult for students to follow.

An induction proof always starts with a base case. This should be the first instance of the thing that you're proving.

Next is the inductive case, and this is where the main part of the proof lies. We've shown the statement holds for one instance. We can now show if the previous instance holds, then this one does. This iteratively applies to all future instances, since we start at the first instance, so the second is true. If the second is true, then the third is true, and so on.

Typically in the inductive case, we assume the statement is true for $k$ and show it holds for $k+1$. Occasionally, we can take more than one step back, such as assuming it holds for $k$ and $k-1$ and then showing it holds for $k+1$, or even assuming it holds for all previous values, and showing it holds true for $k+1$.

The important part is that the base case should cover as many cases as the inductive case steps backwards. If the inductive case requires $k-1$ and $k$, the base case should prove the first two instances hold.

It's also important to realize what variable is the piece you're performing induction on. Some expressions have multiple, but look for the part that can change by $1$ and we still want the expression to hold true.

$n < 2^n$, for $n \geq 1$

Proof.

Base case: When $n = 1$, $2^n = 2$, and $1 < 2$. Thus the base case holds.

Inductive case: Assume $k < 2^k$ for $k > 1$

$k + 1 < k + k$ For $k > 1$

Since $k < 2^k$, by the addititive property of inequality, we also know $k + k < 2^k + 2^k$

$k+1 < k + k < 2^k + 2^k$ by the previous statement and $k + 1 < k + k$ For $k > 1$.

$k + 1 < 2^k + 2^k$ by the transitive property of inequality.

$2^k + 2^k = 2^k (1 + 1) = 2^k \cdot 2 = 2^{k+1}$ By the distributive property.

$k + 1 < 2^{k+1}$ by our previous statements.

Since the property holds for $k+1$, by induction this is true.

Q.E.D.

Think about it: Why does this proof start at $n=1$? This inequality holds for $n=0$ as well.

Show that the $n$th term of the Fibonacci sequence, $F_n$, is always less than or equal to $2^n$.

Proof.

Base cases:

$F_0 = 1 \leq 2^0$

$F_1 = 1 \leq 2^1$

Inductive case: Assume $F_n \leq 2^n$ for $n \leq k$.

$F_{k+1} = F_k + F_{k-1}$

$F_k \leq 2^k$

$F_{k-1} \leq 2^{k-1}$

$F_{k+1} = F_k + F_{k-1} \leq 2^k + 2^{k-1}$ By the additive property of inequalities.

$F_{k+1} \leq 2^{k-1}(2 + 1)$ By the distributive property.

Clearly, $2^{k-1}(2 + 1) < 2^{k-1}(2 + 2)$

$F_{k+1} \leq 2^{k-1}(2 + 1) < 2^{k-1}(2 + 2) = 2^{k-1}\cdot 2^2 = 2^{k+1}$

$F_{k+1} \leq 2^{k+1}$ by the transitivity property of inequalities.

Since the property holds for $k+1$, by induction this is true.

Q.E.D.

Think about it: Why did I type the line "for $n \leq k$" in the inductive case?

Check your understanding: Prove one of the recurrences we solved in the previous week through induction. Is this similar to something we covered that week?

Check your answer

Answers vary, but all should be similar to the iteration method.

Direct

Remember: Please read the text linked above before reading the material below.

Direct proofs simply involve proving something as stated. If the statement is of the form $p \rightarrow q$, start at $p$ and end at $q$ through a series of definitions, theorems, and properties.

If the statement is not in the form of an implication, start with something that is known to be true, or a definition of some part of the statement and end with the statement being proven. Usually the starting place in these situations is some qualification that must be met for the statement to be true, such as a number being positive, or of a certain form.

If $n$ is an even number greater than 2, it is not prime.

Proof.

Suppose $n$ is an even number.

By definition of even, $n$ is divisible by $2$.

Since $n < 2$, this means $n$ is divisible by a positive number less than itself that is not equal to $1$.

By definition, $n$ is composite.

Q.E.D.

The square of an even number is divisible by $4$.

Proof.

Let $n$ be an even number.

By definition of even, we can write $n = 2k$ where $k$ is some integer.

$n^2 = (2k)^2 = 4k^2$

Since an integer times an integer is an integer, $k^2 = m$, where $m$ is an integer.

$n^2 = 4m$, where $m$ is an integer. By definition of divisibility, that means $n^2$ is divisible by $4$.

Q.E.D.

Think about it: Why did this proof start with $n$ being an even number?

Contrapositive

Remember: Please read the text linked above before reading the material below.

Instead of starting with $p$ and ending with $q$, we convert the statement to $\neg q \rightarrow \neg p$, and start at $\neg q$.

Once converted, the proof is exactly the same as a direct proof.

If $n$ is a prime number greater than $2$, then it is odd.

We can convert this statement into "If $n$ is an even number greater than 2, it is not prime," which we proved above.

Think about it: If contrapositive uses a direct proof after converting the statement, what does this mean for every statement we prove via a direct proof? What about each statement we prove through the contrapositive?

Contradiction

Remember: Please read the text linked above before reading the material below.

A proof by contradiction starts by assuming the statement is false. Then we show some contradiction occurs. In logical terms, if $p \rightarrow q$ is our implication. We state $p \wedge \neg q$. Then we show this statement is always false by finding some contradiction, meaning the negation of this negation (our original statement) is always true.

The contradiction must occur throughout all cases, all situations for this method to work. It is not enough to negate a statement and show one counterexample, as this only shows the original statement is true in one circumstance.

If $n$ is a prime number greater than $2$, then it is odd.

Proof.

Assume this is false, that is, assume there is some $n > 2$ such that $n$ is a prime number and it is even.

By definition of even, $n$ is divisible by $2$.

Since $n > 2$, $n \neq 2$.

This means $n$ is composite.

This is a contradiction.

Therefore, if $n$ is a prime number greater than $2$, then it is odd.

Q.E.D.

Think about it: We proved this problem for both contradiction and contrapositive. What are the differences? Do you think all statements that can be proven through contradiction can also be proven through contrapostive? Do you think all statements that can be proven through the contrapositive can be proven via contradiction? If the answer is no to either of these, try to think of an example which could not easily be proven by the other.

Cases

Remember: Please read the text linked above before reading the material below.

Sometimes, we need to split a condition up into cases in order to prove a statement. These cases should cover all the possibilities that could happen, but we can split them up any way we'd like. Cases can be used in proofs of any type.

However, we do not want a large number of cases. If you find yourself splitting up into many cases, there may be a better proof style to use.

$m + n$ is only odd if $m$ is odd and $n$ is even, or if $m$ is even and $n$ is odd.

Proof.

$m$ and $n$ can each either be even or odd.

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

$m = 2k$, $n = 2j + 1$ by definition of even and odd.

$m + n = 2k + 2j + 1 = 2(k+j) + 1$ Since $k$ and $j$ are integers, $k + j$ is an integer, and $2(k+j) + 1$ is odd by definition of odd.

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

This case is the same as case 1.

Think about it: Why can I skip this case?

Case 3: $m$ and $n$ are odd.

$m = 2k + 1$, $n = 2j + 1$ by definition of odd.

$m + n = 2k + 1 + 2j + 1 = 2k + 2j + 2 = 2(k + j + 1)$ Since $k$, $j$, and $1$ are integers, $k + j + 1$ is an integer, and $2(k + j + 1)$ is even.

Case 4: $m$ and $n$ are even.

$m = 2k$, $n = 2j$ by definition of even.

$m + n = 2k + 2j = 2k + 2j= 2(k + j)$ Since $k$ and $j$ are integers, $k + j$ is an integer, and $2(k + j)$ is even.

Therefore, the only cases where $m + n$ is odd is when only one of $m$ and $n$ is odd (and the other is even).

Q.E.D.

Think about it: What might be some good ways we can split numbers into cases? Even/odd is given above, are there any other categories that split nicely like this?

Think about it: What do you think a good number of cases would be? What would a bad number be? Is there a clear line where you should stop thinking in cases, because there are too many?

Proof of Existential Statements or Disproof of Universal Statements

Applied Discrete Structures Chapter 3.9

Remember: Please read the text linked above before reading the material below.

There are only two cases where a proof is as simple as showing an example. Proving an existential statement, or disproving a universal statement.

For the first you simply need to show it exists, so find one!

When disproving a universal statement, even one counterexample will make it false. If you find a counter example, you are done.

All Prime numbers are odd.

This is not true. $2$ is a prime number, and is even.

There exists an even prime number.

$2$ is an even prime number, therefore this statement is true.

There are very few cases where you will prove a statement true with an example. It is far more common to disprove statements in this manner.

Think about it: Why do you think there are very few proofs of these types?

Proof Intuition and Faulty Proofs

Understanding proofs can become easy with enough practice. Creating proofs, and in particular, picking a proof style that will work well, can prove to be difficult.

Readings

Please read this first before moving on to the documents here on Anchor. As a reminder, and for reference, specific chapters are referenced at the beginning of the section for which they are relevant. Feel free to go back to the text(s), or review it if there's been a break since you last read the material. The readings on Anchor have some information in common with the text(s). This is to ensure you see the information from some different perspectives.

Important Tools

Applied Discrete Structures Chapter 3.9

Remember: Please read the text linked above before reading the material below.

When starting on a proof there are important tools you will need to actually complete the proof.

Relevant definitions, theorems, and properties need to be found. Though first, you need to decide what may be relevant. This can be tricky for new students. How do you decide what tools you might need?

This requires some insight into the statement you wish to prove. In other words, you can't prove something without a decent knowledge of the related topics. At least, doing so would be difficult.

When looking at a statement you need to prove, consider what topics are involved. What words in the statement have mathematical definitions? Are there other ways to express some of these terms? Are there other statements you have seen or proved before that are related?

Once you have the tools, you can decide on the method.

Intuition

Developing an intuition for proofs is difficult and takes time. Here are some pointers for using a certain proof type, but you should work on developing your own.

Induction

As induction is recursive/iterative in nature, it works very well for sequences, including recurrence relations. This isn't to say induction only works for these topics, it can certainly work for others, but when proving a sequence's closed form, an inductive proof can be efficient.

Direct, Contrapositive, Contradiction

These three proofs consider different versions of $p \rightarrow q$. When deciding between these three, try writing the statement all three ways: $p \rightarrow q$, $\neg q \rightarrow \neg p$ and $\neg q \wedge p$. Once these are all written, sometimes it becomes obvious what version will work well for the problem.

If not, try starting each version. Can you think of the next step in any of these cases? Don't be afraid to switch methods if you find that the one you chose seems to be the wrong path, though you also shouldn't give up immediately if you cannot think of the next step.

Stepping away to take a break, then coming back to a proof problem can help give clarity. Reading out loud, or attempting to explain your thought process out loud can also help.

After enough practice, the choice of proof becomes intuitive, but it will take time and patience to get there.

Think about it: Start creating a list of indicators for each type of proof. You can start the list with the ideas above. Looking at the proofs done in this week's readings (both the textbook and the text on Anchor), are there other indicators? What are they? Continue to update this list as you write more proofs with your findings.

Faulty Proofs

How to lie using visual proofs

Faulty proofs can come from oversights, logical errors, or missing pieces. There are a few common mistakes, which I'll mention here, but this is not a complete list of every mistake one can make in writing a proof.

Missing Pieces

In order for a proof to work, every statement must have some proof that it holds true. This could be one of many things, but in particular, be careful when using previous lines of a proof to prove later statements.

In induction proofs, a common mistake may be to not create enough base cases. Too many creates a sloppy proof, but too few makes a proof incomplete.

The "horse of a different color" proof is a good example of how this mistake can prove something that is definitely false. We'll discuss this proof in class.

Incomplete Definition/Theorem/Property Considerations

Now, we'll discuss using outside theorems, definitions, and properties. Be sure that the mathematical statement you're using can be applied. The mathematical statement you're using might have some requirement, like the number being positive, or the value being an integer. If the part of your proof does not have this required property, you cannot use the proven property, unless you do something like splitting into cases.

It is unlikely that splitting into cases will help a definition apply. Splitting into too many cases can also make a proof become long and sloppy. Instead, try finding some other definition to use, or use a different proof technique.

Logical Fallacies / Mistakes

Inverse error and converse error were two logical errors we discussed. These errors can occur in proof logic as well.

As a whole, other logical fallacies can make a proof incorrect, but these are less common than inverse and converse errors, since they require some psychological manipulation. However, they can still appear. Be sure that you are sticking to a known proof style, and using mathematically proven techniques and ideas.

There are too many logical fallacies to simply list here, so heed this as a general warning. Don't make assumptions that are not mathematically proven or stated directly in the problem!

Check your Understanding: View the flawed proofs here and try to spot the mistakes before looking at the answers. Were you right?

Check your answer

The answers are in the link!

Visual Proofs

The following video shows that even visual examples are not safe. Watch the video below, and see if you can find the problems with the proofs before the video explains them. This is tough, so don't be upset if you can't find the mistakes!

If you don't have a good knowledge of geometry, this video may be a bit hard to understand. I promise the ideas behind these false proofs translate, so feel free to replay the video after looking up some terms (circumference, isosceles, congruent) if you don't understand the main message. You will likely be completely unable to find the mistake in the last false proof without a good background in the geometry of triangles.

It is okay if you don't fully understand exactly the mistakes that happen in this video. Having a general idea of what went wrong should be enough to warn you that pictures are not proofs.

Week 4: Self-Guided Problems

When you come to class, be ready to discuss these questions, and bring any additional questions you still have after this exercise!

Submitting Your Work

Your work must be submitted to Anchor for degree credit and to Gradescope for grading.

For any work completed outside of GitHub or Gradescope:

Typeset your work in LaTeX.

You should use \begin{enumerate} to create a numbered list, and your solutions to each problem should match with the corresponding number on the assignment.
For example, if an assignment has 10 numbered problems, your enumerate should have 10 \item commands, with your solution(s) to problem 1 under the first \item, problem 2 under the second and so on.
If you skip a problem, just leave the \item blank, otherwise the numbers of your solutions will not match the assignment document.

Compile into a PDF. This can be done easily through an Overleaf account, otherwise you will need to install LaTeX.
Submit the pdf to Gradescope via the appropriate submission link for the course.
Upload the pdf to Anchor using the form below.

Note: Anchor submissions can occur at any time during the term, but it is critical that you upload all of your work to Anchor before the last day of the term. Gradescope submissions must be submitted before the deadline (or the late deadline, if applicable).

It is required that all assignments are submitted as a PDF generated from a LaTeX document.

Assignments submitted in any other form will earn zero credit.

Self-Guided Problems cannot be submitted late for any reason

This is due to the fact we discuss them in the class. Be sure to stay on top of these Self-Guided problems, and remember it is better to turn in an incomplete set than an empty one.

Problems

Find the mistake in the following proofs:

All odd numbers are prime.

Proof.

Every prime number, except for $2$, are odd.

Therefore, all odd numbers are prime.

QED

All odd numbers $> 2$ are prime.

Proof.

Every even number greater than $2$ is composite (not prime).

Therefore, all odd numbers greater than $2$ are prime.

QED

Every number is not prime.

Proof.

Base case: $1$ is not prime.

For every other number, we can determine that $n = 1 \cdot n$. So all other numbers are composite, since they can be written as a multiplication of two numbers

QED

Prove the following in at least 2 different ways:

If $n^2$ is even, $n$ is even.
The sum of the numbers from $1$ to $n$ is $\frac{n(n+1)}{2}$.
The sum of any two odd numbers is even.

We can prove that $\sqrt{2}$ is irrational via this proof:

Proof.

Assume $\sqrt{2}$ is rational.

By definition of rational, $\sqrt{2} = \frac{p}{q}$ where $p$ and $q$ are integers, and $p$ and $q$ share no divisors. (Note: this is so the fraction is in simplest form).

Squaring both sides, we get $2 = \frac{p^2}{q^2}$

Multiplying both sides by $q^2$: $2q^2 = p^2$.

Since $q$ is an integer, $q^2$ is an integer, and by definition of even, $p^2$ is even. Below, you'll prove that if $n^2$ is even, $n$ is even, so we know $p$ is even.

Let $p = 2k$, where $k$ is an integer

$2q^2 = (2k)^2 = 4k^2$

Dividing by $2$: $q^2 = 2k^2$. Since $k$ is an integer, $k^2$ is an integer, and by definition of even, $q$ is even.

This is a contradiction: If $p$ and $q$ are both even, then the fraction is not in lowest terms, as we required.

Therefore, $\sqrt{2}$ is irrational.

QED

What other numbers can you prove are irrational using a similar proof? Complete the proof for one of these numbers.

Ask ChatGPT to prove a mathematical statement or theorem. How did it do? We will discuss where ChatGPT succeeds and fails in class, so try to come up with a unique claim for ChatGPT to prove.
Are there other indicators that were not discussed that could help decide what proof type should be used? What are they?
Of the 4 main proof types discussed this week, which do you find most challenging?

Midterm Exam

We will be conducting the exam using onlineexammaker.

A link to the exam will appear below on 1/30/2024. You must complete the exam by 2/3/2024 11:59PM GMT. No late submissions will be allowed.

You have 45 minutes to take this exam, and it has 21 questions, some being True/False, some multiple choice, some multi-select, and some short answer.

In the exam, you may see the following notation. This is what it means:

R -> R -- $\mathbb{R} \rightarrow \mathbb{R}$.

1/2 -- The fraction one half.

x^2 -- x raised to the second power.

a_n -- a subscript n.

You may use any of this shorthand in your own answers.

Feel free to do questions in any order.

You are allowed to re-take this exam before 2/24/2024. There will only be one retake, and the highest grade will be kept. I highly recommend you complete HW 1-3, review the 4th lecture for common mistakes, and do some practice problems before re-taking the exam.

Do not take this exam multiple times without permission.

Here is the link

Resources

This is an open note, open book exam, but it is not open internet.

The following resources are allowed:

Readings on Anchor.
Textbooks linked on Anchor.
Your own notes on material.
Class recordings (though these will be too time consuming for an exam).

The following resources are not allowed:

MathStackExchange, Khan Academy, or any other online math resource not listed above.
ChatGPT, Bard, or any other AI service.
Any other person than yourself (no peers, family members, or otherwise can help you on your exam).
Any other resources not explicitly listed in the "allowed" list.

Using any unapproved resources during an exam counts as academic dishonesty, and may result in a zero on the exam.

Combinatorics

This week, we'll cover the basic topics of combinatorics. This includes permutations and combinations, Pascal's Triangle, solving counting problems, and combinatorial proofs. The reasoning found in combinatorics is unique, but useful.

By the end of the week, you should be able to:

Identify counting problems from real-life examples.
Solve intermediate combinatorial problems using a variety of methods such as casework, complementary counting, overcounting, using identities, and pigeonhole principle.
Analyze a counting problem to decide which method would be most efficient in solving the problem.
Identify generating function problems, and recall the basics of generating functions.

Counting Principles

There are two basic counting principles that are the basis of combinatorics. This information should largely be review from Mathematical Thinking, but perhaps a different way of thinking about the basics of combinatorics.

Readings

Discrete Mathematics: An Open Introduction, Chapter 1.1 and Chapter 1.3

Counting as Sets

Research (Lockwood, 2014: A set-oriented perspective on solving counting problems) shows that thinking of problems as sets of outcomes can help develop the skills necessary to correctly apply combinatorial strategies. While the strategies themselves won't be discussed for a few sections, try to make sure as you're thinking through problems that you form a set of the desired outcomes (things you want to count), and consider how you might find the cardinality of this set.

Addition Principle

Remember: Please read the text linked above before reading the material below.

When events are disjoint, meaning they do not overlap, we can add the number of possibilities for each event together to find the total number of ways any of these events occur. This is the mathematical definition, the meaning is quite simple, just hard to apply.

As a reminder: "event" is just a mathematical term that refers to something happening. It could be drawing a card, drawing multiple cards, rolling a die, catching a fish, or lightening striking.

Therefore, this definition translates as "if there are multiple things that could happen, but they will not occur at the same time, we can use the addition principle. We can count the number of ways each thing could happen and add each of these values to find the total number of ways any of these things could happen."

For example, imagine we have a deck of cards where there are 5 cards labeled 1 to 5 for each of these colors: red, orange, yellow, green, blue, and purple. We'll use this deck instead of a "standard card deck" to avoid confusion.

How many ways could a person pick a red or an orange card?

Think first: What do you think the answer is? What are our sets of outcomes?

There are 5 red cards and 5 orange cards, these each being our desired sets with their cardinalities. In this deck, no card is red and orange (there is no element in the intersection), so we can just add these numbers. There are 10 ways to pick a red or an orange card.

Check your understanding: Can we used this method for the question "how many ways could a person pick a red card or a card labeled 5"? Why or why not?

Check your answer

This cannot be done exactly the same way, since there is a red card labeled 5! We'll find ways to handle these issues soon.

Multiplication Principle

Discrete Mathematics: An Open Introduction, Chapter 1.2, 1.4-1.7, Chapter 5.1

Remember: Please read the text linked above before reading the material below.

When events are independent, meaning each event does not effect any other events, and for each event, there are a certain number of outcomes for every other event, we can multiply the number of ways each event can happen.

This principle is a little more complicated, so let's break it down.

We have multiple events occuring, they might happen at about the same time, but for the multiplication principle, it's best to think of them sequentially, or one right after the other.

For example, if you can order 3 different kinds of meat, 4 different kinds of cheese, and 7 different kinds of vegetables on a sandwich, choosing each ingredient to be added is an event, and while they can be done in any order, or can even be added to a sandwich all at once, it's easiest to pick an order and stick to it.

First, we choose the meat. There's 3 ways to do this. For each meat, we could choose any of the 4 kinds of cheese, so we multiply these events. Likewise for the 12 sandwich types we have, we can add one of 7 different types of vegetables to each. Therefore, there are $12 \cdot 7 = 84$ different ways to make a sandwich if we can only pick one of each ingredient.

Check your understanding: If you were allowed to pick two vegetables, but they had to be different, could you still use the multiplication principle? What if you could pick any two vegetables, including the same one twice?

Check your answer

If the vegetables have to be different, that effects our choice. If we pick one vegetable, now only 6 others remain. Don't worry, we'll fix this issue as well, though this is considered a part of the multiplication principle.

However, if we can just pick the same vegetable twice, there are always just $7$ choices. Therefore, we'd multiply by another $7$ to get $588$ different types of sandwiches.

Think about it: What are some clues a problem should be solved using addition principle? What about multiplication principle? Can you form some general rules that determine which method should be used?

Fixing the principles

Inclusion-Exclusion

Chapter 1.6 Chapter 2.3

Remember: Please read the texts linked above before reading the material below.

The addition principle can be fixed for the red/5 card example by using a method called Inclusion-Exclusion. This is sometimes called the Principle of Inclusion-Exclusion and abbreviated as PIE.

This problem only had two sets, and the overlap is just the one card: the red 5.

So, we count normally at first, 5 red + 6 fives = 11 options. However, the red 5 card is counted twice, once in the reds, and once in the fives. Therefore, we simply subtract 1, as this is the overlap between the sets. 11 - 1 = 10. When we subtract one copy of the red 5, the other remains, and now we have a perfect set of cards which could be drawn to satisfy red or five.

a venn diagram of union

In a Venn diagram, we can see that if we color both sets, the intersection is colored twice over.

If there are three sets, we can do something similar. Suppose we now have a copy of each card for each one of 4 letters: k, i, b, and o. So there will be a red card with a 1 and a k, a red card with a 1 and an i, a red card with a 2 and a k, and so on, meaning our deck now has 120 cards.

Now we change our question: In how many ways could a person draw a red card, a 5 card, or a card with a k.

The red 5 is still an issue (and now there are 4 copies: one for each letter), but so is the red-5-k card, all the red cards with a k, and any card that has a 5 and a k.

Note that when we start our simple approach: 20 red + 24 fives + 30 k-cards, that the red-5-k card is counted 3 times! All other categories mentioned are counted twice, so we can start with those.

There are now 4 red-5 cards, then we must count the red cards with a k (5: one for each number), and the number of cards with a 5 and a k (6: one for each color).

Now we can subtract one copy of each of these, and be left with a better answer.

$$20 + 24 + 30 - 4 - 5 - 6 = 59$$

However, there is one thing we're missing.

Think first: Can you figure out the last step? What happened when we subtracted each of these overlaps between two groups?

The red-5-k card is in all of these groups, so we've subtracted it 3 times. But it was only in there 3 times to begin with, so we need to add it back in.

$$59 + 1 = 60$$

This pattern of subtracting overlaps, then adding overlaps continues for any set of groups, though it's hard to picture for larger numbers of sets.

Think about it: Draw a Venn Diagram with three circles. Color in areas for each step, keeping track of how many times you color over a specific region. Does this align with Inclusion-Exclusion?

In general, you add the amount from each set, then subtract from all the intersections of two sets, then add all the intersections of 3 sets, then subtract all the intersections of 4 sets and so on until your last intersection includes all the sets.

This is the Inclusion-Exclusion method.

Multiplication Principle: Permutation and Combination

Chapter 1.3

Remember: Please read the text linked above before reading the material below.

From our sandwich example, we discussed picking vegetables twice, but getting two different kinds. You'll notice that no matter what vegetable is chosen, there are always 6 remaining. Therefore, if we want different vegetables, instead of multiplying by 7, we can multiply by 6.

Check your understanding: What if I wanted 3 different vegetables? 4? What if I wanted them all? Does the number of ways to pick all vegetables make sense?

Check your answer

For 3 vegetables, we can do $7 \cdot 6 \cdot 5$, for 4, we multiply by the next number down (4). For all vegetables, we would do $7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$.

This number is huge, and logically we can think about the problem a different way. If I select all the vegetables, there's really only one way to do this, unless we're worried about the order the vegetables get added to the sandwich.

From this idea, we have two different operations.

A permutation involves a situation where we're putting a group of things in order, or putting part of a group in order. This is the math we were doing with the vegetables.

Of course, when there are large numbers, and a large number of options being ordered, we want a faster way to write our answer. Mathematicians use factorials to express a number multiplied by all the positive integers below it. To denote this, we use an exclaimation point (!).

$$n! = n \cdot (n-1) \cdot (n-2) \cdot ... \cdot 3 \cdot 2 \cdot 1$$

Note though that our permutations for 2, 3, and 4 did not include all of these numbers. However, we can use another factorial to cancel out the remaining values.

For example, when we wanted 2 vegetables, we could say $\frac{7!}{5!}$ since the 5, 4, 3, 2, and 1 will cancel. Likewise, for 3 we could say $\frac{7!}{4!}$.

For general $n$ options, where we want to pick $k$ to be ordered, what would the form be?

Think first: Try to come up with the form! Hint: in the first example, $n=7$ and $k=2$, and for the second, $n=7$, and $k=3$.

A permutation is often expressed P(n, k), and can be evaluated mathematically as

$$\frac{n!}{(n-k)!}$$

Think first: if you have $n$ items, how many ways are there to order all n of them?

This comes back to factorial, $n!$ is the number of ways to order $n$ items. This is a more true definition of factorial, which tells us what the value of 0! should be.

Think first: What do you think 0! should be?

If we have no objects to arrange, there's 1 way to arrange them: do nothing! So, $0! = 1$.

Now, let's try to think about what realistically happens when we eat a sandwich. It doesn't really matter what order the worker puts on each vegetable.

We do know that for picking $7$ out of $7$ options, we want the answer to be $1$. Let's try to figure out how to modify our permutation formula to get the correct values.

Note that when we pick our items in order, we can count the number of ways they are ordered.

For each of the sets of k items we pick, there will be $k!$ orders we don't care about. Note that this type of problem should sound a little familiar.

Since each set has $k!$ extras, we can divide by a $k!$ to get rid of the extras from all the sets.

Check your understanding: Why are we dividing instead of subtracting or doing any other operation?

Check your answer

This is very similar to our multiplication principle, it's just the reverse! For each unordered set, there are $k!$ orders, and all of these orders are counted in the final total. To undo multiplication, we use division, so dividing by $k!$ makes sense.

This operation: finding the number of unordered subsets of a larger set is called a combination, denoted ${n \choose k}$ and can be evaluated mathematically as

$${n \choose k} = \frac{n!}{k!(n-k)!}$$

We sometimes pronounce this as "n choose k" since we're choosing $k$ objects out of $n$ total objects. An easier way of writing this is $C(n, k)$, which you can use in Zoom chats or in messages if you're unable to use a mathematical expression tool. In LaTeX, we type { n \choose k } in math mode to write the more mathematical form.

Check your understanding: Does the picking 7 from 7 result in the answer we expect (1)?

Check your answer

Yes! ${7 \choose 7} = \frac{7!}{7!(7-7)!} = \frac{7!}{7!} = 1$

It is possible to memorize the formulas for combination and permutation, but I would advise against simply trying to remember the formulas. This leads to some common errors that could be easily avoided if students instead remember the ideas behind each operation.

Thinking about ideas rather than the formulas will also help in combinatorial proofs.

Check your understanding: What should ${7 \choose 0}$ logically be? What does it work out to be mathematically?

Check your answer

This is very similar to ${7 \choose 7}. If we want to order zero objects, there's one way to do that: do nothing. ${7 \choose 0} = \frac{7!}{0!(7-0)!} = \frac{7!}{7!} = 1$

Pascal's Triangle

Pascal's Triangle is a famous mathematical structure that contains combinations and important identities. Here are two versions of the first few rows.

Pascal's Triangle, two ways

We consider the top row to be the 0th row, then the 1st row underneath it, 2nd row underneath that and so on.

This triangle showcases some important properties of combinations, as well as displaying a topic we will discuss later.

Think about it: Just looking at the structure now, what do you notice? Do you see any patterns? What would be the easiest way to start writing this triangle from scratch? Is computing all the combinations easiest, or is there a different way to look at the triangle?

Counting Strategies

We can use the basic principles along with factorials, combinations, and permutations to solve many different types of problems. There are many strategies to solve counting problems, and we'll discuss the most important ones here.

Readings

Please read this first before moving on to the documents here on Anchor. As a reminder, and for reference, specific chapters are referenced at the beginning of the section for which they are relevant. Feel free to go back to the text(s), or review it if there's been a break since you last read the material. The readings on Anchor have some information in common with the text(s). This is to ensure you see the information from some different perspectives.

Applied Discrete Structures Chapter 2.3-2.4, Chapter 8.5

Casework

In problem solving, a common strategy is to break a problem into parts. In combinatorics, we call this casework when the parts are non-overlapping.

When we count a problem by parts, where each part has nothing in common with any other part, we can use the addition principle to add up all of our values at the end.

For example, imagine drawing 3 cards from our kibo deck. How many ways could you draw at least 2 red cards?

If we need at least 2 red cards, 2 of the 3 could be red or 3 of the 3 could be red. So we can use these as our cases.

Case 1: How many ways are there to draw exactly 2 red cards in a hand of 3?

There are 20 red cards, and 100 cards that are not red. We can choose a red card, then another red card, then a card that's not red to get exactly 2 red cards in our hand.

Note that when we take one red card, there will only be 19 left, so we'll have to remember that when we multiply.

Think first: What do you think the answer is?

When we have a few cards in our hand, the order does not matter, so we need to do a combination rather than a permutation on the red cards.

$$\frac{(20 \cdot 19)}{2} \cdot 100$$

While we could multiply these values and get a final result, we are starting to see values that will be large.

In combinatorics, it's often worthwhile to leave final answers as a series of multiplications or additions, as long as there aren't too many.

So, we'll continue to the next case.

Case 2: How many ways are there to draw exactly 3 red cards in a hand of 3?

Even simpler here, the answer is ${20 \choose 3}$, as we just need to choose 3 red cards of the 20 possibilities.

Since these cases have nothing in common, we can add them to get the final solution.

$$\frac{(20 \cdot 19)}{2} \cdot 100 + {20 \choose 3}$$

This is the number of ways to draw 3 cards where at least 2 of the cards are red.

Complementary Counting

Think first: What would the universe minus $A^c$ be?

This would just be all things in A!

For counting problems, we can use this strategy to count the number of items in A, where A is the set of all events that follow the requirements of the problem.

First we count the universe (total), then the complement of A (all events that are not A), and we subtract to find the number of events that fit in set A.

For example, imagine we were asked instead how many ways a person could have fewer than 2 red cards in their hand out of 3 cards drawn.

We could do casework again for 0 or 1 red cards, but we've already computed the number of ways to get 2 or 3 cards, and we can use it here!

We also need to determine our universe. In total, we are pulling 3 cards from our deck of 120, so the number of total 3 card draws is ${120 \choose 3}$.

If we subtract the number of draws with 2 or 3 red cards, then we should only have sets which have less than 2 red cards!

Our answer is ${120 \choose 3} - (\frac{(20 \cdot 19)}{2} \cdot 100 + {20 \choose 3})$.

Think about it: Try solving this problem using casework, then use a calculator to compute your answer and the one above. Did they match?

This is an example of using complementary counting when we already computed a value, but it's also useful for certain questions on their own.

For example, what if I asked the number of ways to draw 2 or more red cards in a hand of 10? It would be far easier to compute the two cases of 0 red cards and 1 red cards, then the cases of 2, 3, 4, or 5 red cards. Keep this in mind when deciding what strategy to use to solve a combinatorial problem.

Remember when we asked how many ways there were to draw a red card, a 5, or a card with a k?

We could also look for what's not included. The negation of this statment is not red and not a 5 and not a k. This allows us to use multiplication principle since we can break it down into stages. $(6-1) \cdot (5-1) \cdot (4-1) = 60$. $6-1$ for $6$ colors, minus red, $5-1$ for 5 numbers minus the five, and $4-1$ for 4 letters, minus the k. Note that $120 - 60 = 60$ which was our answer from earlier.

Sometimes using complementary counting allows us to change our technique. Here, we multiplied instead of adding and subtracting, and it was a fewer steps. When it comes to solving problems, both ways are valid, but if you want to be the fastest, identifying the best method will help. This is similar in nature to choosing which algorithm will best suit a problem. You have to identify which algorithms could be used, then decide based on the problem which will be most efficient. Eventually, many people develop an intuition, but this takes time and practice.

Overcounting (and Correction)

This method has actually already been discussed. Remember how we fixed a permutation to get a combination? This uses the method of overcounting. If we know we are overcounting by a specific amount, we can correct that by removing the overcounted amount after we count everything.

Often, this is done using division, as was the case with permutation/combination. For example, if there are a group of 20 people, and everyone shakes hands with everyone once, how can we count the number of handshakes?

Note that there are 19 people that each person has to shake hands with, so our initial answer might be $20 \cdot 19$. However, this counts every handshake twice, as we count it once for each person involved in the handshake. Therefore the answer is $\frac{20 \cdot 19}{2}$.

Think about it: We can also count the number of handshakes starting at a specific person: the first person has 19 handshakes to do, the next person only has 18 hands to shake (since they already shook hands with the first person), the next person has 17 and so on. Do we still get the same answer if we complete the problem this way?

This can be used to deal with rotations and reflections as well. Imagine there are 10 people sitting down at a circular table and we want to know how many ways people could be seated.

We can start by pretending the people are in a line, and therefore there's simply $10!$ ways to arrange the people.

However, the seating is only really different if some person is sitting next to someone different. If we simply rotate where people are sitting by one seat, we don't want to count this again.

Note that there are 10 rotations around the table. So each arrangement has 10 extra rotations that are included. Therefore, we divide by 10 and get that the true answer is $9!$.

Think about it: What would happen for a group of 15 people around a table? 20? For n people around a circular table, what is the general answer? Can you think of a way to justify this general solution, other than stating we're dividing by the rotations?

A common type of problem in combinatorics is the rearrangement of letters. For example, how many ways can we rearrange the letters of the word MATHEMATICS?

There are 11 letters, so $11!$ would be a simple answer. However, there are some repeated letters. If we swapped the two As, it doesn't actually make a difference. For every valid different combination, there will be $1$ more ($2$ in total) that is the same, but with the As swapped. Same for the Ms and Ts. Therefore, we take $\frac{11!}{2\cdot 2\cdot 2}$

Think first: What happens for a letter that appears 3 times in a word?

Consider the word Lollipop. L appears 3 times! There will be $3!$ L "orders" that can happen, even if we don't see them. If we labeled them to make them different, we can easily see this is a permutation problem, hence the $3!$.

For lollipop, we have $\frac{8!}{3!2!2!}$.

Sometimes, reframing a problem as a letter arrangement problem can be helpful, as these are easy to solve, and have a known solution method!

The principle of inclusion-exclusion is also a method of correcting some amount of overcounting.

Pigeonhole Principle

Pigeons are a domesticated species of bird used to deliver messages. As they needed a place to stay when not doing this task, people built structures with a number of places (holes) for these pigeons to roost. However, if there were $n$ pigeons and $n-1$ places to roost, at least one of these pigeonholes would need to have more than one pigeon in it. Note that we are not guaranteed that there will be a box with two pigeons in it. All the pigeons could choose to try and squeeze into one hole! But it is true that in the best case scenario, each hole would have one pigeon and one would have two.

This is the idea behind pigeonhole principle: if there are $n$ items and $n-1$ boxes, or any number of boxes less than $n$, it is guaranteed that at least one box must contain more than one item.

This idea can be used for certain counting problems, though it's used in many places outside of combinatorics as well.

For example, imagine there's a drawer with 6 white socks, 6 grey socks, and 8 black socks. How many times would you have to take a sock from the drawer to guarantee a pair of matching socks?

Because there are only 3 colors, we're guaranteed that on the 4th sock, there's at least one matching pair. The 3 colors are our pigeonholes/boxes, and the socks themselves are the pigeons.

Pigeonhole principle can be applied to ensure more than any number are in a specific category as well. We're not restricted to showing there must be at least 2 pigeons in a box. The same reasoning applies: lay out the best case scenario, where all the boxes have fewer than the desired number, then show that when they're all at "maximum capacity," we still have some left over.

For example, consider a box of 24 donuts being left in an office of 5 people. If the box is empty at the end of the day, can we show that at least one person ate at least 5 donuts?

If every person takes 4 donuts, there will still be 4 leftover. This cannot be, since the box was empty, so we must make at least one person take 5 donuts.

Remember, we cannot guarantee any one person ate exactly 5 donuts, or that all people ate a certain number. There could be some donut-eating champion in the office who took all 24 before the others had a chance to even take one.

Pigeonhole allows us to make an "at least" condition, which is not strong, but can still be powerful in the right set of circumstances.

Sticks and Stones / Stars and Bars

Chapter 1.5

Remember: Please read the text linked above before reading the material below.

Imagine there's a bag of 30 candies to split between 5 children. The fair thing to do would be to either split evenly (6 each) or to split based on the ages of the children, but we just want to know how many ways we could distribute this candy, making sure each child gets at least one piece.

Imagine we line the candies up, and line the children up separately.

Think first: How could we use some sticks to mark one way to distribute the candies to the children?

We can just place some sticks between the candies, where the first set (from the beginning to the first stick goes to the first child, the next set goes to the next child and so on.

Think first: Draw a picture of this for 10 candies and 3 kids. How many sticks did you need to use? Do another picture for 10 candies and 4 kids. How many sticks did you need to use then? What about 12 candies and 4 kids? How many sticks do you need? For all of the above, how many places can you put the first stick? After the first is placed, how many places can you place the second stick?

We'll note that we don't need as many sticks as we have children, but one less than that number, since the first and last groups have one stick definining the right and left borders.

It's also important to note that if we want to guarantee each child gets at least one candy, we can only place sticks in between two pieces of candy. This means the number of gaps defines where we can place sticks, which is also the number of candies minus one.

Since the order we place this sticks doesn't matter, this is a combination problem, where there are $n-1$ gaps (for $n$ candies), and $k-1$ sticks to place/places to choose (for $k$ children). This means the problem is ${n-1 \choose k-1}$ in general, or ${30-1 \choose 5-1}$ in the case of our specific problem.

Now what if we don't care if a child doesn't get any candy?

Think first: what changes about our requirements? Do the number of sticks change? Where can we place sticks?

The number of sticks should remain the same, as this still defines how much each child recieves. Likewise, this is still a combinations problem, as the order of how we place the sticks doesn't matter.

When we are allowed to give a child no candy, this means we can now place sticks before the line of candy, and multiple sticks between two pieces of candy. We can try to change how we did the previous problem to accommodate this, or we can realize this re-shapes our problem into something else.

We're just arranging the $n$ candies and the $k-1$ sticks. We can reframe this as a letter problem. If we have $n$ Cs and $k-1$ Ss, how many distinct arrangements of these letters can we create?

This is simply $\frac{(n + k - 1)!}{n!(k-1)!}

Notice that this is the same as ${n+k-1 \choose k-1}$ or ${n+k-1 \choose n}$.

Check your understanding: How is this problem the same as a combination?

Check your answer

This is the same as choosing the $k-1$ spots the sticks go out of a total of $n+k-1$ spots and placing the $n$ candies around it or vice versa.

These situations are both considered as the stars and bars (or sticks and stones) method. The candies are the stars/stones, and the sticks are the bars/sticks.

This method works for many types of problems, including the ones mentioned in the chapter involving integer-valued solutions to simple functions.

Think about it: Try to come up with a problem that can be solved using stars and bars, then solve it using stars and bars.

Pascal Identities

Chapter 1.2 Chapter 1.4

Remember: Please read the texts linked above before reading the material below.

Pascal's triangle has many patterns and identities within the structure.

Pascal's Triangle, two ways

Think first: Try finding as many identities as you can. What do you notice about Pascal's triangle? Are there any relationships between rows? Are there any relationships in each row?

Below is a table of a few identities and the way we see them in the triangle.

Identity	Where it is in Pascal's Triangle
${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$	Each entry is the sum of the two entries above it in the triangle.
$\sum_{k=0}^n {n \choose k} = 2^n$	The $n$th row sums to $2^n$.
${n \choose k} = {n \choose n-k}$	The rows in Pascal's triangle are symmetric.
$\sum_{k=0}^n (-1)^k{n \choose k} = 0$	When you alternate adding and subtracting each entry in a row, the value is 0.
$\sum_{k=r}^n {k \choose r} = {n+1 \choose r+1}$	Find a point on the edge of the triangle, and follow a straight line. Taking a turn will give you the sum of the line of combinations you passed over. An image of this is below.

The first identity is known as Pascal's Identity, and the last is known as the Hockey Stick Identity.

The Hockey Stick Identity

Shown above, ${1 \choose 0} + {2 \choose 1} + {3 \choose 2} + {4 \choose 3} = {5 \choose 3}$, which is true when computed!

These identities are well known, and can be used in combination with other methods to prove a combinatorial identity, or to quickly solve a problem.

This is not a full list of the identities or properties that can be found in Pascal's triangle, but these are the most commonly known.

The Binomial Theorem

Chapter 1.2 Chapter 2.4

Remember: Please read the texts linked above before reading the material below.

The Binomial Theorem finds a relation between $(x + y)^n$ and Pascal's Triangle.

For each simplified term in the expanded form, there may be some coefficient. Let's try to figure each out for a simple case.

For $(x + y)^4$, we can rewrite this as $(x+y)(x+y)(x+y)(x+y)$

Each term must have one of the variables from each set of parentheses since we're performing multiplication through the distributive property.

For example, we know there's an $x^4$ and a $y^4$ term. There's only one way to make each of these: by selecting the same variable in each set of parentheses, so the coefficient will just be 1. So $x^4$ comes from choosing $x$ at every set of parentheses when multiplying.

$$(\underline{x}+y)(\underline{x}+y)(\underline{x}+y)(\underline{x}+y)$$

Next, we know there will be an $x^3y$ term. We need to select 3 $x$ terms, and one $y$ term. This mean we must choose $3$ of the set of parentheses to be $x$, but how many ways can we choose 3 of the 4 parentheses? This is ${4 \choose 3}$.

$$(\underline{x}+y)(\underline{x}+y)(\underline{x}+y)(x + \underline{y})$$

$$(\underline{x}+y)(\underline{x}+y)(x + \underline{y})(\underline{x}+y)$$

$$(\underline{x}+y)(x + \underline{y})(\underline{x}+y)(\underline{x}+y)$$

$$(x + \underline{y})(\underline{x}+y)(\underline{x}+y)(\underline{x}+y)$$

Likewise, for $x^2y^2$, we must choose $2$ to be $x$, therefore we have ${4 \choose 2}$, and for $xy^3$, we just choose one to be $x$, and we have ${4 \choose 1}$.

So we have: $x^4 + {4 \choose 3}x^3y + {4 \choose 2}x^2y^2 + {4 \choose 1}xy^3 + y^4$.

Think first: Do you see the connection to Pascal's Triangle yet?

Notice that ${4 \choose 4}$ and ${4 \choose 0}$ are both $1$. This is also what we were doing to find our answer, choosing $4$ of $4$ to be $x$ or $0$ of $4$ to be $x$.

So we have ${4 \choose 4}x^4 + {4 \choose 3}x^3y + {4 \choose 2}x^2y^2 + {4 \choose 1}xy^3 + {4 \choose 0}y^4$.

We can generalize this pattern to happen for any $n$ value, and therefore we always know the coefficient on any specific term of $(x + y)^n$.

Generating Functions

Chapter 8.5 Chapter 5.1

Remember: Please read the texts linked above before reading the material below.

We can also use coefficients of functions other than $(x + y)^n$ to try and count events.

A generating function has a coefficient on the $n$th term which is the solution to the problem at the $n$th step or at the $n$th level.

For example, a generating function for the fibonacci sequence would have the $n$th term of the fibonacci sequence as the $n$th coefficient.

These can be used to solve problems, find closed forms, or approximate bounds for numbers.

There is actually a closed form formula to find the $n$th term of the fibonacci sequence. It's $\frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}}$ where $\phi = \frac{1 + \sqrt{5}}{2}$

We can find this using generating functions.

First, note our function looks like this:

$F(x) = 1 + 1x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + ...$

With generating functions, we often apply little tricks to get us into the form of a recurrence. We know for fibonacci $f_n = f_{n-1} + f_{n-2}$.

Notice if we multiply $F(x)$ by $x$, we get

$xF(x) = 1x + 1x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + ... $

Which just shifts all the numbers over by one.

Think first: what happens if we multiply by $x^2$?

$x^2F(x) = 1x^2 + 1x^3 + 2x^4 + 3x^5 + 5x^6 + 8x^7 + ... $

It shifts by two!

Let's carefully add these together, combining like terms:

$1x + (1 + 1)x^2 + (1 + 2)x^3 + (2 + 3)x^4 + (3 + 5)x^5 + (5 + 8)x^6 + ...$

$1x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + 13x^6 + ... $

This is almost our original $F(x)$! We just need to add a $1$.

$F(x) = xF(x) + x^2F(x) + 1$

Now, we want a closed form value for the $n$th coefficient on $F(x)$, so let's try solving this equation for $F(x)$, treating it like a variable.

$F(x) - xF(x) - x^2F(x) = 1$

$F(x) (1 - x - x^2) = 1$

$F(x) = \frac{1}{1 - x - x^2}$

This is where our skills in series are useful. If we can get some form like $\frac{1}{1 - x}$, then we know it's a geometric series! We could find the coefficient.

Through a process called partial fraction decomposition we can turn a fraction with a factorable base into two fractions with those bases. This is what leads to the final solution.

These last few steps are not as necessary to a discrete math course. Feel free to research the remaining steps and how they lead to the final closed form, as this could be used as a potential project topic.

Note that our function is not exactly this, since we started the fibonacci sequence at $f_0 = 1$. The equation as given acts as if $f_0 = 0$.

Think about it: What difference would that make to our process? How would it change the closed form we find?

Generating functions are a mathematical tool, but I will not expect you to complete all the steps of computing them in this class. I do expect you to be able to identify potential uses for generating functions.

Week 5: Self-Guided Problems

When you come to class, be ready to discuss these questions, and bring any additional questions you still have after this exercise!

Submitting Your Work

Your work must be submitted to Anchor for degree credit and to Gradescope for grading.

For any work completed outside of GitHub or Gradescope:

Typeset your work in LaTeX.

You should use \begin{enumerate} to create a numbered list, and your solutions to each problem should match with the corresponding number on the assignment.
For example, if an assignment has 10 numbered problems, your enumerate should have 10 \item commands, with your solution(s) to problem 1 under the first \item, problem 2 under the second and so on.
If you skip a problem, just leave the \item blank, otherwise the numbers of your solutions will not match the assignment document.

Compile into a PDF. This can be done easily through an Overleaf account, otherwise you will need to install LaTeX.
Submit the pdf to Gradescope via the appropriate submission link for the course.
Upload the pdf to Anchor using the form below.

Note: Anchor submissions can occur at any time during the term, but it is critical that you upload all of your work to Anchor before the last day of the term. Gradescope submissions must be submitted before the deadline (or the late deadline, if applicable).

It is required that all assignments are submitted as a PDF generated from a LaTeX document.

Assignments submitted in any other form will earn zero credit.

ChatGPT/AI

Use of ChatGPT/AI is forbidden for all assignments in this course.

Self-Guided Problems cannot be submitted late for any reason

This is due to the fact we discuss them in the class. Be sure to stay on top of these Self-Guided problems, and remember it is better to turn in an incomplete set than an empty one.

Problems

Suppose we want to count:

The number of ways to rearrange the letters KIBO.
The number of ways to rearrange the letters KIBO where K is not the first letter.
The number of ways to rearrange the letters KIBO where none of the letters are in the position they are currently in.

Which of these problems should have the largest answer? Which is the smallest?

Solve all of the problems from problem 1. What technique did you use to solve them?
Consider the act of rolling 2 6-sided dice labeled 1,2,3,4,5, and 6 on their faces. Create a chart of the possible sums of these dice when rolled. What do you notice about this chart? How would you have counted the number of ways to roll a specific sum (say, 7)?
Suppose there are 50 people in our class. Using pigeonhole principle, find the following:

a. What is the minimum number of people who were born on the same day of the week?

b. What is the minimum number of people that are born in the same month?

c. What is the minimum number of people that have the same eye color?

Homework Set 5

Submitting Your Work

Your work must be submitted to Anchor for degree credit and to Gradescope for grading.

For any work completed outside of GitHub or Gradescope:

Typeset your work in LaTeX.

You should use \begin{enumerate} to create a numbered list, and your solutions to each problem should match with the corresponding number on the assignment.
For example, if an assignment has 10 numbered problems, your enumerate should have 10 \item commands, with your solution(s) to problem 1 under the first \item, problem 2 under the second and so on.
If you skip a problem, just leave the \item blank, otherwise the numbers of your solutions will not match the assignment document. Here is an example Overleaf document showcasing this format.

Compile into a PDF. This can be done easily through an Overleaf account, otherwise you will need to install LaTeX.
Submit the pdf to Gradescope via the appropriate submission link for the course.
Upload the pdf to Anchor using the form below.

Note: Anchor submissions can occur at any time during the term, but it is critical that you upload all of your work to Anchor before the last day of the term. Gradescope submissions must be submitted before the deadline (or the late deadline, if applicable).

ChatGPT/AI

Use of ChatGPT/AI is forbidden for all assignments in this course.

It is required that all assignments are submitted as a PDF generated from a LaTeX document.

Assignments submitted in any other form will earn zero credit.

Suppose your teacher has a set of 500 math problems to distribute amongst the class. If there are 50 people in the class, how many ways can these problems be distributed if:

a. There are no other restrictions

b. Each student must have at least 1 problem.

c. The students are in groups of 5, and the problems are distributed to groups.

d. The problems are distributed evenly amongst the students.

Show that if there are 500 problems and 50 students, at least one student must have 10 or more problems.
Imagine you have a set of dice. There are 4 6-sided dice and 4 8-sided dice.

a. How would you set up generating functions to solve a problem about the number of ways a specific sum could occur when rolling this set of dice? \textbf{Do not attempt to solve this problem, just explain how you would set it up.}

b. If you rolled only the 6-sided dice, What are the maximum and minimum sums?

c. If you rolled only the 6-sided dice, of all possible sums after the dice are rolled, what sum do you think is most common?

d. If you rolled only the 8-sided dice, of all possible sums after the dice are rolled, what sum do you think is most common?

If there is a set of the integers from 1 to 9, any subset of size 6 must contain two numbers that sum to ten.

a. If you have a set of integers from 1 to 11, what can we say instead? What size subset is needed for two numbers to sum to 12?

b. If you have a set of integers from 1 to 13, what can we say now? This time give the size of subset and the sum.

c. What would this problem be for a set of integers from 1 to n?

Suppose you are at a deli. There are 5 types of meat, 4 types of cheese, 3 types of bread, and 7 types of toppings.

a. How many ways are there to make a sandwich with one type of each item?

b. How many ways are there to make a sandwich with two types of toppings, and one type of every other item?

c. How many ways are there to make a sandwich with any combination of toppings? Assume there is one type of each other item on the sandwich.

d. How many ways are there to make a sandwich if you can order double meat or two different kinds of meat? Assume there is one type of each other item on the sandwich.

Project Selection

Remember to submit the module that is most related to a project topic you have in mind.

If you don't yet have an idea for a project, submit the module you are most interested in, and work on a project idea before the proposal deadline.

Submit a PDF containing a module number to Anchor, and the associated assignment on Gradescope.

Combinatorial Proofs & Probability

This week, we'll cover probability. This includes a probability definition for discrete and continuous probability, related probability notions of independence, conditional probability, expected value, and probability distributions.

Readings

Introduction to Probability Chapter 1 Chapter 4 Chapter 6.1

By the end of the week, you should be able to:

Provide a sketch of a combinatorial proof for simple identities.
Determine the probability of discrete probability problems.
Determine the probability of continuous probability problems.
Use Bayes Theorem to solve dependent probability problems.
Find the expected value of events.
Identify real-life instances of named probability distributions.

Counting Proofs

There is one more proof types that we can use for counting problems or related arguments. This is quite different from the proof methods we've seen before, but this proof style can be quite useful for proving identities.

Readings

Please read this first before moving on to the documents here on Anchor. As a reminder, and for reference, specific chapters are referenced at the beginning of the section for which they are relevant. Feel free to go back to the text(s), or review it if there's been a break since you last read the material. The readings on Anchor have some information in common with the text(s). This is to ensure you see the information from some different perspectives.

Discrete Mathematics: An Open Introduction, Chapter 1.4

Combinatorial Proofs

Chapter 1.4

Remember: Please read the text linked above before reading the material below.

The basic premise of a combinatorial proof is that we're proving both sides of an equality count the same thing. We make up a problem, then solve it using both methods.

Combinatorial proofs are my personal favorite. Why? They're about telling a story.

I'll try to keep the stories simple and generic in the notes, but I highly encourage you to be creative in your own combinatorial proofs! They should still be readable, and should not require extra context to understand, but if you want your proof to be about your favorite animal or an activity you enjoy, feel free to use your experience if it fits.

If you were to publish results in a paper, you'd need to stick to a more boring problem, but that's not what we're doing here! It might help to stick to more generic examples at first, using problems we've already seen, but you're free to do as you wish.

Let's try proving Pascal's Identity. We can already mostly see it's true, but we cannot trust patterns in mathematics. We must prove them to be sure.

$${n-1 \choose k} + {n-1 \choose k-1} = {n \choose k}$$

Proof.

Suppose we're forming a committee from $n$ people, and need a advisory board of $k$ people. How many different advisory boards could we create?

Right Hand Side (RHS):

The simplest way to count this is to simply choose the $k$ members from the $n$ total people: ${n \choose k}$

Left Hand Side (LHS):

Suppose you yourself are in the group of $n$ people. Thinking about yourself, there are two options: you're in the advisory board or you're not. These are disjoint sets so we can count them separately, then add up the results.

If you're in the group, you need to choose $k-1$ people to join you from the other $n-1$ committee members. This is ${n-1 \choose k-1}$.

If you're not on the board, you need to choose all $k$ members from the other $n-1$ committee people. This is ${n-1 \choose k}$

This indeed covers all posibilities (there is no third option where you are both not on the board and on the board), so the final result is ${n-1 \choose k} + {n-1 \choose k-1}$

Since these both count the same problem, they are the same.

QED

This particular type of problem is a common in combinatorial proofs, and it is called a committee-forming proof. The "advisory board" in our problem was left vague since $k$ is an unspecified number, but often it can be done for choosing a chair, choosing a president, vice-president, and secratary, or any other combination which lines up with the identity.

Here's an identity we haven't seen yet:

$$\sum_{i=0}^n {n \choose i}^2 = {2n \choose n}$$

The left-hand side is the sum of the squares of a row in Pascal's triangle.

Note that we can use identities to help us within these combinatorial proofs.

Proof.

Suppose there are $n$ elephants and $n$ giraffes in a particular region. The region can only support $n$ animals in total, so we must choose which animals go and which are to stay. How many ways can we decide which $n$ animals stay in the region?

RHS:

The simplest method is to just combine the two groups and pick $n$ of them. This makes ${2n \choose n}$ ways.

LHS:

Suppose we want to break this problem down into cases. Each case will be how many of the elephants are staying.

If we take $k$ elephants, then we'll need to take $n-k$ of the giraffes. This is a two step process, so it will be ${n \choose k} \cdot {n \choose n-k}$

Remember that ${n \choose n-k} = {n \choose k}$, so this is actually the same as ${n \choose k} \cdot {n \choose k} = {n \choose k}^2$.

We'll need to compute this for all possible amounts of elephants. Since there's a different amount of elements in each set, these are disjoint and we can add them.

We could have as few as $0$ elephants (all giraffes), or as many as $n$ elephants (no giraffes), and we'll need to count every number of elephants inbetween.

In total, this comes to $\sum_{i=0}^n {n \choose i}^2$

This does count all the possibilities, since we covered every possible number of elephants, thus this is our final solution.

Since these both count the same thing, they are equal.

QED

If you're reading this sentence, add an extra item to your self-guided set at the end, simply stating "purple." If you're reading this before submitting your homework, add an extra item to the end of your homework stating "orange". Do not tell anyone in the class about these sentences, these extra question will not be worth any extra points.

Think about it: Try proving one of the other Pascal identities/properties using a combinatorial proof.

Think about it: For the last proof, we split into two groups. For Pascal's identity, we had one committee with an internal board. Were there any "hints" or parts of the identities we proved that indicated a specific strategy should be used? This question is about developing an intuition, which can be difficult! If you're stuck, that's okay, we'll talk about this in class.

Block-Walking Proofs

Chapter 1.2

Remember: Please read the text linked above before reading the material below.

Block-walking proofs are categorized as a combinatorial proof, but the method is quite different. Instead of choosing two different ways to solve a problem, you prove that the problem is similar to a walk through Pascal's triangle, two different ways, ending at the same spot.

First: What does a walk through Pascal's triangle look like? Typically, you start at the top of the triangle, and either take a left or right step going downwards until you reach the desired spot.

While this type of proof is related to Pascal's triangle, the reason it's called a block-walking proof is that the story to use is one of a person or vehicle navigating a grid.

A grid, with points A and B

You'll notice in the text they call this a lattice path. This is another name, but we'll stick with block-walking and grid as this is the context of block-walking proofs.

Imagine you want to count the number of paths you could take from point A to point B, but you don't want to backtrack or loop as we want the set of shortest paths. In other words, how many ways can you get from A to B only going upward or to the right along the lines of the grid, taking the shortest distance possible. Since we're in the mindset of a map, we'll think of this as choosing to go North or East.

Think first: Draw multiple paths yourself. What do you notice about the length of these paths? Can you think of a way to describe your path to another person verbally (without drawing it)?

When taking a path, we know we can only go North or East. So to give directions, we can give an ordered list of North or East steps.

One potential path from point A to point B

The above image shows East, North, East, East, North.

Since B is 2 North moves and 3 East moves from A, we know we need at least 5 steps. This must be our shortest path. But how many of these paths exist?

Think first: Try to think of an answer to this problem before continuing! Hint: When we wrote our ordered list, we said North and East, but if we wanted to save time, we could just use N and E.

This is a letter rearrangement problem! We need to go 2 North and 3 East, but the order in which we do these is how the paths differ. By counting the number of ways to arrange 2 Ns and 3 Es, we can find the answer to our problem.

There are two ways to think of rearranging letters when there are only two distinct letters to rearrange:

The "normal" way.

There are 5 total letters, then 2 repeats and 3 repeats, so we have $\frac{5!}{2!3!}$ as our solution.

The combinations way.

We have 5 steps we need to write. We can first select where the Ns will go in ${5 \choose 2}$ ways. Then the remaining spots will be filled with Es. This thinking can also be applied in the other direction: We select where the Es will go in ${5 \choose 3}$ ways, and the Ns will fill in the remaining spaces.

All ways result in the same answer, but I encourage you to think in the combinations way for the next part.

Check your understanding: Fill in the number of ways to get to each intersection of the grid from point A, taking the fewest amount of steps possible. You may compute the numbers, but it may be easier to leave these in combination form. What do you notice here?

Check your answer

All points labeled

This looks like Pascal's Triangle!

Indeed, this method of counting paths is closely related to Pascal's triangle, and we can use it to prove identities and properties related to the structure of Pascal's triangle.

Consider Pascal's Identity itself.

Think first: How does this block-walking problem show that adding the two previous entries should result in the next entry?

Looking at our example from before, let's find the two previous entries in our grid.

The two previous entries

We should notice that all paths to B must pass through one of these two points. These points differ in whether the last step is North or East.

Since the last step is different for all paths that pass through these points, the set of paths through point C and the set of paths through point D are disjoint.

By the Principle of Addition, we can add these.

Check your understanding: How do we know this includes all potential paths from A to B?

Check your answer

As mentioned, these are the points one step away from the finish line.

You can check yourself by drawing paths that they must pass through one of these, since the last step must always be a North or an East by our rules.

The two previous entries

While we were looking at a specific example, all of our reasoning holds in a general case, and so we have proven Pascal's identity again!

Think about it: How does this proof relate to the combinatorial proof that we already did? Which do you personally find easier for this problem? Which do you think is easier in general? Note that these last two questions are about you and your intuition, so there is no "right answer."

Check your understanding: Can you prove that ${n \choose k} = {n \choose n-k}$ using block-walking? Hint: Where are each of these in the grid, and what is the relationship between the two problems? This is the key to your proof. You may need to try a specific example first, like ${5 \choose 2}$ and ${5 \choose 3}$

Check your answer

You may notice that ${n \choose k}$ is just a rotated version of ${n \choose n-k}$.

Therefore, these problems are the same, since we can rotate our paths over the line $y = x$

Another way to put this would be that we're simply swapping the N and E values to get a solution to the other problem.

You may notice that combinatorial proofs seem more relaxed than other proof types. Don't be fooled! These still need to be rigorous, and their relaxed nature can make it harder to spot mistakes.

Arriving at the correct conclusion does not mean that your proof is valid.

Keep in mind that the lessons we learned in week 4 still apply.

Note: All the grids on this page were made using the Tikz package in LaTeX. It's very useful, but can be challenging to use.

Basic Probability Definitions

An Intuitive Definition

Imagine you have a six-sided die. What's the probability of rolling a one? What is the probability of rolling an even number?

Think first: Answer these!

There are 6 options on the die, only one is a one, so there is a $\frac{1}{6}$ chance of rolling a one.

Likewise, there are 3 even numbers on the die, so there should be a $\frac{3}{6}$ or $\frac{1}{2}$ chance of rolling an even number.

As it turns out, these are the correct probabilities! In easy cases of dice, coins, and cards, finding the probability is simple.

Check your Understanding: What is the probability of flipping a head on a fair coin? What is the probability of drawing a red card from our KIBO deck in the previous section? What is the probability that the sum of two 6-sided dice is 7?

Check your answer

Head: $\frac{1}{2}$ Red Card: $\frac{20}{120}$ or $\frac{1}{6}$ Sum: $\frac{6}{36}$ or $\frac{1}{6}$

Think about it: The red-card probability can be found by counting all red cards and all cards in total, but is there an easier way to think about the problem to get the answer of $\frac{1}{6}$?

Imagine a die with 2 ones, 2 twos, and 2 threes.

Think first: What is the new probability of rolling a one with this die?

There's a $\frac{1}{3}$ chance of rolling a one this time, from $\frac{2}{6}$.

What changed? To define probability better across all situations, we should use mathematical terms.

Mathematical Definition of Probability

If we have a discrete set of equally likely outcomes, we can consider probability in the following way:

Let $S$ be our sample space, which is a set that contains all possible outcomes.

We can define the probability of an event, $e$ as

$p(e) = \frac{\text{Number of outcomes in }e}{\text{Total number of outcomes in }S}$

This is sometimes also written as

$\frac{\text{Number of favorable outcomes}}{\text{Total number of outcomes}}$

These definitions line up with how we intiutively decide probability above! But note that it has some conditions.

There needs to be a finite number of outcomes.
These outcomes must be equally likely.

On our die with only 1, 2, and 3, the outcomes are still equally likely, so we can use this definition. However, what if the die had only one 3 and three 1s?

Think first: What do you think the probability is?

Half of the numbers on the die are 1, so this should be $\frac{1}{2}$

With this example, we can change the problem slightly to have something that fits the definition better.

Pretend each face of the die is a different color. That way, we have different outcomes for each face. Then, all outcomes are equally likely, so we just have to sum the ones that are favorable: the three faces that have a one on them.

Some problems can be adapted, but some cannot. For example, if I just told you I had an unfair die, and no other information, you could not find the probability. If I told you there were 3 ones, but did not tell you the die had 8 sides, you would get an incorrect result.

Knowing all of the faces, or at the very least, all of the relevant faces and the total number of faces on the die, allows us to know what all the outcomes are, and if we assume the die is fair, know how likely each face is to appear.

Think about it: If you were told a coin flipped heads 70% of the time, could you figure out the probability it flips tails? How would you do so?

Rules of Probability

There's also an unsaid, but important, condition that all possible probabilities over a sample space should sum to 1. Intuitively, this should make sense, the probability of a coin flipping either heads or tails should be 100%. In the case of finite outcomes, this is especially important, and it is something to consider with continuous probability, which we will discuss later.

Think about it: Convince yourself that this condition is satisfied by the definitions above.

Independence

Since probabilities on a finite set of outcomes involve counting, we often add or multiply probabilities.

Combining Probabilities: Addition

The probability of rolling a 1 or a 6 on a fair 6-sided die is the probability of rolling a 1 plus the probability of rolling a 6.

By definition: $P(1 \text{ or } 6) = \frac{2}{6}$

By addition: $P(1 \text{ or } 6) = \frac{1}{6} + \frac{1}{6} = \frac{2}{6}$

However, just like with counting, we need to be careful.

What is the probability of drawing a red card or a card labeled "k" from our Kibo deck?

Think first: What do you think the answer will be?

If we just add as before, we would have $\frac{20}{120} + \frac{30}{120} = \frac{50}{120} = \frac{5}{12}$

If we follow the definition, to count the number of cards labeled "k" or red cards, we would need to follow the principle of inclusion-exclusion.

$20 + 30 - 5 = 45$

The probability would be $\frac{45}{120} = \frac{3}{8}$

We have two different answers!

Think first: Can you find the mistake in the first method?

When adding probabilities, the principle of Inclusion-Exclusion applies! There's an overlap in the events of "drawing a red card" and "drawing a card labeled 'k'," which needs to be removed.

The formula for finding probabilities of event $A$ or event $B$ happening, is therefore:

$P(A \cup B) = P(A) + P(B) - P(A \cap B)$

Note that when $A \cap B$ is empty (the events have nothing in common), $P(A \cap B)$ will be zero! This means that this formula works regardless of whether or not the events overlap. When $P(A \cap B)$ is zero, $A$ and $B$ are called Mutually Exclusive or Disjoint.

Combining Probabilities: Multiplication

The probability of rolling a 1 and then a 6 is the probability of rolling a 1 times the probability of rolling a 6.

Multiplying: $\frac{1}{6} \cdot \frac{1}{6} = \frac{1}{36}$

Definition: $\frac{1}{36}$, since there are $36$ different ordered dice rolls.

However, we need to be careful.

Consider the probability of drawing a red card, then an orange card.

Multiplying: $\frac{20}{120} \cdot \frac{20}{120} = \frac{1}{6} \cdot \frac{1}{6} = \frac{1}{36}$

Definition: $\frac{20 \cdot 20}{120 \cdot 119}$, since drawing a red, then an orange is $20 \cdot 20$ and drawing any two cards is $120 \cdot 119$.

These are once again different!

When events do not effect each other, they are called Independent. Two events, $A$ and $B$ are independent if

$P(A \text{ and } B) = P(A) \cdot P(B)$

If this is not true, events are considered dependent.

Think first: Why didn't multiplying work here? Is there a way you could fix what we did, like we did for addition?

Conditional Probability

Conditional probability allows us to find the probability of an event given that another event has occurred. There are two ways to think about this type of event. It could be true that a physical change from the first event effects the second event. It could also be true that if the first event is true, or falls into a certain category, it changes the probability of the second event. For this section, we'll focus on the first type, as the second will be covered in the section on Bayes' Theorem.

For example, when drawing cards from a deck, if we don't place the cards back, the chance we pull a certain type of card changes each draw. Not only does the size of the deck change, but we could pull a card in the category of what we would like to draw next.

What is the probability you draw a red card as your second card?

This depends:

If your first card was not red, then it should be $\frac{20}{119}$ for the 20 red cards remaining in the deck of 120 minus the first card you drew.

If your first card is red, then it should be $\frac{19}{119}$ for the 19 red cards left in the deck of 119.

Each of these separately is a conditional probability. The first is the chance of drawing a red card given that you've drawn a non-red card, and the second is the chance of drawing a red card given that you have drawn a red card already.

While this answers the question of what conditional probability is, how do we combine these into one probability?

Think first: What do you think you should do?

The conditional probabilities assume the event has already occurred, so we need to bring in the probabilities of the first events themselves.

The overall probability of drawing a non-red card, then drawing a red card is $\frac{100}{120} \cdot \frac{20}{119}$

The overall probability of drawing a red card, then drawing another red card is $\frac{20}{120} \cdot \frac{19}{119}$

Since these events do not have anything in common, we can add them to get the total probability.

$\frac{100}{120} \cdot \frac{20}{119} + \frac{20}{120} \cdot \frac{19}{119} = \frac{100 \cdot 20}{120 \cdot 119} + \frac{20 \cdot 19}{120 \cdot 119} = \frac{100 \cdot 20 + 20 \cdot 19}{120 \cdot 119} = \frac{100 + 19}{6 \cdot 119} = \frac{1}{6}$

Note that it's the same probability as drawing a red card from the deck.

Think about it: Can you figure out why the probability the second card drawn is red is the same as the probability that the first card drawn is red?

Conditional probability is denoted with a bar (|) read as "given", so the probability of $A$ given $B$ would be denoted:

$P(A|B)$

We can also note here that this provides the solution we needed to our multiplication problem!

$P(A \cap B) = P(A|B)\cdot P(B)$

Note that we can do this both ways:

$P(A \cap B) = P(B|A)\cdot P(A)$

Just like with addition, if there's no change from the first event happening, then

$P(A|B) = P(A)$

Since the probability is unaffected.

Check your understanding: What is the probability that the sum of two dice is even? Try doing this by calculating the probability the sum is even when the first die is odd, and the probability the sum is even when the first die is even. Does the answer make sense?

Check your answer

$P(\text{Sum is even} | \text{First die odd}) = \frac{1}{2}$, since we need another odd number.

$P(\text{Sum is even} | \text{First die even}) = \frac{1}{2}$, since we need another even number.

$P(\text{Die rolls even}) = P(\text{Die rolls odd}) = \frac{1}{2}$.

So the total probability is $P(\text{Sum is even} | \text{First die odd}) \cdot P(\text{Die rolls odd}) + P(\text{Sum is even} | \text{First die even}) \cdot P(\text{Die rolls even}) = \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4} + \frac{1}{4} = \frac{1}{2}$

This should make sense, as it's just 50/50 odds of rolling even or odd in the first place. The sum is no different.

Bayes Theorem

Introduction to Probability

These two videos are some of the best videos from 3Blue1Brown in terms of explaining a mathematical concept that is relevant to many areas of real-life situations. Please watch them to understand Bayes Theorem on an intuitive level. Note that these videos are a required portion of your readings for this week.

Feel free to pause, rewind, and think about the ideas brought up in these videos.

Continuous Probability

Chapter 2

Imagine a situation where there are infinitely many options, like a number line. How do we decide probabilities?

Instead of counting, we consider area. Watch the following video to see how (and why) we use area to calculate probability.

The problem in this video is a little more complex than needed. A classic continuous probability problem involves two friends trying to meet.

For some reason, two friends decide not to tell each other what time they will arrive at a local meeting spot. Each will arrive at some random time between 4:00 PM and 5:00 PM, however, they are impatient, and if the other person doesn't arrive within 15 minutes of their arrival, they will leave. What is the probability they actually meet?

We can represent one friend's arrival on the x-axis, and the other friend's arrival on the y-axis, then color the portion where they will meet.

Here is a link to a desmos graph of what this looks like.

Keep in mind the total possibilities is the square defined by $x=0$, $y=0$, $x=60$, $y=60$, since we assume they arrive sometime in that range. The total area of outcomes is $60^2$

To find the area of the favorable outcomes, it might be easier to find the area of the triangles and subtract. Each triangle is $\frac{1}{2}45\cdot 45$, but there are two, so the total area of "unfavorable" outcomes is $45^2$. Our probability will be $\frac{60^2 - 45^2}{60^2}$.

Our formula for continuous probability becomes

$\frac{\text{Area of Favorable Outcomes}}{\text{Total Area of Outcomes}}$

Think about it: How does this compare to our counting definition for discrete probabilities? Does it make sense?

Expected Value

Chapter 6.1

Expected Value

The expected value is almost exactly what it sounds like. The expected value results in the average value that is expected if something happens many times. It could be the most likely outcome, or it could be a value that is impossible to achieve.

When rolling a standard, fair 6-sided die, what is the expected value?

Think first: What do you think it is?

The middle value is between 3 and 4 so a good guess might be either 3 or 4, or to split it, 3.5. It turns out that 3.5 is, in fact the answer. We can calculate this by computing a weighted average.

$\frac{1 + 2 + 3 + 4 + 5 + 6}{6} = \frac{21}{6} = \frac{7}{2}$

This works because each option is equally likely. What about our die with three ones, two twos and one three?

For each value, we can multiply it by the probability it happens, which also gives a weighted average. You'll notice this is what we also did in the previous problem, since all values were divided by $6$.

$\frac{1}{2}1 + \frac{1}{3}2 + \frac{1}{6}3 = \frac{1}{2} + \frac{2}{3} + \frac{1}{2} = \frac{5}{3}$

Think about it: Does $\frac{5}{3}$ make sense as an answer here?

In general, the formula for the expected value of discrete probability problems is

$\sum_{x \in S} p(x) \cdot x$

Where $S$ is the sample space, $x$ represents an outcome, and $p(x)$ is the probability of $x$.

This can apply for situations where sets of outcomes and associated probabilities are given.

For example, assume we are told that a college class has 21 20-year olds, 23 21-year olds, 11 22-year olds, and 3 31-year olds. If you choose a person at random, what do you expect their age to be?

$\frac{21}{21+23+11+3}\cdot 20 + \frac{23}{21+23+11+3}\cdot 21 \frac{11}{21+23+11+3}\cdot 22 + \frac{3}{21+23+11+3}\cdot 31$

If we use a calculator, we find this to be about 21.34.

Think about it: Does this answer make sense?

Recursive Games

Expected value can sometimes be calculated for recursive probability problems.

Imagine a game where you roll a die and you recieve the value you roll, except if you roll a 1, in which case you add one to your current value, then roll again.

Think first: Make an estimate of what you think the expected value should be.

The expected value is

$E = \frac{1}{6}2 + \frac{1}{6}3 + \frac{1}{6}4 + \frac{1}{6}5 + \frac{1}{6}6 + \frac{1}{6}(1 + \text{ rolling again })$

Note that when you roll again, the expected value is exactly the same formula, so we can replace "rolling again" with $E$

$E = \frac{2}{6} + \frac{3}{6} + \frac{4}{6} + \frac{5}{6} + \frac{6}{6} + \frac{1}{6}(1 + E)$

$E = \frac{20}{6} + \frac{1}{6}(1 + E)$

$6E = 20 + 1 + E$

$5E = 21$

$E = \frac{21}{5}$

This is a little over $4$, which is not much more than the original expected value for a die roll.

Think about it: Does this make sense?

Continuous Expected Value

As mentioned in the continuous probability section, sums turn into integrals. The same happens with expected values!

Since calculus is not a prerequisite, we won't go into any more detail here.

Probability Functions

Chapter 1 Chapter 2

There are two types of functions to display the probability attributed to each outcome. These display the probabilities as areas, which as we discovered, works well for continuous probability problems.

Probability Mass Function

A Probability Mass Function shows the probability attributed to discrete probability distributions. Each outcome should appear on the x axis, and the bar for each outcome will be the length of the probability of this outcome. For example, the probability mass function for a standard, fair, 6-sided die would be 6 bars (labeled 1 to 6), where each bar starts at zero and ends at $\frac{1}{6}$

Here is a link to a Desmos chart of the Probability Mass Function of the example described above.

Probability Density Function

A Probability Density Function shows the same information, but for a continuous probability problem. Remember that we use area to represent probability, so the probability that a range of values occurs is the area of that region under the curve.

This 3Blue1Brown video does an excellent job diving into the Binomial Distribution, but the ideas in this video about probability density functions apply to any distribution.

Common Distribution Functions

While the Binomial distribution was mentioned in the previous video, the most well known and often-used distribution is the Normal distribution, also known as the Gaussian distribution, or sometimes "the bell curve," which describes a surprising number of situations.

We'll explore the Normal distribution more in the section on Random Variables next module.

Week 6: Self-Guided Problems

When you come to class, be ready to discuss these questions, and bring any additional questions you still have after this exercise!

For the first week only, this Self-Guided exercise is due by Friday. All other Self-Guided Problem Sets will be due before class starts.

Submitting Your Work

Your work must be submitted to Anchor for degree credit and to Gradescope for grading.

For any work completed outside of GitHub or Gradescope:

Typeset your work in LaTeX.

You should use \begin{enumerate} to create a numbered list, and your solutions to each problem should match with the corresponding number on the assignment.
For example, if an assignment has 10 numbered problems, your enumerate should have 10 \item commands, with your solution(s) to problem 1 under the first \item, problem 2 under the second and so on.
If you skip a problem, just leave the \item blank, otherwise the numbers of your solutions will not match the assignment document.

Compile into a PDF. This can be done easily through an Overleaf account, otherwise you will need to install LaTeX.
Submit the pdf to Gradescope via the appropriate submission link for the course.
Upload the pdf to Anchor using the form below.

Note: Anchor submissions can occur at any time during the term, but it is critical that you upload all of your work to Anchor before the last day of the term. Gradescope submissions must be submitted before the deadline (or the late deadline, if applicable).

It is required that all assignments are submitted as a PDF generated from a LaTeX document.

Assignments submitted in any other form will earn zero credit.

Self-Guided Problems cannot be submitted late for any reason

This is due to the fact we discuss them in the class. Be sure to stay on top of these Self-Guided problems, and remember it is better to turn in an incomplete set than an empty one.

ChatGPT/AI

Use of ChatGPT/AI is forbidden for all assignments in this course.

NEW: Forming Groups

You may solve Self-Guided Problem sets in groups of up to 4 people.

Rules for groups:

You must list everyone in your group on the assignment. Leaving off a name counts as academic dishonesty.
Working with another group/working with more than 4 people counts as academic dishonesty.
Homework assignments, exams, and projects are still individual assignments, and any group work on these counts as academic dishonesty.
You must have a table at the start of your problem sets with approximate "effort" percentages. For example, if I work with David, and I think we both contributed equally to the problem set, I would insert a table:

Name	Percent Effort
Kiera Gross	50%
David Walter	50%

If your effort percentage is very low or consistently low, your score may be changed to reflect your effort.

If a group has problems deciding the amount of effort each member should recieve, the group will not be permitted to work together again for an assignment.

Every member of the group must understand the solution to every problem in the Self-Guided Problem set.
All other guidelines still apply to Self-Guided Problem Sets (no use of AI tools, no plagiarism, must be typeset in LaTeX, etc.)

NEW: Assignment Template

Example templates for Self-Guided Problem sets and Homework assignments are available in the shared Overleaf Document, under Templates.

Do not under any circumstances modify the templates in the Shared Overleaf.

There is a list at the bottom of both assignments, meant for citation. If a resource was consulted, it should be linked, and the problem(s) it has been used for should be specified.

As a note: Copying answers word-for-word from any sources is considered plagiarism. This may result in a zero on the problem or a zero on the assignment depending on severity. Any use of ChatGPT or other AI tools will result in a zero on the assignment.

As a general guideline: if you could not do the problem yourself without looking at the resource, you should not be using this resource and should find another way to study.

I would also generally advise against using resources such as Quora, Reddit, etc where people crowdsource answers. People can say many things on the internet, including things that are untrue or misleading. The best resources will always be the readings on Anchor, the textbook, live classes, Discord, and my office hours.

Problems

Prove one of the Identities based in Pascal’s Triangle using:

a. Blockwalking

b. A Combinatorial Proof

c. Algebra

Do not pick an identity that was proven on Anchor.

d. Which method was easiest for this identity? What do you think made it easiest?

Create a 6-sided die where

a. The chances of rolling a one are 2/3.

b. The chances of rolling an even number are 100%.

c. The probability of rolling a 3 is 0%.

d. The probability of the sum of two of your die is 8 is 1/6.

Determine if the following events are independent or dependent. Note that you do not have to solve these problems, just determine if they are independent or dependent.

a. Drawing a red card, then drawing a card labeled k.

b. Drawing a red card, then drawing another red card.

c. Drawing a red card, then rolling a 6 on a standard, fair, 6-sided die.

d. Rolling a 6 on a standard, fair, 6-sided die, then rolling a 1 on the die.

Find the probability of the following events. Assume all dice are standard, fair 6-sided dice.

a. Rolling 2 dice and they are both ones.

b. Rolling a one, then rolling another one.

c. Rolling an even number, then an odd number.

d. Rolling an odd number, then an even number.

e. Rolling an even number, then an even number.

f. Rolling an even number, then a different even number.

Imagine there's a test for a disease that only 2% of people have. The test has a 99% sensitivity rate, and a 95% specificity rate.

a. If a person has a positive result, what is the probability they have the disease?

b. If a person has a negative result, what is the probability they do not have the disease?

Find the expected value of

a. Rolling a standard, fair 8-sided die.

b. The sum of two rolls of a standard, fair, 8-sided die.

c. The sum of four rolls of a standard, fair 8-sided die.

Homework Set 6

Submitting Your Work

Your work must be submitted to Anchor for degree credit and to Gradescope for grading.

For any work completed outside of GitHub or Gradescope:

Typeset your work in LaTeX.

You should use \begin{enumerate} to create a numbered list, and your solutions to each problem should match with the corresponding number on the assignment.
For example, if an assignment has 10 numbered problems, your enumerate should have 10 \item commands, with your solution(s) to problem 1 under the first \item, problem 2 under the second and so on.
If you skip a problem, just leave the \item blank, otherwise the numbers of your solutions will not match the assignment document. Here is an example Overleaf document showcasing this format.

Compile into a PDF. This can be done easily through an Overleaf account, otherwise you will need to install LaTeX.
Submit the pdf to Gradescope via the appropriate submission link for the course.
Upload the pdf to Anchor using the form below.

Note: Anchor submissions can occur at any time during the term, but it is critical that you upload all of your work to Anchor before the last day of the term. Gradescope submissions must be submitted before the deadline (or the late deadline, if applicable).

ChatGPT/AI

Use of ChatGPT/AI is forbidden for all assignments in this course.

It is required that all assignments are submitted as a PDF generated from a LaTeX document.

Assignments submitted in any other form will earn zero credit.

Using a combinatorial proof, show that the sum of the $n$th row in Pascal's triangle is $2^n$
Using a combinatorial proof, show that ${4n \choose 2} = 4 \cdot {n \choose 2} + 6n^2$

Hint: $6 = {4 \choose 2}$ and $n$ can also be written as ${n \choose 1}$

Find the probabilities of the following events:

a. A randomly chosen integer number between 1 and 100 contains a 2.

b. Rolling a sum of 3 on two standard, fair, 6-sided die.

c. Rolling a sum of 3 on three standard, fair 6-sided die.

d. Drawing all 4 letters from our Kibo deck in a hand of 5 cards.

e. A randomly chosen real number chosen between 1 and 10 falls in the range from 2 to 4.

f. A point randomly selected in a square of side length 1 also appears in a circle centered on the square with radius $\frac{1}{2}$.

Imagine there's a test for a disease that only 0.5% of people have. The test has a 99.9% sensitivity rate, and a 99% specificity rate.

a. If a person has a positive result, what is the probability they have the disease?

b. If a person has a negative result, what is the probability they do not have the disease?

Find the expected value of the following events

a. The sum of numbers on 5 cards drawn from our Kibo deck.

b. The sum of numbers on 10 cards drawn from our Kibo deck.

c. The outcome of 4 coin flips where heads add 1 and tails subtract 1.

d. The multiplication of two rolls of a standard, fair 6-sided die.

Draw or graph a probability mass function for the following:

a. The sum of two dice rolls.

b. The results of a single coin flip.

c. The value of a random integer number between 1 and 10.

Statistics, Number Theory

This week, we'll work through a few statistical concepts, then begin discussing basic concepts in Number Theory.

Readings

Chapter 5.2

By the end of the week, you should be able to:

Identify potential values of random variables and solve discrete problems which use random variables.
Compute the mean, median, mode, and range of a group of numbers.
Understand the premise behind central limit theorem and the law of large numbers.
Properly define "prime number" and use notation related to the concept of divisibility.
Find the prime factorization of any number.
Understand why divisibility rules work.
Know the definitions of GCD and LCM, as well as some important properties of GCD and LCM.
Write numbers in new bases, and compute simple arithmetic problems within the base.
Use your knowledge of divisibility rules in base 10 to create new rules in other bases.
Know what a Diophantine equation is, and how to solve simple, one-variable Diophantine equations.

Random Variables

Random Variables are a probabilistic/statisical tool to discuss probability of events, usually continuous probability, but sometimes even discrete random variables can be useful.

Readings

Random Variable Defintion

Introduction to Probability

Random Variables, just like normal variables take the place of a value. In the case of Random Variables, their value is the outcome of an event.

For a die roll, a random variable could hold any integer value between 1 and 6 (inclusive).

For a coin flip, the value would be heads or tails.

When drawing a card, the value might be the numerical value if that's what we're considering. With Random Variables we almost always consider a numerical value.

Unlike normal variables, we usually do not solve for the value of random variables. Instead, we talk about their properties and use them as placeholders for the outcome of an event.

Discrete/Continuous Random Variables

Chapter 1.1 Chapter 2.1

Just like probability problems, Random Variables can be made to reference discrete probabilities or continuous probabilities. For discrete probabilities, like the ones described above, it is easy to say what values a random variable might take on, and how likely it is to take on that value.

For continuous probability problems, this information is often visualized with probability density function. As discussed in the last module, this describes the probabilities over a range of values, which we can calculate by finding the area. Usually this is done with integrals, so we won't be solving any that require integration, but it's useful to know about this method of displaying probability.

Expected Value of RVs

Chapter 6.1

The expected value of a random variable is simply the expected value of the event it is associated with. For example, the expected value of a random variable representing a standard, fair 6-sided die roll would be 3.5, as we've calculated before.

Since random variables are a placeholder, all the calculations we complete with them just reference the event, and the probabilities associated with the event.

Variance

Chapter 6.2

The variance of a probability distribution (or of a random variable) measures how varied the results of the event are or can be. This is measured by squaring the difference between each outcome and the mean, then taking the average of these numbers.

For example, the variance of rolling a standard, fair, 6-sided die is

$Var(X) = [(1 - 3.5)^2 + (2 - 3.5)^2 + (3 - 3.5)^2 + (4 - 3.5)^2 + (5 - 3.5)^2 + (6 - 3.5)^2]/6 \approx 2.92$

The variance of choosing a random integer between 1 and 10 inclusive is $6$.

Think about it: try to calculate this value.

When there are more options, there is more variance. Likewise, when the options are spread out more, there is more variance.

Sums of Random Variables

Chapter 7.1 Chapter 9

Below is a required video that is a part of the readings this week. Feel free to pause, rewind, or take notes as needed.

Think about it: Try computing the 95% bounds for 1,000 die, for 10,000 die, and for 10 die. Combined with the 100 die example from the video, what do you notice?

Statistics

Statistics is the science of probability. Using mathematical methods, we discuss what is or isn't likely to happen based on data, and define some new, helpful terms.

Readings

Mean, Median, Mode, Range

If you are given a list of numbers, and are told these are outcomes from a repeated event, what can you do with them?

Mean

The mean of a set of numbers is simply the average. This tells us some information about the expected value, but does not give much information on its own.

Median

The median of a set of numbers is the middle value, when ranked highest to lowest. Combined with the mean, we can use this to say some things about the distribution of values.

If the median is larger than the mean, that means there must be some very small numbers weighing the mean down.

If the median is smaller than the mean, the opposite must be true: some large values are making the mean larger.

If the mean and median are close to the same number, we can assume a relatively even distribution sometimes. However, we cannot guarantee this.

Mode

The mode of a set of numbers is the most common value. If there are multiple that are just as common, they are all considered modes. The mode, and the number of values that are equal to the mode, can tell us some information as well.

Range

The range of a set of numbers is the difference between the largest and smallest value. This tells us how wide our distribution is (roughly), though it doesn't tell us any information about how values are distributed between these points.

Check your understanding: Go to random.org and flip 10 coins, keeping track of the number of heads that come up in the 10 flips. Do this at least 10 times, recording the numbers, then calculate the mean, median, mode, and range.

Check your answer

I preformed this 20 times, getting the following results:

5, 4, 7, 3, 6, 3, 7, 8, 6, 6, 4, 3, 7, 5, 7, 5, 5, 5, 5, 8

Mean: 5.45

Median: 5

Mode: 5

Range: 5

These were remarkably consistent for me, but see what you find!

Law of Large Numbers

Chapter 8

The Law of Large Numbers is a probability theorem that is very useful for statistics. There's a lot of mathematical terms in this theorem that I don't expect you to fully comprehend, but the big picture is important.

This theorem basically states if you have a process that happens many times (a large number of times), the mean of the values should be equal to the expected value generated probabilistically. Larger numbers should have means that get closer and closer to the expected value.

Think about it: Try using the random.org coin flipper or dice roller 5, 10, 20, and 50 times (you can just do 50 times and use the first 5, 10, 20 values). Find the mean of each of these sets of numbers. How close is each to the true expected value?

Confidence Intervals

Confidence intervals are another statistical tool which provides a range of values that you expect the result of an event to fall between. If this sounds familiar, it should be, as it was in the Central Limit Theorem video!

Confidence intervals are usually 95% or 99% based on the standard deviation of the normal distribution, though other values can be made using integration or specific tables.

These confidence intervals simply state an interval, then the confidence level (percent likelihood) that a new value will fall in this range.

Calculating these is a bit beyond the scope of this course, but there are tons of resources on this topic, and if you'd like to do a project on statistics, this may be a topic you could discuss!

Divisibility

Divisibility is an important concept to Number Theory. We will discuss a few ways of thinking about divisibility here.

Divisibility

There are many terms similar to divisibility that you may already be familiar with:

If $n$ is divisible by $d$, this means:

$d$ is a factor of $n$
$d$ divides $n$
$d | n$ (A symbol, read as "divides")

And if $d \neq 0$,

$n$ is a multiple of $d$.

$n$ is divisible by $d$ if

$\frac{n}{d} = k$ where $k \in \mathbb{Z}$.

Think about it: Why does $d$ need to be non-zero for multiple to the same as divisibility?

If $d$ does not divide $n$, we can express this as

$d \nmid n$

Check your understanding: List all numbers that divide 6. List all numbers that divide 9. List all numbers that divide 11.

Check your answer

For $6$: $-6, -3, -2, -1, 1, 2, 3, 6$

For $9$: $-9, -3, -1, 1, 3, 9$

For $11$: $-11, -1, 1, 11$

Check your understanding: There is a specific term for numbers that are divisible by 2. What is it?

Check your answer

Even!

Quotient-Remainder Form / Division Algorithm

Chapter 2.1

From the previous example, we know $4$ does not divide 6. We can write these numbers in quotient-remainder form as follows:

$6 = 4 \cdot 1 + 2$

Where $2$ is the remaining amount (remainder) left over when we have divided 6 by 4 as much as we can.

In this case, 1 is the quotient, and 4 is sometimes known as the dividend.

In any case, there is a theorem that tells us the following:

For any integers $n$ and $d$, there are unique integers $q$ and $r$, with $0 \leq r < n$ such that

$n = d\cdot q + r$.

Check your understanding: What are $q$ and $r$ for $n=13$, $d=6$? What about $n=13$, $d=-6$? What about $n=-13$, $d=6$?

Check your answer

$13 = 6 \cdot 2 + 1$

$13 = -6 \cdot -2 + 1$

$-13 = 6 \cdot -3 + 5$

Quotient-Remainder form can be useful for future topics, so keep this in mind.

Divisibility of Large Numbers

If a number is divisible by 10, can you say any other numbers it might be divisible by?

Since 10 is divisible by 2 and 5, we can use this to say any number divisible by 10 is also divisible by 2 and 5!

This is simple to see:

$n = 10k = 5 \cdot 2k = 5(2k)$ which is a multiple of $5$!

If a number is divisible by a number, k, it is also divisible by any factors of k.

We can also use this the other way around:

If a number is divisible by $2$ and $5$, then it is divisible by $10$.

We have to be careful, though.

Think about it: Can you think of three numbers where this doesn't work? Hint: $3$, $6$, and $18$ is an example.

Primes and Prime Factorization

Primes are incredibly important for a number of reasons, so let's be sure to get the definition right.

Prime Numbers

Many people will naively define primes as "A number which is divisible by 1 and itself" or as "A number which is divisible by two numbers."

These definitions both fail to correctly define a prime number.

Think first: Can you find the problems with these?

Think of your favorite prime number. By our definition in the last section, what are its divisors?

You should find 4 numbers: $1$, $p$, $-1$, and $-p$ where $p$ is your prime number.

A more acceptable definition of prime is to say "a number which is divisible by exactly 2 positive integers."

An even better definition allows us to see the usefulness of primes.

A composite number is a number that is not prime. This means it should have some divisor, other than 1, that is strictly less than the number.

For example, $6 = 3 \cdot 2$ where $3$ and $2$ are both strictly less than 6.

This is often how composite numbers are defined in the world of Number Theory.

A composite number is an integer greater than 1 which can be written as a product of two strictly smaller positive integers.

Then we can define a prime as follows:

A prime number is an integer greater than 1 which cannot be written as a product of two strictly smaller positive integers.

We consider primes and composites only amongst the positive integers, excluding $1$. We will see why $1$ cannot fit in either category later on, but for now know that $1$ is neither prime nor composite, just like zero is neither positive nor negative.

Prime Factorization

Take your favorite composite number and break it down into factors. Keep breaking it down until you can no longer do so. You should end up with a multiplication of prime numbers. This is the basic idea behind prime factorization.

$400 = 40 \cdot 10 = 4 \cdot 10 \cdot 2 \cdot 5 = 2 \cdot 2 \cdot 2 \cdot 5 \cdot 2 \cdot 5 = 2^4 \cdot 5^2$

A number $n$ can be written in the form

$n = p_1^{x_1}\cdot p_2^{x_2} \cdot p_3^{x_3} \cdot ... \cdot p_n^{x_n}$

Where $p_i$ are all distinct prime numbers, written in order from smallest to largest, and $x_i$ are positive integer exponents.

In fact, we can say something stronger

The Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic states that any positive integer $n$ has a unique prime factorization of the form described above.

Check your understanding: Can you see now why $1$ cannot be prime nor composite?

Check your answer

$1$ obviously cannot be composite, as it cannot be expressed as a product of strictly smaller positive integers.

However, if $1$ was prime, we could create infinitely many prime factorizations for any number!

$400 = 2^4 \cdot 5^2 = 1^1 \cdot 2^4 \cdot 5^2 = 1^2 \cdot 2^4 \cdot 5^2 = ...$

Infinitely Many Primes

As the values of numbers increase, primes seem to be less and less common. However, we can prove that there are infinitely many prime numbers.

Proof.

Assume there are only finitely many primes. Let $P$ be the product of all primes.

Consider the number $P+1$.

$P+1$ is not divisible by any prime (it would leave remainder 1).

Therefore, $P+1$ is not composite, as it cannot be written as a product of strictly smaller positive integers.

However, $P+1$ is larger than all primes, and therefore cannot be any of our finite primes.

Contradiction: This means there is a number that is both not prime and not composite. All numbers greater than 1 are either prime or composite.

Therefore, there cannot be finitely many primes.

QED.

GCD and LCM

GCD and LCM are related concepts that are important in Number Theory. We'll revisit these concepts when we discuss the Euclidean Algorithm next week.

GCD

GCD stands for Greatest Common Divisor, and evaluates to the largest divisor two numbers have in common, as the name suggests.

$GCD(10, 20) = 10$

$GCD(10, 15) = 5$

$GCD(10, 13) = 1$

Since $1$ is a divisor of all numbers, the minimum a GCD can be is $1$.

Note also that

$k \cdot GCD(a, b) = GCD(k \cdot a, k \cdot b)$

So,

$GCD(10, 20) = 10 \cdot GCD(1, 2) = 10 \cdot 1 = 10$

GCD From Prime Factorizations

Given two prime factorizations, can you find the GCD?

$n_1 = 2^3 3^2 5^2 7^1$

$n_2 = 2^4 3^1 5^3$

Think first: What divides both?

We can see that $2$, and even all the way up to $2^3$ divides both numbers. Unfortunately, $2^4$ only divides one, so we can't go that high. Likewise, $3^1$ and $5^2$ go into both numbers. If I assemble these into one number:

$2^3 3^1 5^2$

This is the GCD!

In general, we can find the GCD of two numbers by looking for the lowest exponent in each prime factorization.

LCM

The LCM stands for Least Common Multiple, and is the lowest integer that is a multiple of two numbers.

$LCM(10, 20) = 20$

$LCM(10, 15) = 30$

$LCM(10, 13) = 130$

Since the multiplication of two numbers is a multiple of both, the maximum LCM is the product of the two values.

$k \cdot LCM(a, b) = LCM(k \cdot a, k \cdot b)$

So,

$LCM(10, 20) = 10 \cdot LCM(1, 2) = 10 \cdot 2 = 20$

LCM From Prime Factorizations

Given two prime factorizations, can you find the LCM?

$n_1 = 2^3 3^2 5^2 7^1$

$n_2 = 2^4 3^1 5^3$

Think first: What would be a multiple of both numbers?

We can see that if we include $2^4$, then both numbers will be a divisor, at least in terms of $2$s. If we select fewer $2$s, then $n_2$ will not be a divisor. More $2$s are not needed.

Likewise, we can take $3^2$, $5^3$ and $7^1$ to cover both numbers.

$2^4 3^2 5^3 7^1$

This is the LCM!

In general, we can find the GCD of two numbers by looking for the highest exponent in each prime factorization.

Relationship Between GCD and LCM

Think first: If GCD takes the highest exponents and LCM takes the lowest, what is the relationship between the GCD, LCM, and the two numbers?

For two numbers, $a$ and $b$,

$a \cdot b = GCD(a,b) \cdot LCM(a,b)$

Since the GCD captures all the higher exponents, and LCM captures the lower exponents, between the two of them, all exponents are there!

This can be very helpful in solving problems quickly. If you can find the GCD easily, to find the LCM, you just need to compute $\frac{a \cdot b}{GCD(a,b)}$

GCD and LCM of 3 or More Numbers

GCD and LCM can be defined on more than two numbers, this just doesn't allow us the nice relationship we just described. We will be working only with GCD and LCM on two numbers.

Divisibility Rules

Many people already know some of these divisibility rules, but identifying where they start can help in creating new rules or memorizing other known rules.

Divisibility by 2

Many of us can look at a number and immediately determine if it is even. We just look at the last digit: if this is even, then the whole number is even.

We tend to take this as a fact, not thinking about why it works. Looking at place values can help us figure this out.

We think in base ten, so for any number, we can represent it as a sum of values multiplied by powers of 10.

$54398 = 5 \cdot 10^4 + 4 \cdot 10^3 + 3 \cdot 10^2 + 9 \cdot 10^1 + 8 \cdot 10^0$

Look closely at this statement. All values except for the last digit are divisible by $10$. This means they must also be divisible by $2$! The only value we need to check is the last digit. If it's even, everything is even, if it's odd, we'll have an odd value.

Divisibility by 4

There is a less commonly known rule for divisibility by 4: looking at the last two digits.

Think first: Based on what we did above, can you figure out how this rule works?

$54328 = 5 \cdot 10^4 + 4 \cdot 10^3 + 3 \cdot 10^2 + 2 \cdot 10^1 + 8 \cdot 10^0$

Notice that $10^2 = 100$ is divisible by 4! So all digits except the tens and ones are divisible by 4, therefore, we look at those last two!

Think about it: Can you come up with a rule for divisibility by 8?

Divisibility by 5

Because $10$ is divisible by $5$ along with $2$, we have a similar rule for divisibility by 5: look at the last digit.

Think about it: Can you come up with a rule for divisibility by 25? What about 125?

Divisibility by 9

There's a somewhat-known rule for divisibility by 9 or 3. Let's see if we can start from our place values first, then reach the rule.

We know a number can be expressed in terms of 10, but we want 9 instead, so let's try doing $9 + 1$ wherever we see a 10

$54324 = 5 \cdot 10^4 + 4 \cdot 10^3 + 3 \cdot 10^2 + 2 \cdot 10^1 + 4 \cdot 10^0 = 5 \cdot (9 + 1)^4 + 4 \cdot (9 + 1)^3 + 3 \cdot (9 + 1)^2 + 2 \cdot (9 + 1)^1 + 4 \cdot (9 + 1)^0$

Note that for the expansions of all of these, every term will have some power of $9$ except for the $1^n$ term.

Therefore, each expanded term is divisible by $9$ except for that last $1$. This means, we're really just considering each digit since $1$ times any number is itself.

$5 + 4 + 3 + 2 + 4 = 18$

Since the sum of the digits is divisible by $9$, we can say the whole number is!

Divisibility by 3

Since $9$ is divisible by $3$, the same rules and steps apply, just that the sum of the digits needs to be divisible by $3$ instead of $9$.

Divisibility by 11

Think about it: Can you come up with a divisibility rule for 11s? Hint: Remember we had 9 + 1 = 10? What happens if you say 11 - 1 = 10? Be careful of the negative and what happens in the expansion.

Different-Based Number Systems

We discuss numbers most often in base-10, but other bases can sometimes be useful.

Exploding Dots

Please complete explorations 1-5 on the exploding dots website. Note that there is no interactive web app (right now), but the videos should explain the idea.

Mathematical Definition

A number is expressed in base $b$ if it is written as

$(d_n d_{n-1} d_{n-2} ... d_2 d_1 d_0)_b$

Where $d_i$ are digits from 0 to $b-1$, and the number can be expressed as

$d_n \cdot b^n + d_{n-1} \cdot b^{n-1} + d_{n-1} \cdot b^{n-1} + ... + d_2 \cdot b^2 + d_1 \cdot b^1 + d_0 \cdot b^0$

For example, a base-2 number is always expressed using 1s and 0s, and 17 would be expressed as

$10001_2$ since $17 = 1 \cdot 2^4 + 0 \cdot 2^3 + 0 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0$

Think about it: How does this all tie into exploding dots?

Divisibility Rules in Different Bases

Just like we have divisibility rules in base 10, we can have rules in any base.

Divisors of the Base

If a number divides the base, this is similar to our divisibility by 2 and 5 rules in base-10.

Just look at the last digit!

$101_2$ is not divisible by $2$ since it ends in a $1$

$3F94_{16}$ is divisible by $2$ and $4$, but not $8$ or $16$ since it ends in a $4$.

$A3B5_{15}$ is divisible by $5$ since it ends in a $5$, but it is not divisible by $3$ since its last digit is $5$ (not divisible by 3).

Check your understanding: Use a random number generator to generate a number between 2 and 10, then generate another number between 1 and 10,000. Using the first number as the base, can you determine if the second number has any easy-to-find divisors?

Check your answer

Answers here will depend largely on the numbers generated, but use this for practice, and double check by converting the number back into base $10$ and using a calculator.

Base - 1

We were able to determine a rule for divisibility by $9$ in base $10$. We can similarly find that for any base $b$, a number is divisible by $b-1$ if the digits (in that base) sum to a number that is divisible by $b-1$.

For example:

$2433_7$

$2 + 4 + 3 + 3 = 12$

This number is divisible by 6!

In fact, if we convert it,

$2 \cdot 7^3 + 4 \cdot 7^2 + 3 \cdot 7^1 + 3 \cdot 7^0 = 906$

$906$ is divisible by $2$ and $3$, therefore it is divisible by $6$!

So, $2433_7$ is divisible by $6$

Check your understanding: Use a random number generator to generate a number between 2 and 10, then generate another number between 1 and 10,000. Using the first number as the base, can you determine if the second number is divisible by the base minus $1$?

Check your answer

Answers here will depend largely on the numbers generated, but use this for practice, and double check by converting the number back into base $10$ and using a calculator.

Base + 1

Think about it: Can you come up with a divisibility rule for the base plus 1? Hint: divisibility by 11 would be an example here. What would happen in general?

Multiplication in Different Bases

We know that 10 times any number in base 10 just moves all the digits one place value.

Think about it: What happens if I multiply any number by $(10)_b$? Hint: Remember that this is just $b$ itself.

Diophantine Equations

One Variable

Diophantine Equations are equations where we look for integer solutions only. Watch the following video on one-variable Diophantine Equations:

Multiple Variables

Diophantine equations are important, since we need to consider one for a specific theorem.

If $a$ and $b$ are integers, then

$ax + by = GCD(a, b)$

Has integer solutions for $x$ and $y$

We'll cover how to solve this problem in the next module, but for now, try to think about it yourself.

Think about it: How might you solve for integer x and y? Hint: The quotient-remainder theorem can be very helpful here.

Week 7: Self-Guided Problems

When you come to class, be ready to discuss these questions, and bring any additional questions you still have after this exercise!

For the first week only, this Self-Guided exercise is due by Friday. All other Self-Guided Problem Sets will be due before class starts.

Submitting Your Work

Your work must be submitted to Anchor for degree credit and to Gradescope for grading.

For any work completed outside of GitHub or Gradescope:

Typeset your work in LaTeX.

You should use \begin{enumerate} to create a numbered list, and your solutions to each problem should match with the corresponding number on the assignment.
For example, if an assignment has 10 numbered problems, your enumerate should have 10 \item commands, with your solution(s) to problem 1 under the first \item, problem 2 under the second and so on.
If you skip a problem, just leave the \item blank, otherwise the numbers of your solutions will not match the assignment document.

Compile into a PDF. This can be done easily through an Overleaf account, otherwise you will need to install LaTeX.
Submit the pdf to Gradescope via the appropriate submission link for the course.
Upload the pdf to Anchor using the form below.

Note: Anchor submissions can occur at any time during the term, but it is critical that you upload all of your work to Anchor before the last day of the term. Gradescope submissions must be submitted before the deadline (or the late deadline, if applicable).

It is required that all assignments are submitted as a PDF generated from a LaTeX document.

Assignments submitted in any other form will earn zero credit.

Self-Guided Problems cannot be submitted late for any reason

This is due to the fact we discuss them in the class. Be sure to stay on top of these Self-Guided problems, and remember it is better to turn in an incomplete set than an empty one.

ChatGPT/AI

Use of ChatGPT/AI is forbidden for all assignments in this course.

Forming Groups

You may solve Self-Guided Problem sets in groups of up to 4 people.

Rules for groups:

You must list everyone in your group on the assignment. Leaving off a name counts as academic dishonesty.
Working with another group/working with more than 4 people counts as academic dishonesty.
Homework assignments, exams, and projects are still individual assignments, and any group work on these counts as academic dishonesty.
You must have a table at the start of your problem sets with approximate "effort" percentages. For example, if I work with David, and I think we both contributed equally to the problem set, I would insert a table:

Name	Percent Effort
Kiera Gross	50%
David Walter	50%

If your effort percentage is very low or consistently low, your score may be changed to reflect your effort.

If a group has problems deciding the amount of effort each member should recieve, the group will not be permitted to work together again for an assignment.

Every member of the group must understand the solution to every problem in the Self-Guided Problem set.
All other guidelines still apply to Self-Guided Problem Sets (no use of AI tools, no plagiarism, must be typeset in LaTeX, etc.)

Assignment Template

Example templates for Self-Guided Problem sets and Homework assignments are available in the shared Overleaf Document, under Templates.

Do not under any circumstances modify the templates in the Shared Overleaf.

There is a list at the bottom of both assignments, meant for citation. If a resource was consulted, it should be linked, and the problem(s) it has been used for should be specified.

As a general guideline: if you could not do the problem yourself without looking at the resource, you should not be using this resource and should find another way to study.

Problems

Find the mean, median, mode, and range of the following set of numbers. Does the distribution look familiar?

5, 5, 2, 2, 1, 5, 6, 1, 5, 2, 1, 3, 1, 4, 5, 1, 2, 1, 2, 2, 4, 4, 2, 1, 4, 1, 5, 3, 3, 1, 6, 6, 6, 6, 6, 6, 5, 5, 6, 4, 5, 5, 3, 5, 5, 6, 2, 3, 4, 5, 1, 1, 5, 6, 6, 1, 3, 2, 3, 6, 5, 1, 1, 3, 3, 5, 5, 3, 1, 4, 3, 1, 1, 6, 5, 2, 6, 5, 4, 6, 5, 5, 4, 1, 4, 1, 4, 4, 3, 2, 3, 3, 2, 2, 1, 6, 3, 5, 2, 6

Find the prime factorization of the following integers

a. 96

b. 1,575

c. 182

d. 385

e. 697
Find the GCD and LCM of these pairs

a. 16 and 28

b. 60 and 156

c. 455 and 78

d. 97 and 771
Multiply $10101_2$ and $101_2$ two different ways:

a. By converting to base ten, multiplying, then converting to base 2.

b. By multiplying the numbers in base 2.

c. Which way was easier?
Find a divisibility rule for numbers divisible by 7 in base 8.
Find a divisibility rule for 11 in base 10. Show that it works using place values.

Homework Set 7

Submitting Your Work

Your work must be submitted to Anchor for degree credit and to Gradescope for grading.

For any work completed outside of GitHub or Gradescope:

Typeset your work in LaTeX.

You should use \begin{enumerate} to create a numbered list, and your solutions to each problem should match with the corresponding number on the assignment.
For example, if an assignment has 10 numbered problems, your enumerate should have 10 \item commands, with your solution(s) to problem 1 under the first \item, problem 2 under the second and so on.
If you skip a problem, just leave the \item blank, otherwise the numbers of your solutions will not match the assignment document. Here is an example Overleaf document showcasing this format.

Compile into a PDF. This can be done easily through an Overleaf account, otherwise you will need to install LaTeX.
Submit the pdf to Gradescope via the appropriate submission link for the course.
Upload the pdf to Anchor using the form below.

Note: Anchor submissions can occur at any time during the term, but it is critical that you upload all of your work to Anchor before the last day of the term. Gradescope submissions must be submitted before the deadline (or the late deadline, if applicable).

ChatGPT/AI

Use of ChatGPT/AI is forbidden for all assignments in this course.

It is required that all assignments are submitted as a PDF generated from a LaTeX document.

Assignments submitted in any other form will earn zero credit.

Problems

Assume $X$ is a random variable representing the outcome of rolling a standard, fair 10-sided die. a. What are all the possible values $X$ could hold?

b. What is the expected value of $X$ ($E[X]$)?

c. What is the variance of $X$?

d. What is $P(X < 6)$?

e. What is $P(X < 11)$?

f. What is $P(X = E[X])$?
Find the mean, median, mode, and range of the following set of numbers. Does the distribution look familiar?

7, 5, 6, 7, 6, 2, 4, 3, 5, 2, 7, 5, 9, 9, 7, 12, 5, 5, 9, 8, 9, 4, 7, 10, 7, 3, 8, 9, 5, 4, 7, 7, 2, 11, 8, 5, 9, 8, 8, 11, 3, 6, 4, 7, 8, 8, 12, 6, 5, 7

Write a function to calculate the mean of a list of numbers, and a function that would calculate the median of a set of numbers. Feel free to use this function to determine the answers to problem 1.
Find the prime factorization of the following numbers a. 456

b. 2024

c. 2970

d. 8910

e. 2197.
Compute the following: a. $501_8$ + $427_8$

b. $324_7$ + $324_7$

c. $412_7$ - $362_7$

d. $324_7 \cdot 2_7$

e. $324_7 \cdot 10_7$.
Find a divisibility rule for numbers divisible by 6 in

a. Base 5

b. Base 6

c. Base 7

Project Proposal

Details on the Proposal are in the Project Document on Overleaf.

The basic requirements:

Give a one to three sentence summary of your chosen topic.
Provide a bulleted list of the sub-topics you will cover.
Provide a source for each sub-topic that you will get information from.
Sources may be from Wikipedia or MathStackExchange, but at least two must be textbooks or research papers.
Using Quora, Reddit, or other blog/social media websites are not generally acceptable as sources.

An example would be:

For my project, I intend to explore a few different ways to select random points from a circle, and some common mistakes people make when selecting random points from a circle.

My main points will be:

Number Theory II

This week, we'll continue discussing topics related to Number Theory, diving deep into Modular Arithmetic and solving Linear Congruences.

Readings

Chapter 2.3 Chapter 4 Chapter 5 Chapter 8.5

By the end of the week, you should be able to:

Identify problems that may be related to modular arithmetic.
Solve one-variable linear congruences.
Solve simple multi-variable linear congruences.
Apply the Euclidean Algorithm and the Extended Euclidean Algorithm.
Remember useful theorems regarding modular arithmetic and prime numbers.

Modulo

You are likely already familiar with the idea of mods, but let's make sure you know all of the ways we can define mod!

Readings

What is a mod?

The first definition we often hear for modulo is that two numbers are the same mod n if they both have the same remainder when divided by n.

This definition serves us well, but doesn't express the nature of modulo nor help us identify when it might be useful.

Suppose I ask you what day of the week your birthday will be on next year? What about in 10 years? What was the day of the week the day you were born?

If you've got a calendar, you can easily find your birthday this year, and it may even be easy to find the day of the week next year, but past that would take a lot of scrolling or future calendars.

Instead, we can recognize the year is a cycle of 365 days, and every 7 days the day of the week repeats.

The number of days until your next birthday will be 365 (most of the time), then we can explore how many weeks will occur in between. When we find out the number of days left over, we can find the day of the week.

This problem can be easily solved through modular arithmetic. Take the number of days until your next birthday, and divide by 7. If you get a remainder 0, it should be the same day you started on! Remainder 1 will be the next day, 2 will be two days after, and so on until a remainder 6 gives you 6 days later, and allows us to easily think about negative remainders.

The day that is 6 days after Monday is Sunday, but it's easier to describe this day as yesterday. This is one step back, or a negative $1$, meaning

$6 \equiv -1 \mod{7}$

Modulo can be used to solve many problems that are related to cycles, even ones which are not necessarily numeric, like days of the week.

Modulo

Two numbers, a and b, are considered equivalent modulo n when certain criteria are met. We also sometimes call this a "congruence" modulo n. The below video shows a few different ways we can define what modulo means.

To be clear: This relationship is symmetric, meaning all the rules written still apply when $a$ is swapped with $b$, for example:

$10$ and $14$ still obviously have the same remainder.

$14 = 4 \cdot 1 + 10$

$4 | (14 - 10)$

But let's discuss each of these definitions a little more.

Remainder Definition

While we referenced this definition at the very start, we should discuss it more mathematically.

Similarly to the second rule, we can remember our quotient-remainder form and know that if $a \equiv b \mod{n}$, then

$a = k \cdot n + r$

$b = j \cdot n + r$

Where $k, j, r$ are integers, and in particular, $0 \leq r < n$ since $r$ is a remainder.

This allows us to create that second defintion, with a little algebra manipulation.

$a = (k-j)n + b$

Think about it: Verify that this definition works from the equations above.

Difference Definition

This definition is commonly used in proofs, because it can be helpful to know what things divide rather than their remainders.

We can also get this definition from the quotient-remainder form:

$a - b = k \cdot n + r - (j \cdot n + r) = k \cdot n - j \cdot n + r - r = (k-j)\cdot n$

When subtracted, the remainder cancels, leaving a result that is divisible by $n$.

Addition in Modulo

This video also touches on adding something to both sides. We'll cover this topic more thouroughly in the next section.

Residues

While we can have any number in a modulus, sometimes we like to reduce that number to its remainder. This is called the residue of a number, mod $n$.

The residue of $10 \mod{4}$ is $2$, and the residue of $14 \mod{4}$ is also $2$, which is why they are equivalent.

Modular Arithmetic

It's important to understand how we can manipulate modular equivalences while keeping the equivalence. We have similar rules to algebra, with a few notable differences.

Readings