# Math Prerequisities

The course assumes fluency with all of the math below. These concepts, results, and methods will be used without explanation. If you’ve forgotten some of it, please review the relevant materials. The more confident you are with this math content, the faster you will be able to grasp the material of the course.

Please do the exercises. They are based on calculations that come up frequently.

Being able to assess your own work is an important mathematical skill and will be crucial in this course. If your answer to an exercise below doesn’t match the one provided, or if you can’t get started on an exercise,

• don’t ask for a detailed solution.
• Remember that this is prereq material: you could do this stuff once upon a time. Maybe go back to your own previous class notes if you have them, or review the summaries here again, and examine your answer.
• Which results did you use, and why?
• Did you try a simpler version of the problem for which you can check your answer long-hand, for example by writing out all possibilities?
• Did you draw a diagram?
• Is your answer too big, or too small? Try to figure out which one, as it can help point out your error. If you can compare the question with another related one, that also can sometimes help explain the difference.
• After going through the above, try the exercise again a couple of times.
• If it still doesn’t work out, post on Piazza explaining the reasoning that you used and which of the above steps you took to troubleshoot.

## Chapters 1-9, 12-14

### Basic Counting

The number of finite sequences and subsets that can be created out of a finite set of objects:

Notice the distinction between sequences (orderings, or “arrangements in a line”) and subsets (unordered collections). You have to decide which is appropriate, by looking carefully at the context. In some probability calculations it won’t matter which you decide to use, as long as you are consistent in the numerator and denominator of your proportions.

Exercise BC1: How many different ways are there to arrange six people

a) in a row?

b) in a circle?

b) 120

Exercise BC2: A committee consists of six women and four men. How many different choices can be made if you want to select

a) a Chairperson and an Assistant Chairperson?

b) a subcommittee of two people?

c) a subcommittee of three men and three women?

b) 45
c) 80

### Sums

Summation notation will be used throughout the term. For Chapters 1-7 you just need the following.

Review: Terrific notes by Prof. James Aspnes of Yale’s CS department

“Sigma notation” is simply a compact way of making “…” precise when you are adding a bunch of terms. You’ve known the properties of sums since you started addition and multiplication in elementary school. The notation allows you to express those calculations concisely and precisely when the number of terms is large or when the terms being added are themselves functions.

• Review the definition in the first sentence of the notes.
• Then go to Section 1.4 which has standard notation that we will use.
• You should understand (not just memorize) the first two sums in Section 2.1 on Page 5, and the first two identities in Section 2.2 on Page 6. There’s a typo in the second one. It should read
$\sum_{i \in S} (x_i + y_i) ~ = ~ \sum_{i \in S} x_i + \sum_{i \in S} y_i.$
• Section 2.3 has excellent advice.
• In Chapter 4 of the textbook you’ll start working with double sums. The main idea is in Section 1.7 on Pages 4-5 of the Prof. Aspnes notes linked above; note the analogy with nested for loops. Useful properties are in the latter half of Section 2.2.

Exercise S1: Consider the sequence defined by $$c_i =i$$, for $$i=1, 2, \ldots , 10$$. If possible, find $$\sum_{k=1}^{10} c_k$$. If this is not possible, explain why not.

Exercise S2: Does the expression $$\sum_{n=1}^{10} 2$$ make sense? If it does, what is its value?

Exercise S3: Let $$\{c\}$$ and $$\{d\}$$ be sequences of real numbers so that

$\sum_{i=1}^{100} c_i ~=~ 10 ~~~~\mbox{and} ~~~~~ \sum_{j=1}^{100} d_j ~=~ 20.$

a) Find the value of $$\displaystyle \sum_{i=1}^{100} (4c_i + 5)$$.

b) Find the value of $$\displaystyle \sum_{i=1}^{100} 4c_i ~+~ 5$$.

c) Find the value of $$\displaystyle \sum_{i=1}^{100} (4c_i - d_i + 5)$$.

d) True or false:

$\sum_{i=1}^{100} \sum_{j=1}^{100} (c_i + d_j) ~~=~~ \sum_{i=1}^{100} (c_i + d_i).$

If the identity is true, find the common value of the two sides. If it is false, find the values of the two sides.

b) 45
c) 520
d) False: $$\displaystyle \sum_{i=1}^{100} \sum_{j=1}^{100} (c_i + d_j)= 3000 \neq 30 = \sum_{i=1}^{100} (c_i + d_i)$$

Exercise S4: Fill in the blanks:

$\sum_{i=1}^n \sum_{j=i}^n a_{ij} ~ = ~ \sum_{j = \underline{~~~}}^{\underline{~~~}} \sum_{i = \underline{~~~}}^{\underline{~~~}} a_{ij}.$

[Hint: It might help to draw a grid of all $$(i,j)$$ pairs for some small value of $$n$$.]

Answer S4 $$\displaystyle \sum_{j = 1}^n \sum_{i = 1}^j a_{ij}$$

### Induction

Mathematical induction is a method that is sometimes helpful for proving math statements if:

• You have a guessed a math statement for each positive integer $$n$$, where the $$n$$th statement depends on $$n$$, and
• for small $$n$$ (even just $$n=1$$) you can easily show that the statement is true.

Review: A clear set of notes from Tom Davis of the Berkeley Math Circle

• Just go through Pages 1 and 2

The method is always the same.

• Prove the base case.
• Assume the induction hypothesis. That is, assume that the statement is true for a generic integer $$n$$.
• Write the statement for $$n+1$$. This is what you have to prove.
• [This is where the bulk of the work comes in.] Somehow write the statement for $$n+1$$ in terms of the statement for $$n$$ (assumed to be true) and the base case (which you have proved), in such a way that a little algebraic or other mathematical messing around show that the statement for $$n+1$$ is true.

Exercise I1: Show by induction that for each positive integer $$n$$,

$\sum_{i=1}^n i ~ = ~ \frac{n(n+1)}{2}.$
Answer I1 The key step is $$\displaystyle \sum_{i=1}^{n+1} i = \sum_{i=1}^n i + (n+1)$$.

Exercise I2: Apply I1 (no induction necessary) to find

$\sum_{i=0}^{n-1} i.$

This is the form in which the result first appears in the course, in Chapter 1 of the textbook.

Exercise I3: Use I1 and properties of sums (no induction necessary) to find a simple expression for the sum of the first $$n$$ odd integers:

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

Exercise I4: As a check, use induction to prove the formula you got in I3.

### The Exponential and Log Functions

NOTE: All $$\log$$s in this class, and in almost all of math, are natural logarithms taken to the base $$e$$.

You know that $$\log(1) = 0$$. What we’re going to need, quite often, is an approximation for the log of a number that is very close to 1. A crude approximation is 0 because the number is close to 1. But we’ll use a finer approximation based on the first couple of terms in a related Taylor expansion.

Review: Graphs and Relevant Properties. For now, you need the Limits and Approximations section but not the Bounds. Preferably, you should understand the approximations in relation to the graphs of $$e^x$$ and $$\log(x)$$.

• In Chapter 1 you’ll need the approximations.
• Starting with Chapter 6 you’ll need the Taylor expansion of $$e^x$$.

Exercise EL1: About how big is

a) $$\log(1.01)$$?

b) $$\log(0.99)$$?

Answer EL1 a) $$0.01$$
b) $$-0.01$$

Exercise EL2: Suppose $$0 < p_n < 1$$ for all $$n$$, $$\lim_{n \to \infty} p_n = 0$$, and $$\lim_{n \to \infty} np_n = \mu$$ for some number $$\mu > 0$$. Find $$\lim_{n \to \infty} (1 - p_n)^n$$.

[Hint: Start by considering the $$\log$$ of $$(1 - p_n)^n$$. Approximate it for large $$n$$, and then invert.]

Answer EL2 $$e^{-\mu}$$

Exercise EL3: In EL2, $$1 - p_n \to 1$$ as $$n \to \infty$$, and $$1^n = 1$$ for all $$n$$. So why isn’t it true that $$(1 - p_n)^n \to 1$$ as $$n \to \infty$$?

Answer EL3 For a fixed power $$m$$, it's true that $$(1 - p_n)^m \to 1$$ as $$n \to \infty$$. But in the expression $$(1 - p_n)^n$$ the power $$n$$ isn't fixed. It's going to infinity. So the sequence $$(1-p_n)^n$$ is pulled in opposite directions: $$1-p_n$$ is heading for its upper limit of 1, but it's always less than 1 and so raising it to an increasing power $$n$$ keeps pulling it downwards.

Exercise EL4: Computers can’t do infinite sums (though they can get close numerically, and some symbolic math systems can handle many infinite sums). Find simple expressions for the following sums.

a) $$\displaystyle \sum_{n=0}^{\infty} \frac{1}{n!}$$

b) $$\displaystyle \sum_{i=0}^{\infty} \frac{2^{3i}}{i!}$$

c) $$\displaystyle \sum_{k=2}^{\infty} \frac{3^k}{k!}$$

d) $$\displaystyle \sum_{i=0}^\infty \frac{2^i}{(i+1)!}$$

Answer EL4 a) $$e$$
b) $$e^8$$
c) $$e^3 - 4$$
d) $$\frac{1}{2}(e^2 - 1)$$

### Geometric Series

We’ll use the infinite series more frequently than the finite one, starting in Chapter 8 of the textbook. In fact the infinite series is easier to sum (provided you assume it’s finite, which it’s fine for you to do), and then you can derive the finite series sum from the infinite one, as in the notes linked below.

Review: The main results on Page 6 (Section 2.1) of Prof. Aspnes notes. Understand the derivation of the infinite sum. That way you’ll never have to memorize the results.

Exercise GS1: Let $$0 < p < 1$$. Let $$\displaystyle S = \sum_{i=0}^{\infty} p^i$$.

a) Find $$S$$.

b) Replace the $$?$$ with the appropriate factor: $$\displaystyle \sum_{i=3}^{\infty} p^i = ? \cdot S$$. Hence find $$\displaystyle \sum_{i=3}^{\infty} p^i$$.

c) Find $$\displaystyle \sum_{i=0}^{\infty} p^{3i}$$.

Answer GS1 a) $$\dfrac{1}{1-p}$$
b) The factor is $$p^3$$ so the sum is $$\dfrac{p^3}{1-p}$$
c) $$\dfrac{1}{1-p^3}$$

## Chapters 10-11

### Basic Matrix Operations

That’s all we’ll need for these two chapters. Linear algebra will be used more significantly towards the end of the course.

By the time you get to Chapter 10 you will have realized that probability is all about weighted averages. Matrix representation gives us a compact and powerful way to work with these. For example, suppose $$\mathbf{x} = x_1, x_2, \ldots, x_n$$ is a list of numbers and $$\mathbf{w} = w_1, w_2, \ldots, w_n$$ is a list of weights that add up to $$1$$. Then the dot product $$\mathbf{w\cdot x}$$ is the weighted average of $$\mathbf{x}$$ using $$\mathbf{w}$$ as the weights.

Review: It is important to visualize the sizes and shapes of the vectors and matrices involved. Prof. Semyon Dyatlov of MIT has a nice summary of the basic matrix operations, which I believe was written when he taught Math 54 as a graduate student at Berkeley. Notice that he starts with just the sizes, before going into the algebra.

Exercise MO1: Let $$\mathbf{A}$$ be $$n \times m$$ and let $$\mathbf{v}$$ be a vector.

Fill in the first blank with either row or column, and the second with either $$n$$ or $$m$$.

For $$\mathbf{vA}$$ to make sense, $$\mathbf{v}$$ must be a __ vector of length __.

Answer MO1 row, $$n$$

In the following exercises, assume the conditions of MO1 and that $$\mathbf{vA}$$ makes sense.

Exercise MO2: Fill in the first blank with either row or column, and the second with either $$n$$ or $$m$$.

$$\mathbf{vA}$$ is a __ vector of length __.

Answer MO2 row, $$m$$

Notation for MO3-MO5: Let $$\mathbf{A}(i, j)$$ be the $$(i, j)$$ element of $$\mathbf{A}$$, $$\mathbf{A}(i, *)$$ the $$i$$th row of $$\mathbf{A}$$, and $$\mathbf{A}(*, j)$$ the $$j$$th column of $$\mathbf{A}$$. Let $$\mathbf{v}(j)$$ be the $$j$$th element of $$\mathbf{v}$$.

Exercise MO3: Write the $$j$$th element of $$\mathbf{vA}$$ using sigma notation.

Answer MO3 $$\displaystyle \sum_{i=1}^n \mathbf{v}(i)\mathbf{A}(i, j)$$

Exercise MO4: True or false: The elements of $$\mathbf{vA}$$ are $$\mathbf{v}\cdot\mathbf{A}(*, 1), \mathbf{v}\cdot\mathbf{A}(*, 2), \ldots, \mathbf{v}\cdot\mathbf{A}(*, m)$$.

Exercise MO5: Now suppose $$\mathbf{A}$$ is $$n \times n$$ for $$n \ge 5$$. Fill in the first blank with the right coordinates and the second with a matrix:

$$\sum_{k = 1}^n \mathbf{A}(2, k)\mathbf{A}(k, 5)$$ is the __ element of the matrix __.

Answer MO5 $$(2, 5)$$, $$\mathbf{A}^2$$

## Chapter 15 onwards

### Calculus

Here are two excellent resources for refreshing your memory.

Topics worth remembering:

## Chapter 23 onwards

### More Linear Algebra

Recall the Basic Matrix Operations, above. You will also need the following summaries of properties.