Homework Problems

Previously, homework assignments were beautifully typeset in LaTeX and distributed as PDFs. On the daily-homework model we adopted in week 6, this no longer makes sense. A few students even complained that the homework after this shift felt "disorganized" as a result of the fact that "now the problems are just written on the board like anything else".

Because I am an overly kind human being who sometimes spends too much time on things the students should do for themselves, I have organized this page of homework problems assigned to students in class (i.e., given to students on the blackboard during lecture).

For Friday, 30 September 2022: Prove or disprove each of the following.

1. Let \( A \), \( B \), \( C \), and \( D \) be sets. If \( A \subseteq C \) and \( B \subseteq D \), then \( A \times B \subseteq C \times D \).
2. For all sets \( A \) and \( B \) we have \( \mathbb{P}(A \times B) = \mathbb{P}(A) \times \mathbb{P}(B) \).

For Friday, 30 September 2022:

1. Prove that \( \mathbb{P}(A) \cup \mathbb{P}(B) \subseteq \mathbb{P}(A \cup B) \) for all sets \( A \) and \( B \). Does \( \mathbb{P}(A) \cup \mathbb{P}(B) = \mathbb{P}(A \cup B) \) in general? Prove or disprove!
2. Prove or disprove for all sets \( A, B, C, D \):
   1. \( A \times (B \cup C) = (A \times B) \cup (A \times C) \).
   2. \( (A \cup B) \times (C \cup D) = (A \times C) \cup (B \times D) \).

For Friday, 7 October 2022:

1. Prove that the relation \( x \sim y \) when \( x - y \in \mathbb{Z} \) is an equivalence relation on \( \mathbb{Q} \).

For Friday, 7 October 2022:

1. For each subset of the set of properties \( \{\text{reflexive}, \text{symmetric}, \text{antisymmetric}, \text{transitive}\} \), either construct a relation which satisfies exactly those properties and no others from our list OR prove that no such relation exists.

   For example, for the subset \( \{\text{reflexive}, \text{antisymmetric}\} \) you would provide a relation which is reflexive and antisymmetric but neither symmetric nor transitive. There are sixteen subsets of that four-element set, so this problem has sixteen parts.

For Wednesday, 12 October 2022:

1. For each of the relations \( f \) below, decide if \( f \) is a function with the given domain and codomain. Explain why or why not using definitions. If \( f \) is a function, decide whether or not it is injective, surjective, bijective, or none; explain using definitions.
   • \( f = \{(1, 1), (1, 2), (3, 2)\} \) from \( [3] \) to \( [3] \).
   • \( f = \{(1, 1), (2, 2), (3, 2)\} \) from \( [3] \) to \( [3] \).
   • \( f = \{(1, 1), (2, 2), (3, 2)\} \) from \( [3] \) to \( [4] \).
2. For each of the functions \( f \) below, decide if \( f \) is injective, surjective, bijective, or none. Prove it!
   • \( f \colon \mathbb{Q} \to \mathbb{Q} \) defined by \( f(x) = 2x + 1 \).
   • \( f \colon \mathbb{Z} \to \mathbb{Z} \) defined by \( f(x) = 2x + 1 \).
   • \( f \colon \mathbb{Z} \to \mathbb{N}_0 \) defined by \( f(x) = |x| \).

For Wednesday, 19 October 2022:

1. For each subset \( X \subseteq \{\text{injective}, \text{surjective}\} \), construct a function which satisfies exactly the properties in \( X \).

   Challenge: Make your example so that the domain and codomain are as small as possible.

For Wednesday, 19 October 2022:

Let \( f \colon A \to B \) and \( g \colon B \to C \) be functions.

1. Prove that if \( f \) and \( g \) are surjective, then \( g \circ f \) is surjective.
2. Prove that if \( g \circ f \) is injective, then \( f \) is injective.
3. Prove that if \( g \circ f \) is surjective, then \( f \) need not be surjective.

For Friday, 21 October 2022:

1. Prove that a function \( f \) is surjective if and only if for all \( x \in \operatorname{cod}(f) \) we have \( |f^{-1}(x)| \geq 1 \).
2. Prove that a function \( f \) is surjective if and only if \( f(\operatorname{dom}(f)) = \operatorname{cod}(f) \).

For Friday, 21 October 2022:

1. Prove that for all \( n \in \Z \) we have \( 1 \mid n \), \( n \mid n \), and \( n \mid 0 \).

For Monday, 24 October 2022:

1. Prove that the divisibility relation is transitive.

For Wednesday, 2 November 2022, prove (at least the first two parts of) the following proposition.

For Friday, 4 November 2022, use Euclid's Algorithm with back-substitution to express \( \gcd(a, b) = as + bt \) for some \( s, t \in \Z \).

1. \( a = 15 \), \( b = -350 \)
2. \( a = 257 \), \( b = 37 \)
3. \( a = -87 \), \( -21 \)

For Monday, 14 November 2022, prove the following propositions.

• Prove that for all prime numbers \( p \), the square root of \( p \) is irrational.

For Monday, 14 November 2022, prove the following proposition.

• Prove that for all \( n \in \N \) we have \( \displaystyle{\sum_{k=0}^n k^2 = \frac{n(n+1)(2n+1)}{6}} \).
• Conjecture and prove a formula for \( \displaystyle{\sum_{k=0}^n k^3} \) for all \( n \in \N \).

For Wednesday, 16 November 2022, prove the following propositions.

• For all \( n \in \N \) we have \( 1 \leq n! \).
• For all \( n \in \N \) we have \( n < 2^n \).
• Every \( n \in \Z_{\geq 2} \) is divisible by a prime number.

For Monday, 21 November 2022, prove the following propositions.

• The \( n^{\textrm{th}} \) Fibonacci number is an integer for all \( n \in \N \).
• For all \( n \in \N \) we have \( F_{2n} = F_n(F_{n-1} + F_{n+1}) \).
• For all \( n \in \N \) we have \( \displaystyle{\sum_{k = 1}^n F_k^2 = F_n \cdot F_{n + 1}} \).

For Wednesday, 30 November 2022, consider the sequence \( (A_n)_{n \geq 0} \) where \( A_n = \frac{1}{2^n\sqrt{5}}\left((1+\sqrt{5})^n - (1-\sqrt{5})^n\right) \). Complete either one of the following exercises.

• Prove that the sequence \( (A_n)_{n \geq 0} \) is the sequence of Fibonacci numbers via strong induction. I.e., prove that \( A_n = F_n \) for all \( n \geq 0 \).
• Prove that the sequence \( (A_n)_{n \geq 0} \) satisfies the Fibonacci recursion (i.e., using some algebra). Use this fact together with the Universality of the Fibonacci Numbers to prove that \( A_n = F_n \) for all \( n \geq 0 \).

For Wednesday, 30 November 2022, read my notes on enumeration and Oscar Levin's chapter on counting. Prioritize reading Levin's sections 1.1 (Additive and Multiplicative Principles), 1.2 (Binomial Coefficients), and 1.3 (Combinations and Permutations). My presentation will differ from his, but the content is roughly the same.