Refereed problems

The class is split into three groups, based on last name.

Group 1: Last names beginning with the letters A through J
Group 2: Last names beginning with the letters K through L
Group 3: Last names beginning with the letters N through Y.

Due Tuesday, June 14th

Definition Let $b \neq 0$ be an integer. We say that $m \equiv n (\mod b)$ if $b ∣ (m - n)$ .

All groups:

Prove the following statements.

For every integer $m$ , we have that $m \equiv m (\mod b)$ .
For every integer $m, n$ , we have that $m \equiv n (\mod b)$ implies that $n \equiv m (\mod b)$ .
For every three integers $m, n, ℓ$ , we have that $m \equiv n (\mod b)$ and $n \equiv ℓ (\mod b)$ implies that $m \equiv ℓ (\mod b)$ .

This shows that $\equiv$ is an equivalence relation.

In addition, each group should prove their part of the following.

Group 1: Show that if $m \equiv n (\mod b)$ and $p \equiv q (\mod b)$ , then we also have that $m + p \equiv n + q (\mod b)$ .

Group 2: Show that if $m \equiv n (\mod b)$ and $p \equiv q (\mod b)$ , then we also have that $m - p \equiv n - q (\mod b)$ .

Group 3: Show that if $m \equiv n (\mod b)$ and $p \equiv q (\mod b)$ , then we also have that $m \cdot p \equiv n \cdot q (\mod b)$ .

We will discuss in class how the refereeing process works.

Due Tuesday, June 21st

Group 1: Show that if $f : X \to Y$ is an injective function, then there is some function $g : Y \to X$ which is surjective.

Group 2: Show that if $f : X \to Y$ is a surjective function, then there is some function $g : Y \to X$ which is injective.

Group 3: Show that if $f : X \to Y$ is a function and if there is some function $g : Y \to X$ such that $g \circ f : X \to X$ is the identity function, then $f$ must be injective.

Due Tuesday, June 28th

Recall that Pascal's triangle is defined via the relations $P_{i, 0} = P_{i, i} = 1$ and $P_{i, j} = P_{i - 1, j - 1} + P_{i - 1, j}$ , where the first number denotes the row, and the second the diagonal column.

Prove the following using induction.

Hint: In each case, consider writing out the first few terms to make sure that you have the indexing right. What is the variable that you should use in your induction step?

Group 1: Show that, for every integer $n$ , the sum of all of the entries in the $n$ -th row is $2^{n}$ .

Group 2: Show that, for every integer $n$ , and for every fixed integer $0 \leq k \leq (n - 1)$ , that

\sum_{i = 0}^{k} (- 1)^{i} P_{n, i} = (- 1)^{k} P_{n - 1, k}

.

Group 3: Show that, for every fixed integer $k$ , and for every integer $n$ , that

\sum_{i = 0}^{n} P_{i + k, k} = P_{n + k + 1, k + 1}

.

Due Tuesday, July 19th

The goal is for each group to prove one of the ubiquitous limit laws of first-year calculus, in the context of sequences.

Let $(a_{n})_{n \in ℕ}$ and $(b_{n})_{n \in ℕ}$ be sequences such that

\lim_{n \to \infty} a_{n} = L

and

\lim_{n \to \infty} b_{n} = M

.

Let k be any real number.

Group 1: Show that $\lim_{n \to \infty} a_{n} b_{n}$ exists and is equal to LM. Hint: Note that

| a_{n} b_{n} - L M | = | a_{n} b_{n} - a_{n} M + a_{n} M - L M |

and remember the properties of the absolute value function.

Group 2: Show that $\lim_{n \to \infty} (a_{n} + b_{n})$ exists and is equal to $L + M$ .

Group 3: Show that $\lim_{n \to \infty} k \cdot a_{n}$ exists and is equal to kL.