"Y20HW" refers to the "Homework, material covered" page of the 2021 edition of this course. Y20HW03 refers to class #3 in year 2020.
"ORD" refers to ordinary homework problems, "Bonus" refers to bonus problems. They all count together, but the Bonus problems may take more work per point. Solve the ordinary problems first.
"DM 4.1.15" refers to item 4.1.15 (Chapter 4, Section 1)
in the instructor's online
Discrete Mathematics Lecture Notes.
WARNING. Skip DM Section 2.2 and Chap. 7. DM Sec 2.2 is replaced
by ASY (below) and DM Chap. 7 is replaced by PROB (click "Texts"
on the banner).
"ASY 6.21" refers to item 6.21 (Section 6) in the Asymptotic Equality and Inequality handout, October 27, 2022 version. (The date is under the title; refresh your browser if you see an older version. If that is not sufficient, clear the cache of your browser or try another browser.)
"PROB 7.4.22" refers to item 7.4.22 (Section 4) in the handout Finite Probability Spaces.
Class 27, Thu 12-01 (last class) Aces vs Spades: uncorrelated but not indepedent. Diagonal Ramsey numbers. Erdös's lower bound: the Probabilistic Method. Upper bound on the independence number of almost all graphs.
27.10 ORD (3+6+5 points) Consider and ordered poker hand. (a) What is the size of the sample space for this experiment? (b) For $1\le i,j \le 5$, let $A_i$ denote the event that the $i$-th card in the hand is an Ace, and $B_j$ the event that the $j$-th card in the hand is Spades. Prove that for every $i,j$, these two events are independent. (c) Let $X$ denote the number of Aces and $Y$ the number of Spades in the poker hand. Use (b) to prove that these two random variables are uncorrelated.
27.20 Notation: diagonal Ramsey numbers $R(k) := R(k,k)$.
For instance, $R(3)=6$.
27.22 DO Recall: by the Erdös-Szekeres bound we have $R(k) \le \binom{2k-2}{k-1} < 4^{k-1}\,.$ Infer from this that for every $n\ge 1$ we have $n\to ((1/2)\log_2 n, (1/2)\log_2 n)$.
27.25 ORD (6+3 points) (a) Give a simple proof that $(\forall k\ge 1)(k^2 \not\to (k+1, k+1))$. (b) Deduce from this that for every $n\ge 1$ we have $n\not\to (1+\sqrt{n}, 1+\sqrt{n})$.
27.30 Reward (Zsigmond Nagy, 1973) $(\forall k\ge 3)\left(\binom{k}{3}\not\to (k+1,k+1)\right)$. Define Nagy's graph $N_k$ by letting $V=\binom{[k]}{3})$ and making $A,B\in\binom{[n]}{3}$ adjacent if $|A\cap B|=1$. Prove that (a) $\alpha(N_k)\le k$ and (b) $\omega(N_k) \le k$.
27.32 Reward Prove: $\omega(N_7)=7$.
27.34 DO Infer from Nagy's graph that $n \not\to (2+(6n)^{1/3}, 2+(6n)^{1/3})$.
27.40 DO (Erdös) Consider the uniform
Erdös-Rényi model. Prove that almost all graphs $G$
satisfy $\alpha(G) < 1+ 2\log_2 n$.
Compare this result with 27.22.
Review the proof from the iPad class notes.
27.45 ORD (6 points) Derive from Erdös's result that $(\forall n\ge 2)(n \not\to (1+2\log_2 n, 1+2\log_2 n))$.
Class 26, Wed 11-18 Problem session.
Class 25, Tue 11-29 Inclusion-Exclusion formula. Ramsey's Theorem for graphs. Directed graphs (digraphs), oriented graphs, orientation. Accessibility, strong components. Due Dec 7.
25.10 ORD (10 points) We say that a random variable $X$ is positive if $(\forall a\in\Omega)(X(a) > 0)$. Find a probability space and two positive random variables that are uncorrelated but not independent. Make your sample space as small as possible. You don't need to prove minimality of the sample space. Conceptual clarity is paramount.
25.12 HW
(ab) ORD (4+2 points) Prove:
$\eee^{\lfloor \ln n\rfloor} = \Theta(n)$.
State specific values of the implicit constants. You gain the
$+2$ points if your constants are tight. You do not need to prove
that your constants are tight.
(c) Bonus (8 points) Prove: the sequence
$(1/n)\cdot\eee^{\lfloor \ln n\rfloor}$ is divergent.
25.14 ORD (6 points) Let $a_n = (\ln n)^{\ln\ln n}$. Is the sequence $(a_n)$ polynomially bounded?
25.17 Reward (strongly negatively correlated events)
Let $A_1,\dots,A_m\subseteq\Omega$ be events such that
(i) $(\forall i)\left(P(A_i)=1/2\right)$ and
(ii) $(\forall i\neq j)\left(P(A_i\cap A_j)\le 1/5\right)$.
Prove: $m\le 6$.
25.20 DO Let $A,B\subseteq \Omega$ be events. Then
25.22 DO Let $A,B,C\subseteq \Omega$ be events. Then $$P(\overline{A\cup B\cup C})=P(\Omega)-P(A)-P(B)-P(C)+P(A\cap B) +P(A\cap C)+P(B\cap C)-P(A\cap B\cap C)\,.$$
25.25 ORD (6 points) Let $(\Omega,P)$ be a probability space and assume $(\forall a\in\Omega)(P(a) > 0)$. Let $A,B,C\subseteq \Omega$ be events. Assume $P(A)=P(B)=P(C)=1/2$ and $P(A\cap B)=P(A\cap C)=P(B\cap C)=1/6$. Prove: $A\cup B\cup C=\Omega$ and $A\cap B\cap C=\emptyset\,.$
25.30 Theorem (Inclusion-Exclusion formula) Let $A_1,\dots,A_k\subseteq\Omega$ be events. Then $$P(\overline{A_1\cup\dots\cup A_k})=\sum_{j=0}^k (-1)^{\,j}S_j$$ where $$S_j = \sum_{T\in\binom{\Omega}{j}} P\left(\bigcap_{i\in T} A_i\right)\,.$$
Note that $S_0=P(\Omega)=1$.
25.32 Theorem (Inclusion-Exclusion formula) We rephrase Theorem 25.30. Let $A_1,\dots,A_k\subseteq\Omega$ be events. Then
$$ P(\overline{A_1\cup\dots\cup A_k}) = \sum_{T\subseteq [k]} (-1)^{|T|} P(A_T)$$ where $A_T = \bigcap_{i\in T} A_i$.
25.34 DO Prove that Theorems 25.32 and 25.34 are equivalent.
25.40 Reward (Bonferroni's Inequalities)
We use the notation of Exercise 25.30. Let $C=\overline{A_1\cup\dots\cup A_k}$.
Then we have
$$P(C)=\sum_{j=0}^k (-1)^{\,j} S_{j}\,.$$
Let us consider the truncations of this sum: for $\ell=0,\dots,k$ let
$$ R_{\ell} = \sum_{j=0}^{\ell} (-1)^{\,j} S_{j}\,.$$
Prove that for all even values of $\ell$ we have
$P(C) \le R_{\ell}$ and for all odd values of $\ell$ we have
$P(C) \ge R_{\ell}$.
Examples: $S_0-S_1+S_2-S_3 \le P(C) \le S_0-S_1+S_2$.
25.42 DO Observe that Bonferroni's inequalities trivially hold for $\ell = 0$ and $1$.
25.44 Bonus (7 points) Prove Bonferroni's inequality for $\ell =2$.
25.50 ORD (7 points) Count the surjections $f: [n]\to [5]$. Your answer should be a closed-form expression using binomial cofficients. Evaluate your formula for $n=10$.
25.60 DEF: Recall from the class notes the Erdös-Rado arrow symbol: We say that "$n\to (k,\ell)$" (in words: "$n$ arrows $(k,\ell)$") if for all red/blue colorings of the edges of the complete graph $K_n$, either there is an all-red $K_k$ or an all-blue $K_{\ell}$.
25.64 DO (Baby Ramsey) Prove: $6\to (3,3)$.
25.66 DO (Baby Ramsey is tight) Prove: $5\not\to (3,3)$.
25.70 DEF (Ramsey numbers) $R(k,\ell)$ dentes the smallest
value of $n$ such that $n\to (k,\ell)$.
Example. The Baby Ramsey Theorem says that $R(3,3)\le 6$, and 25.66
states that this bound is tight, i.e., in fact, $R(3,3)=6$.
25.72 ORD (3+3 points) Prove: $(\forall k\ge 2)(R(k,2)=k)$. Note that you need to prove two inequalities: (a) $R(k,2)\le k$ and (b) $R(k,2)\ge k$.
25.74 DO Prove: $(\forall k,\ell \ge 2)(R(k,\ell)=R(\ell,k))$.
25.77 Reward (Erdös--Szekeres, 1935): $$(\forall k,\ell\ge 2)\left(R(k,\ell) \le \binom{k+\ell-2}{k-1}\right)\,.$$ Prove this by induction on $k+\ell$. The base cases are those with $k=2$ or $\ell = 2$ (infinitely many base cases). Use Pascal's identity.
25.79 ORD (3 points) Use the Erdös--Szekeres theorem to prove that $(\forall k\ge 2)(R(k,k) < 4^{k-1})$.
25.82 Bonus (8 points) For $k=3, \ell=4$ the Erdös--Szekeres theorem states that $R(3,4)\le 10$. Prove that this upper bound is not tight, i.e., $R(3,4)\le 9$. There is a sweet and simple proof. DON'T LOOK IT UP, discover it yourself.
25.85 ORD (3+8 points) (a) Define the meaning of the arrow symbol $n\to (k,\ell,m)$. (b) Prove: $17\to (3,3,3)$.
25.100 STUDY DM 6.4 (Digrph terminology)
25.105 DO DM 6.4.7 (counting orientations), 6.4.9 (counting tournaments), 6.4.12 (directed handshake theorem)
25.108 ORD (6+4 points) DM 6.4.16 (accessibility)
25.110 Bonus (5+6 points) DM 6.4.19 (min number of edges of a weakly/strongly connected digraph)
25.112 Terminology A clarification to the definition of strong connectedness (second bullet point in DM 6.4.18): a digraph $(V,E)$ is strongly connected if for every $u,v\in V$ there exists a directed path from $u$ to $v$. (Note: if $u=v$ then there always exists a path from $u$ to $v$, namely, the path of length zero.)
25.114 Reward DM 6.4.20 (under a degree condition, weak connectedness implies strong connectedness)
25.116 ORD (7 points) DM 6.4.22 (every tournament has a Hamilton path)
25.120 Bonus (8 points) DM 6.4.25 (DAG has topological sort)
More to follow. Please check back later. Please report any errors.
Class 24, Thu 11-17 Blowing up the sample space.
Exponential vs. polynomial rate of growths. Graph theory.
Connected components. Induced subgraphs. Independent sets.
Chromatic number.
All problems are due Nov 28, unless otherwise stated, along with
previously stated problems marked "due Nov 28." All problems
that were not discussed in class or stated in the iPad notes
are due December 7.
24.10 ORD (4+3+4 points)
(a) Explain, what is wrong with the following sentence:
"The sequence $a_n$ eventually converges to $\sqrt{5}$."
(b) Correct the sentence by making minimum change.
(c) Correct the sentence by replacing the phrase
"eventually converges to" by one or two words
that do not include "converges." Give two answers.
24.15 ORD (3+4 points)
(a) Explain, what is wrong with the following formula:
$\lim_{n\to\infty} a_n \to \infty$.
(b) State two correct and simple formulas each of which
expresses the intended meaning.
24.20 Bonus (4+7 points)
Consider the following problem.
Let $\Omega$ denote the set of poker hands, so $|\Omega|=\binom{52}{5}$.
Consider the uniform probability space with $\Omega$ as the sample space.
Let $X$ denote the number of Aces in a poker hand. Prove that
$E(X)=5/13$.
(a) Explain, what is wrong with the following solution.
"Let $X_i$ denote the indicator variable indicating the event $A_i$
that the $i$-th card is an Ace. Then $X=\sum_{i=1}^5 X_i$ and therefore
$E(X)=\sum_{i=1}^5 E(X_i)$ by the linearity of expectation. Moreover,
$E(X_i)=P(A_i)$ (the expectation of an indicator variable is the
probability of the event it indicates (PROB 7.7.11)). By symmetry,
the $i$-th card has an equal chance of being any of the 13 kinds, so
$P(A_i)=1/13$. Therefore $E(X)=\sum_{i=1}^5 1/13 = 5/13$."
(b) Fix the solution in such a way that the proof given here becomes part of a correct proof. In particular, do not change the definition of the random variables $X_i$.
24.30 DO Review from the iPad class notes the proof of the following fundamental limit relation: $$\lim_{x\to \infty} \frac{\ln x}{x} = 0\,.$$ Use L'Hospital's Rule (from Calculus). Watch especially what limit L'Hospital's Rule assumes to exist and the existence of what limit is its conclusion.
24.32 DO Review from the iPad class notes the proof of the statement $$\lim_{x\to \infty} \frac{x}{\eee^x} = 0$$ using the preceding exercise and a change of the variable. No calculus is used in this proof, but remember to verify that your new variable goes to infinity as $x\to\infty$.
24.34 DO Review from the iPad class notes the proof of the statement $$(\forall C\in\rrr)\left(\lim_{x\to \infty} \frac{x^C}{\eee^x}\right) = 0$$ using the preceding exercise and a change of the variable. No calculus is used in this proof, but remember to verify that your new variable goes to infinity as $x\to\infty$.
24.36 NOTATION $\exp(x) = \eee^x$.
24.38 ORD (4 points: Exponential decay beats polynomial growth)
Prove:
$$(\forall c,d > 0)\left(\lim_{x\to \infty} \frac{x^c}{\exp(x^d)}\right) = 0$$
using the preceding exercise and a change of the variable.
Do not use calculus in the proof, but remember to verify
that your new variable goes to infinity as $x\to\infty$.
Example: $x^{100}/\eee^{\sqrt{x}}\to 0$ (as $x\to\infty$).
24.40 Bonus (3+7 points, due Wed Dec 7) Fix a real number $p$ in the interval $0 < p < 1$. Prove that in the Erdös-Rényi model $\Gbold(n,p)$, almost every graph has diameter 2. First give a clear explanation of the meaning of this statement. This explanation is worth the 3 points.
24.50 DEF (polynomially bounded sequence) We say that the sequence $(a_n)$ is polynomially bounded if $(\exists C)(a_n = O(n^C))$.
24.52 DO In class we defined a polynomially bounded sequence as a sequence that is eventually less than $n^C$ for some real number $C$. Prove that this definition is equivalent to the definition given in the preceding item. In the future, always use that definition (from the preceding item).
24.55 ORD (6 points, due Wed Dec 7) Let $a_n \ge 1$.
Prove:
The sequence $a_n$ is polynomially bounded if and only if
$\ln a_n = O(\ln n)$.
24.60 ORD (5 points, due Wed Dec 7) Let $N$ be the product of $k$ consecutive integers $(k\ge 1)$. Prove that $N$ is divisible by $k!$. The proof should be very short -- one or two lines.
24.65 Reward Let $p$ be a prime number, $t\ge 1$, and $0\le k\le n$. Prove: if $p^t$ divides $\binom{n}{k}$ then $p^t \le n$.
24.70 DO REVIEW DM Section 6.1 (graph theory terminology)
24.72 DO (triangle inequality) Let $G$ be a graph and $u,v,w\in V(G)$. Prove: $\dist(u,v)+\dist(v,w)\ge \dist(u,w)$.
24.74 ORD (5 points) Let $G$ be a graph. Prove: $G$ or $\Gbar$ (the complement of $G$) is connected.
24.76 Bonus (6 points, due Wed Dec 7)
Let $G$ be a graph. Prove that at least
one of the following holds:
(i) $\diam(G)\le 2$ (ii) $\diam(\Gbar)\le 2$
(iii) $\diam(G)=\diam(\Gbar)=3$.
Make it clear
in every argument, what is your assumption. Clarity of the logic
of your steps is paramount.
24.78 ORD (7 points, due Wed Dec 7) Prove: if a graph has $n$
vertices and
$k$ connected components then it has $m\ge n-k$ edges. Proceed
by induction on $n-k$.
A solution with comments is posted here.
24.80 DEF We say that a graph $G$ is self-complementary if $G\cong \Gbar$ ($G$ is isomorphic to its complement).
24.82 ORD (4+4 points) (a) Find a self-complementary graph with $n=4$ vertices and one with $n=5$ vertices. If your graphs have standard names used in class, state them. To prove they are self-complementary, number their vertices and state an isomorphism from $G$ to $\Gbar$ in each case. You do not need to describe the verification of these isomorphisms. (b) Prove: if $G$ is a self-complementary graph with $n$ vertices then $n\equiv 0$ or $1\pmod 4$.
24.85 DEF A forest is a cycle-free graph (contains no cycles). A tree is a connected forest.
24.87 DO Prove: a tree with $n\ge 2$ vertices has a vertex of degree 1.
24.88 DO Prove: (a) A tree with $n\ge 1$ vertices has $m=n-1$
edges. Prove this by induction on $n$, using the preceding exercise.
(b) A forest with $k$ connected components has $m=n-k$ edges.
Give two proofs. (b1) Use part (a). (b2) Prove this by induction on $n-k$.
This will also give an alternative proof of (a).
24.95 DO Recall that $\alpha(G)$ denotes the
independence number of the graph $G$ (DM 6.1.42 terminology).
Prove: (a) $\alpha(P_n)=\lceil n/2\rceil$. (Here $n\ge 1$.)
Note that you need to prove two things:
(a1) $\alpha(P_n)\ge \lceil n/2\rceil$. You prove this by finding an
independent set of this size. (a2) $\alpha(P_n)\le \lceil n/2\rceil$.
For an elegant proof, use the Pigeon Hole Principle.
(b) $\alpha(C_n) = \lfloor n/2\rfloor$. (Here $n\ge 3$.)
Find an elegant proof.
(c) $\alpha(K_n) = 1$. $\alpha(K_{r,s})=\max(r,s)$.
(Here $K_{r,s}$ denotes the complete bipartite graph (also called
"bipartite clique") with parts of siz $r$ andn $s$.
24.97 Bonus (6 points, due Wed Dec 7) Let $G$ be a regular graph
of degree $\ge 1$. Prove: $\alpha(G)\le n/2$.
For an elegant proof, use an "averaging argument":
introduce indicator variables for the vertices in your
independent set $S$ (these are simply variables, not random
variables), write an inequality for each edge that
asserts that at most one of the two vertices of the edge
belongs to $S$, and add up these inequalities.
24.100 Bonus (7 points, due Wed Dec 7) Count the independent sets of the path $P_n$. (Note: $P_n$ has length $n-1$.) Give a very simple answer in terms of a familiar sequence. (Note that the empty set is an independent set.)
24.104 Bonus (6 points, due Wed Dec 7) Let $G$ be a graph with $n=6$ vertices. Prove: $\alpha(G)\cdot\alpha(\Gbar)\ge 6$.
24.106 Challenge (a) In the uniform Erdös-Rényi model $\Gbold(n,1/2)$, almost all graphs $G$ satisfy $\alpha(G) \le 1+2\log_2 n$ and therefore (b) almost all graphs also satisfy $\alpha(G)\cdot\alpha(\Gbar)=O(\log^2n)$.
24.110 DO Recall that a bipartite graph is a graph with chromatic number $\chi(G)\le 2$. Prove: a graph $G$ is bipartite if and only if $G$ contains no odd cycle.
24.112 DO Prove that the $k\times\ell$ grid graph and the $d$-dimensional cube graph are bipartite.
24.115 ORD (4+2 points, due Wed Dec 7) (a) Prove: A bipartite graph with $n$ vertices has $m\le \lfloor n^2/4\rfloor$ edges. (b) Show that this inequality is tight for every $n\ge 1$.
24.117 Reward (Mantel's Theorem) A triangle-free graph with $n$ vertices has $m\le \lfloor n^2/4\rfloor$ edges.
24.118 DO Prove Mantel's Theorem by induction on $n$.
Hint. Delete a pair of adjacent vertices.
24.119 DO Prove that Mantel's bound is tight for every $n$.
24.122 Reward Prove: If $G$ has no 4-cycles then the number of edges is $m=O(n^{3/2})$.
24.128 ORD (5 points, due Wed Dec 7)
Let $G$ be the $k\times \ell$
grid graph. (So $G$ has $k\ell$ vertices.) Prove: if both $k$
and $\ell$ are odd then $G$ is not Hamiltonian, i.e., $G$ does not
contain a Hamilton cycle (a cycle passing through all vertices).
Make your proof very short (just one line or two) (based on
previous exercises). Elegance counts.
24.132 ORD (5 points) Prove: for every graph $G$ with $n$ vertices, $\alpha(G)\cdot\chi(G)\ge n$. (Here $\chi(G)$ denotes the chromatic number of $G$.)
24.133 NOTATION For a graph $G$, we write $\omega(G)$ to denote the clique number of $G$, i.e., the size of the largest clique in $G$, i.e., the number of vertices of the largest complete subgraph. In other words, $\omega(G)=\alpha(\Gbar)$.
24.134 DO $\chi(G)\ge \omega(G)$.
While this is pretty obvious, we show in the next exercise that
the chromatic number is typically much greater than the clique number.
24.136 Bonus (7 points, due Wed Dec 7) In the uniform Erdös-Rényi model $\Gbold(n,1/2)$, almost all graphs $G$ satisfy $\chi(G) \ge (\omega(G))^{100}$. You may use any of the preceding exercises, including a challenge problem.
24.140 ORD (6 points, due Wed Dec 7) Find a graph $G$ with 6 vertices such that $\omega(G)=3$ but $\chi(G)=4$. You do not need to verify that $\omega(G)=3$ and $\chi(G)\le 4$ for your graph, but do prove that $\chi(G)\ge 4$.
24.142 Bonus (6 points, due Wed Dec 7)
Find a triangle-free graph $G$
with 11 vertices and chromatic number 4. You do not need to verify that
your graph $G$ is triangle-free ($\omega(G)\le 2$) and $\chi(G)\le 4$,
but do prove that $\chi(G)\ge 4$.
Hint. Make your graph have a 5-fold rotational symmetry in the plane.
In other words, make $V(G)$ a subset of $\rrr^2$ such that $G$
is invariant under the $72$-degree rotation of the plane (the rotated
graph is the same as the original: it has the same set of vertices and
the same adjacency relation). Note that the graph need not be planar.
WARNING. You can find this graph on the internet. DO NOT LOOK IT UP.
I assigned this problem to an 8th-grade math club, the kids experimented
at the blackboard, and one of the girls found the graph within a few minutes.
Do not deprive yourself of the experience of discovery.
24.145 ORD (6 points) Let $d$ denote the maximum degree of the graph $G$, i.e., $d=\max\{\deg(v) \mid v\in V(G)\}$. Prove: $\chi(G)\le d+1$. Proceed by induction on $n$, the number of vertices.
24.147 ORD (5 points, due Dec 7) Let $d$ denote the maximum degree of the graph $G$. Prove: $\alpha(G)\ge n/(d+1)$. Your solution should be very short (two or three lines) with reference to previous exercises.
24.150 Bonus (8 points) Let $G$ be a triangle-free graph. Prove: $\chi(G) = O(\sqrt{n})$. State your constant hidden in the big-Oh notation. (The smaller, the better.)
24.160 DO STUDY PROB Chapter 7.11 (Strong concentration inequalities). Understand the results. Studying the proofs is recommended but not required.
24.165 Bonus (12 points, due Dec 7) PROB 7.8.11 (number of common neighbors in random graph). This result does not follow from Chebyshev's inequality; use the Bernstein--Hoeffding bound for bounded variables (PROB Theorem 7.11.7). Make sure to refresh your browser; this chapter has recently been updated.
More to follow. Please check back later. Please report any errors.
Class 23, Wed 11-16 Problem session.
Class 22, Tue 11-15 Diameter of random graphs: "almost all graphs have diameter 2."
More to follow. Please check back later. Please report any errors.
Class 21, Thu 11-10
Expected value of product of independent random variables.
Variance, Cauchy-Schwarz inequlality. Covariance.
Positively correlated, uncorrelated, negatively correlated
pairs of random variables. Connection to similar concepts
about events via indicator variables.
Variance of sum of random variables is the sum of their
pairwise covariances. Variance of sum of pairwise independent
random variables.
Asymptotic notation: little-oh, big-Oh, big-Omega, big-Theta.
Rates of growth.
Graphs, subgraphs, spanning subgraphs. Trees. Spanning trees.
Counting spanning trees: Matrix-tree theorem (Kirchhoff 1848)
(indicated), Cayley's formula. Distance, diameter.
Typical diameter of random graphs?
21.10 DO STUDY PROB Sections 7.5 (random graphs), 7.7--7.10 (independence of random variables, variance, Chebyshev's inequality)
21.20 DO STUDY DM Chapter 2, Sections 2.3, 2.4 (asymptotic notation)
21.30 DO STUDY DM Section 6.1 (graph terminology)
21.43 DO PROB 7.7.6, 7.7.7 (linearity of expectation)
21.50 DO STUDY PROB 7.7.14 (Markov's Inequality)
21.55 ORD (3+5+4+4 points) PROB 7.7.17 (lottery)
21.60 ORD (8+3 points) PROB 7.7.18 (Moonwatcher' Club)
The 3 points go for the size of the sample space. Half of the 8 points
go for the rigorous definition of the indicator variables you introduce.
21.70 HW PROB 7.7.19 (b)(c)(d) (cycles in random graph)
(b,c) ORD (4+6 points) (d) Bonus (6 points)
In each problem, half the credit goes for the rigorous definition of the
indicator variables you introduce. "Random graph" in this problem
refers to the uniform Erdös-Rényi model $\Gbold(n,1/2)$.
21.73 Reward PROB 7.7.20 (counting prime divisors)
21.76 DO PROB 7.7.21 (mismatched letters)
21.80 ORD (4+3+2) PROB 7.7.22 (marbles in cups)
The 2 points go for the size of the sample space.
21.85 Reward PROB 7.7.23 (number of cycles in random permutation)
21.90 DO (Chebyshev's Inequality) STUDY PROB 7.8.10
21.95 Bonus (7 points, due Nov 28) PROB 7.8.11 (number of common neighbors in random graph). Here "random graph" refers to the uniform Erdös-Rényi model $\Gbold(n,1/2)$.
21.100 Bonus (2+8+5 points, due Nov 28) PROB 7.8.21 (variance of the number of triangles). Here "random graph" refers to the Erdös-Rényi model $\Gbold(n,p)$.
21.103 ORD (5 points) Show that the variables $X$ and $Y$ defined in PROB 7.8.17(a) are not independent (number of Aces and number of Spades in poker hand are not independent)
21.105 Bonus (6+8 points, due Nov 28) PROB 7.8.17 (a)(b) (number of Aces and number of Spades in poker hand are uncorrelated)
21.107 Challenge PROB 7.8.22 (strongly negatively correlated events)
21.110 ORD (7 points, due Nov 28) PROB 7.9.4 (uncorrelated but not independent random variables). You do not need to prove that your sample space has minimum size.
21.113 ORD (2+3+3+4+4 points) What is the diameter of (a) the complete graph $K_n$ $(n\ge 1)$ (b) the cycle $C_n$ $(n\ge 3)$ (c) the complete bipartite graph $K_{k,\ell}$ $(k,\ell\ge 2)$ (d) the $d$-dimensional cube $Q_d$ (e) the $k\times\ell$ grid graph (see Figure 6 on p50 in DM) ?
21.117 ORD (5 points) DM 6.1.49 (number of shortest paths between opposite corners of the $k\times \ell$ grid)
21.120 ORD (14 points, lose 3 points for each mistake, due Nov 28) DM 6.1.34 (draw all 7-vertex trees)
21.130 ORD (3+2 points) DM 2.3.3 (adding little-oh relations)
21.133 ORD (4 points) DM 2.3.6 (little-oh vs logarithm)
21.136 DO DM 2.4.2 (if ratio converges)
21.139 ORD (4+4 points) DM 2.4.9 (big-Oh in exponent)
21.142 ORD (5 points) Find two sequences, $a_n$ and $b_n$ such that (i) $a_n, b_n \ge 1$, (ii) $a_n =\Theta(b_n)$, (iii) the sequence $a_n/b_n$ is divergent
21.146 ORD (3+2 points) DM 2.7.7 (Theta vs log)
21.150 ORD (3+3+4 points, due Nov 28) DM 2.7.8 (polynomially bounded sequences)
21.154 ORD (5 points) Prove: $F_{n+1} = \Theta(F_n)$ where $F_n$ denotes the $n$-th Fibonacci number. The proof should be very simple. Elegance counts. State the hidden constants.
More to follow. Please check back later. Please report any errors.
Class 20, Wed 11-09 Problem session.
Class 19, Tue 11-08 Expected value, linearity. Definition: sum over domain. Equivalent definition: sum over range. Indicator variables -- Bernoulli trials. Expected number of heads in $n$ flips of a biased coin: two proofs. Independence of random variables. Random graphs: the Erdös-Rényi model $\Gbold(n,p)$.
19.10 STUDY PROB Sections 7.7, 7.9, 7.10.
19.30 DO Let $X$ be the number of successes in a sequence
of $n$ independent Bernoulli trials with success probability $p$, i.e.,
the number of Heads in a sequence of $n$ flips of a biased coin with
$P($Heads$)=p$. Prove: $E(X)=np$.
Review the two proofs from class:
First proof: By the definition of expected value by summation
over the range:
$$ E(X) = \sum_{k=0}^n k\cdot \binom{n}{k}\cdot p^k(1-p)^{n-k}$$
Prove that this quantity is equal to $np$. (Review iPad class notes.)
Second proof: Let $X_i$ denote the indicator of the event
$A_i$ that the $i$-th Bernoulli trial is a success ($i$-th coin comes up Heads).
Notice that $X=\sum_{k=1}^n X_i$ and therefore $E(X)=\sum_{k=1}^n E(X_i)$.
Now $E(X_i)=P(A_i)=p$, so $E(X)=np$.
More to follow. Please check back later. Please report any errors.
Class 18, Thu 11-03 Conditional probability. Independence of
events, positively/negatively correlated events. Independence of
several events. Random variables.
Expected value, linearity of expectation.
All problems are due Nov 7, unless otherwise stated, along with
the following previously posted problems: ORD 13.104, 13.157a, 13.165a
Bonus 13.75, 13.77, 13.157b, 13.159, 13.165b.
18.10 DO STUDY PROB Sections 1, 2, 3, 4, 7.
18.15 DO PROB 7.2.2 (itarated conditional probabilities)
18.17 ORD (1+2+3+3 points) PROB 7.2.3 (3 dice)
18.20 DO PROB 7.2.4 (Theorem of Complete Probability)
18.23 ORD (3+5+4 points) PROB 7.2.5 (Probability of causes)
State the required probabilities as fractions reduced to their
lowest terms (numerator and denominator relatively prime).
State all intermediate results.
18.30 DO PROB 7.3.4 (independence of complement)
18.32 ORD (3 points) PROB 7.3.5 (independence of trivial events)
(Recall that a trivial event is an event with probablity zero or one.)
18.34 DO PROB 7.3.6 (rolling a die)
18.36 ORD (3 points) PROB 7.3.8 (sample space of prime cardinality)
18.38 DO PROB 7.3.11 (positive/negative correlation vs. conditional probability)
18.41 Bonus (8 points, due Nov 14) PROB 7.3.12 (divisibility by 2 and by 3)
18.44 ORD (3 points) Let $A,B$ be nontrivial events. Prove: if $A\subseteq B$ then $A$ and $B$ are positively correlated.
18.46 ORD (3 points) PROB 7.3.14 (independence of union, intersection)
18.50 ORD (3 points) PROB 7.4.3 (independence of complement)
18.52 DO PROB 7.4.4 (independence of trivial event)
18.54 ORD (3 points) PROB 7.4.5(b) (independence of union)
18.57 DO PROB 7.4.6 (lower bound on $\Omega$)
18.60 ORD (3+4 points) PROB 7.4.7 (pairwise but not full independence)
18.62 ORD (3 points) PROB 7.4.8(a) (triple intersection is insufficient). Your example should be very simple. Solving the Bonus version of this problem (7.4.8(b)) will not earn you credit for this question.
18.64 Bonus (3 points) PROB 7.4.8(b) (triple intersection is insufficient for balanced events)
18.67 ORD (3 points) PROB 7.4.13(a) (intersection of empty list of events)
18.70 Bonus (6 points) PROB 7.4.14 (equivalence of two definitions of independence)
18.72 DO PROB 7.4.15 (only $2^k-k-1$ conditions for independence)
18.75 Bonus (6 points) As in exercise 16.65 (PROB 7.1.5) consider the uniform probability space over the sample space $\Omega_n = \{0,1\}^n$ of $n$-bit strings, thought of as sequences of $n$ coin flips. Let $X_i$ denote the $i$-th bit of the sequence and let $A_i$ denote the event "$X_i=1$" (the $i$-th coin came up Heads). Prove that the events $A_1,\dots,A_n$ are independent.
18.80 DO PROB 7.4.16 and 7.4.17 (independence of complements)
18.82 Bonus (4 points) PROB 7.4.18 (lower bound on $|\Omega|$)
18.84 Bonus (5 points) PROB 7.4.19 (independence vs. $(n-1)$-wise independence). Elegance counts.
18.90 Challenge problems PROB 7.4.20-23 (pairwise independence with small sample space)
18.93 Bonus (5 points) PROB 7.4.24 (independence of Boolean functions of independent events)
18.95 Reward PROB 7.4.25 (colored balls)
18.100 ORD (3 points) PROB 7.7.3 (equivalence of alternative definition of expected value)
18.101 DO PROB 7.7.4 (infinite sum actually finite)
18.103 ORD (3 points) PROB 7.7.5 (min, max vs. expected value)
18.105 DO (additivity of expectation) PROB 7.7.6 (STUDY, simple but very important)
18.107 DO (linearity of expectation) PROB 7.7.7 (very important!)
18.112 ORD (3 points) PROB 7.7.10 (events vs. indicator variables)
18.113 ORD (3 points) PROB 7.7.11 (expected value vs. probability)
18.115 Reward PROB 7.7.12 (random variables vs. indicator variables)
18.117 ORD (3 points) PROB 7.7.13 (sum of Bernoulli trials)
18.119 ORD (6 points) PROB 7.7.15(a) (expected number of Aces). Express your answer as a fraction reduced to its lowest terms. Use indicator variables and the linearity of expectation. Half the credit goes for a clear definition of the random variables you use. State the size of your sample space.
18.121 Bonus (6 points) Let $f\in B^A$ be a random function with domain $A$ and codomain $B$ where $|A|=k$ and $|B|=\ell$. Let $X$ denote the number of collisions of $f$. Determine $E(X)$. Your answer should be a very simple closed-form expression in terms of $k$ and $\ell$. Use indicator variables. Half the credit goes for a clear definition of the random variables you use. State the size of your sample space.
More to follow. Please check back later. Please report any errors.
Class 17 (problem session), Wed 11-02
Class 16, Tue 11-01 Review: functions, collision, counting
injections. Naive probability. Finite probability spaces.
All problems are due Nov 7, unless otherwise stated, along with
some previously posted problems.
16.50 DO STUDY the PROB handout ("Finite Probability Spaces"), see link above.
16.51 DO Let $\Abar :=\Omega\setminus A$ denote the complement of the event $A$. Prove: $P(\Abar) = 1 - P(A)$.
16.52 DO PROB 7.1.2 $(P(\Omega)$ and $P(\emptyset))$
16.55 ORD (4 points) PROB 7.1.3 (counting trivial events)
16.58 DO STUDY the standard deck of 52 cards.
16.60 ORD (3 points) PROB 7.1.4 (probability of a "full house" poker hand). Calculate the probability as a fraction, given by its prime factorization. (Example: $36/75 = 2^2\cdot 3\cdot 5^{-2}$.) State the size of the sample space for this question.
16.65 ORD (4+2+3+2+2) PROB 7.1.5 (a),(b),(d1),(d3),(d4)
(fair coin flips: first coin Heads, first 2 coins Heads, first 2 coins
same, $k$ Heads, even number of Heads).
WARNING: You cannot assume that the coin flips are independent.
This will be a consequence of the uniformity of the distribution over
the coin flip sequences that will require a proof, see next exercise.
16.70 ORD (3+4 points) PROB 7.1.7 (a) (b) (distribution of Aces in bridge). Calculate the requested probabilities as rational numbers given by their prime factorizations. (Example: $36/75 = 2^2\cdot 3\cdot 5^{-2}$.) State the size of the sample space for each question.
16.75 DO PROB 7.1.8 (modular equation)
16.78 DO PROB 7.1.10 (union bound)
More to follow. Please check back later. Please report any errors.
Class 15, Thu 10-27 Graphs, the adjacency relation. Isomorphism.
Degree sequence. Complete graphs, cycles, paths. Connected components.
All problems are due Oct 31, unless otherwise stated,
along with problems from Class 13 and
problems ORD 10.96, 10.176(a), 10.177, 12.18, 12.75, 12.80,
12.95, 12.98, and
Bonus 10.176(b), 12.25, 12.82, 12.84, 12.88, 12.102, 12.108.
15.05 STUDY DM, Sec. 6.1 "Graph Theory Terminology" (see link above.)
15.10 Convention In the exercises below, $G=(V,E)$ is a graph with $n$ vertices and $m$ edges. If a second graph, $H=(W,F)$, is also mentioned, then $n_G$ and $n_H$ are the respective nuber of vertices of the two graphs and $m_G$ and $m_H$ their number of edges.
15.15 DO $m\le \binom{n}{2}$. Moreover, $m=\binom{n}{2}$ if and only if $G$ is the complete graph on $V$.
15.17 ORD (4 points) Count the graphs with a given set $V$ of $n$ vertices. Your answer should be a simple closed-form expression. Reason your answer.
15.20 HW (5+5 points) DM 6.1.6 (a) ORD (5 points)
(b) Bonus (5 points) (non-isomorphic regular graphs).
These problems ask you to draw graphs. Please attach a sheet with the
drawings. Please also describe your graphs verbally (in the PDF), using terms
for the graphs we have seen (complete graphs, cycles, connected components,
etc.) State the number of vertices and their degrees. If your verbal
description clearly and completely describes the graph (up to isomorphism),
you do not need to attach a picture.
More to follow. Please check back later. Please report any errors.
Class 14 (problem session), Wed 10-26
Class 13, Tue 10-25 Sequences of real (or complex) numbers.
Summing arithmetic and geometric progressions. Gcd of arbitrary sets
of integers.
Periodicity. Eventually periodic sequences, eventually nonzero sequences.
Limits. Asymptotic equality.
All problems are due Oct 31, unless otherwise stated,
along with problems ORD 10.96, 10.176(a), 10.177, 12.18, 12.75, 12.80,
12.95, 12.98, and
Bonus 10.176(b), 12.25, 12.82, 12.84, 12.88, 12.102, 12.108.
13.05 CONVENTION In this class, the term "sequence" will always refer to an infinite sequence of real numbers, unless expressly stated otherwise. Most but not all of what we learn also applies to infinite sequences of complex numbers.
13.10 STUDY ASY ("Asymptotic Equality and Inequality" handout), Sections 1--3. (See link near the top of this page and also under the "Texts" tab on the banner.)
13.15 DEF The sequence $a_0, a_1, a_2, \dots$ is an arithmetic progression if $(\exists d\in\rrr)(\forall n\ge 1)(a_n - a_{n-1}=d)$. We say that $d$ is the increment of the sequence. Such a sequence if defined by the recurrence $a_n = a_{n-1}+d$ $(n\ge 1)$ and the initial value $a_0$.
13.17 DO Let the sequence $a_0, a_1, a_2, \dots$ be an arithmetic progression with increment $d$. Prove the explicit formula $a_n = a_0 + nd$.
13.19 DO Observe that the sequence $a_0, a_1, a_2, \dots$ is an arithmetic progression if and only if each term is the b>arithmetic mean (average) of its two neighbors: $(\forall n\ge 1)(a_n = (a_{n-1}+a_{n+1})/2$.
13.21 DO (sum of arithmetic progression) Let the sequence $a_0, a_1, a_2, \dots$ be an arithmetic progression. Prove: $$(\forall n\ge 0)\left(\sum_{k=0}^n a_k = (n+1)\cdot\frac{a_0+a_n}{2}\right)$$ Hint. Let $S_n$ denote this sum. Compute $2S_n$ by adding $S_n$ to $S_n$, listed in reverse order, term by term: $2S_n = (a_0+a_n)+(a_1+a_{n-1})+\dots+(a_n+a_0)$. Notice that all the $n+1$ parenthesized terms are equal.
13.23 DO Use the previous exercise to show that $\sum_{j=1}^n j = n(n+1)/2$.
13.30 ORD (sum of geometric progression, 2 points) Prove: if $q\neq 1$ then $$ \sum_{k=0}^n q^k = \frac{1-q^{n+1}}{1-q}\,.$$ Hint Let $T_n$ denote this sum. Expand the product $(1-q)T_n$. Notice that you get a telescoping sum: neighboring terms cancel. [Note: in the original posting, there was a typo: $q^n$ instead of $q^{n+1}$.]
13.35 ORD (3 points) Evaluate the sum $\sum_{k=0}^n \binom{n}{k}2^{-k}$ as a simple closed-form expression.
13.40 DEF (gcd of any set of integers) Let $S\subseteq \zzz$.
We say that $e\in\zzz$ is a common divisor of $S$ if
$(\forall a\in S)(e\mid a)$.
We say that $d\in\zzz$ is a greatest common divisor of $S$ if
(a) $d$ is a common divisor of $S$
(b) $d$ is a multiple of all common divisors of $S$
(i.e., if $e$ is a common divisor of $S$ then $e\mid d$).
Compare this with EUCL DEF 1.7 (definition of greatest common divisor
of two integers).
13.42 DO Prove: every finite set $S\subseteq \zzz$ has a greatest common divisor.
13.44 Reward Prove: every set $S\subseteq \zzz$ has a greatest common divisor.
13.46 DO Let $S\subseteq\zzz$.
Prove: (a) If $d$ is a greatest common divisor of $S$ then $-d$ is also
a greatest common divisor of $S$.
(b) If both $d$ and $d'$ are greatest common divisors of $S$ then
$|d|=|d'|$.
In other words, the greatest common divisor is unique up to the sign.
13.48 Convention Let $S\subseteq\zzz$. If $d$ is a
greatest common divisor of $S$ then we write $\gcd(S)=|d|$.
This makes the gcd notation uniquely defined.
13.49 Example (Verify!) $\gcd(-36,60,-90)=6$.
13.50 DO Observe: if $S=\{a\}$ (so $|S|=1$) then $\gcd(S)=|a|$.
13.52 DO Prove: If $S\subseteq T\subseteq\zzz$ then $\gcd(T)\mid\gcd(S)$.
13.54 ORD (1+3 points) Determine (a) $\gcd(\zzz)$ (b) $\gcd(\emptyset)$.
13.56 HW
(a) ORD (2 points) Find three integers, $a,b,c$, such that
$\gcd(a,b,c)=1$ but no two of $a,b,c$ are relatively prime.
State the pairwise gcd's. No proofs required.
(b) Bonus (3 points) For every $n\ge 3$, find
a set $K$ of $n$ integers such that $\gcd(K)=1$ but
$(\forall a\in K)(\gcd(K\setminus\{a\})\neq 1)$.
13.58 Bonus (4 points) Determine $\gcd(p^2-1\mid p\ge 20$ is a prime number$)$.
13.65 DEF Let $d\in \nnn$ (i.e., $d$ is a positive integer).
The sequence $a_0, a_1, a_2, \dots$ is periodic with period $d$ if
$(\forall n\ge 0)(a_{n+d}=a_n)$.
Example: The sequence $1,2,5,1,2,5,1,2,5,\dots$ is periodic
with period 3.
13.67 DO If $d$ is a period of a sequence $S$ then every positive multiple of $d$ is also a period of $S$.
13.70 ORD (3 points) Prove: If $d$ and $e$ are periods of a sequence $S$ then $\gcd(d,e)$ is also a period.
13.72 DO Let $S$ be a periodic sequence and let $d$ be its shortest period. Then the set of periods of $S$ is $d\nnn$ (the set of positive multiples of $d$) (see Notation 10.75).
13.75 Bonus (4 points, due Nov 7) Let $0 < x < 1$ be a real number. Let $S$ denote the sequence of decimal digits of $x$ after the decimal point. Prove: if $S$ is periodic then $x$ is a rational number expressible as a fraction whose denominator is relatively prime to 10. (Example: $1/7=0.{\dot 1}4285{\dot 7}$ where the dots indicate the beginning and the end of the period -- this segment is then repeated indefinitely.)
13.77 Bonus (6 points, due Nov 7)
Prove the following partial converse to 13.75:
Let $p$ be a prime number, $p\nmid 10$. Prove that the sequence
of decimal digits of $1/p$ is periodic with period $p-1$.
(Note: $p-1$ is not necessarily the shortest period, but the
shortest period will be a divisor of $p-1$. Example:
$1/13=0.{\dot 0}7692{\dot 3}$. The shortest period is 6
and $6\mid 12 = 13-1$.)
13.79 Reward Prove the full converse of 13.75:
If $0 < x < 1$ is a rational number expressible
as a fraction whose denominator is relatively prime to 10 then
the sequence of decimal digits of $x$ is periodic.
You may use the Fermat-Euler congruence (a generalization
of Fermat's little Theorem) (look it up).
13.85 DEF We say that the sequence $a_0, a_1, a_2, \dots$ is eventually periodic with period $d\in\nnn$ if $(\exists n_0)(\forall n \ge n_0)(a_{n+d}=a_n)$.
13.87 Reward Let $0 < x < 1$. Prove: the sequence of decimal digits of $x$ is eventually periodic if and only if $x$ is a rational number.
13.90 DO Prove: if a geometric progression is periodic then its quotient is $\pm 1$.
13.92 Reward Find all periodic geometric progressions of complex numbers. Give a simple description of their quotients. (There are infinitely many possible quotients.)
13.100 ORD (1+1 points) ASY 1.3 (eventually zero/nonzero)
13.102 ORD (2 points) ASY 1.4 (negate "eventually nonzero")
13.104 ORD (3+1 points, due Nov 7) ASY 1.7 (infinite limits)
If you submitted this last week, please resubmit. (I forgot to state that
it was due Nov 7.)
13.106 DO ASY 1.13 (limit of subsequences)
13.108 ORD (3 points) ASY 1.15 (convergent $\Rightarrow$ bounded)
13.110 ORD (3 points) ASY 1.16 (bounded $\not\Rightarrow$ convergent)
13.112 ORD (2 poits) ASY 1.17 ($a_n$ divergent, $a_n^2$ convergent)
13.114 DO ASY 1.18, 1.19, 1.20 (constant sequence, dilation)
13.116 DO ASY 1.21, 1.22 (convergence vs. arithmetic)
13.118 DO ASY 1.23 (continuous function of convergent sequence)
13.120 DO ASY 1.25 (every increasing sequence has a limit)
13.125 HW ASY 1.27 (tower of $\sqrt{2}$'s)
(a) DO (b) ORD (3 points)
(c) DO (d) Reward.
13.127 Reward ASY 1.28 (tower of constant)
13.129 DO ASY 1.31 (Golden Ratio)
13.131 Bonus (4 points) ASY 1.32(a) (if Fibonacci quotients converge $\dots$)
13.133 Reward ASY 1.32(b) (Fibonacci quotients converge)
13.140 DO ASY 2.2 (multiplication, division of asymptotic equalities)
13.141 ORD (3 points) ASY 2.3(c) (a quotient of polynomials)
13.142 ORD (3 points) ASY 2.3(e) 13.143 DO ASY 2.5 (degree of polynomials)
13.144 DO ASY 2.6(a), (b), (c), ASY 2.6
13.146 Bonus (3 points) ASY 2.7(d) ($\sqrt{n^2+1}-n\sim 1/(2n)$)
13.148 ORD (3 points) ASY 2.8 ($a_n^n$)
13.150 ORD (3 points) ASY 2.10 ($\binom{2n}{n}$)
13.155 DO ASY 3.1--3.4 (basic properties of $\sim$)
13.157 HW (due Nov 7) ASY 3.4 (asympotic equality of sum) (a) ORD (3 points) (b) Bonus (3 points)
13.159 Bonus (3+3 points, due Nov 7) ASY 3.5 (asymptotic equality vs. logarithm)
13.161 DO ASY 3.7 (squeeze)
13.163 DO ASY 3.8(a)(b) (lower bound on $n!$ for all $n$, why not from Stirling's formula?)
13.164 DO ASY 3.8(c) (asymptotic lower bound on $n!$, from Stirling's formula)
13.165 HW (due Nov 7) ASY 3.9 (a) ORD (4 points) (b) Bonus (4 points) (asymptotics of $\ln(n!)$)
Class 12, Thu 10-20 Sequences, recurrence, geometric
progressions, explicit formula, Fibonacci sequence,
Fibonacci-type sequences. Binomial coefficients, Binomial Theorem,
indentities: combinatorial proof (counting sets),
algebra proof (using the Binomial Theorem)
All problems are due Oct 24, unless otherwise stated,
along with the problems from Class 10, and Bonus problem 9.108.
12.05 DEF We consider infinite sequences of numbers (integers, real numbers, complex numbers): $a_0, a_1, a_2,\dots$
12.10 DEF Geometric progression with quotient $q$:
$a_0, a_0q, a_0q^2,\dots$
Recurrence: $a_n = a_{n-1}q$ $(n\ge 1)$
Initial value: $a_0$
Explicit formula: $a_n = a_0q^n$
12.12 DO Prove the explicit formula for geometric progressions from the recurrence and the initial value.
12.15 DEF Fibonacci sequence:
$0,1,1,2,3,5,8,13,21,34,55,89,144,\dots$
Recurrence: $F_n = F_{n-1}+F_{n-2}$ $(n\ge 2)$
Initial values: $F_0=0$, $F_1=1$
12.18 ORD (5 points, due Oct 31) Prove: consecutive Fibonacci numbers are relatively prime. In other words, $(\forall n\ge 1)(\gcd(F_{n-1},F_n)=1)$
12.22 DEF We say that a sequence $g_0,g_1,g_2,\dots$ is a Fibonacci-type sequence if it satisfies the Fibonacci recurrence: $$ g_n = g_{n-1}+g_{n-2} \qquad (n\ge 2) $$ Example: $5, -2, 3, 1, 4, 5, 9, 14, 23, 37,\dots$
12.25 Bonus (5 points, due Oct 31) Find all Fibonacci-type geometric progressions with initial value $g_0=1$.
12.30 DO STUDY the Pascal Triangle.
12.32 DO REVIEW the combinatorial proof of Pascal's Identity (10.160) discussed in class (see the posted iPad class notes)
12.35 DO REVIEW the combinatorial proof of Vandermonde's Identity discussed in class (see iPad notes): $$ \sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n} $$
12.40 DO The Binomial Theorem expands the binomial $(x+y)^n$ : $$ (x+y)^n = \sum_{k=0}^n \binom{n}{k} x^ky^{n-k} $$ Prove by counting how many times we get $x^ky^{n-k}$ in the expansion of the product $\prod_{i=0}^n (x+y)$.
12.42 DO (simplified Binomial Theorem) The most useful special case of the Binomial Theorem: the case $y=1$: $$ (1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k $$
12.44 DO Recover the Binomial Theorem from its simplified version.
12.46 ORD (2 points) Expand the binomial $(1+x)^6$. You need to write explicit numbers rather than binomial coefficients.
12.48 DO Prove the following identity: $$ \sum_{k=0}^n \binom{n}{k} = 2^n \qquad (n\ge 0) $$ Give two proofs: (a) a combinatorial proof (b) an algebra proof (use the simplified Binomial Theorem)
12.50 NOTATIONAL trick We could also write $$ \sum_{k=0}^{\infty} \binom{n}{k} = 2^n \qquad (n\ge 0) $$ because all additional terms are $0$ (because $k > n$)
12.52 NOTATION (floor, ceiling) Let $x$ be a real number. Then
the floor of $x$, denoted $\lfloor x\rfloor$, is the
rounded-down value of $x$ (rounded down to the nearest
integer $\le x$). For example,
$\lfloor 3.2\rfloor = 3$, $\lfloor -3.2\rfloor = -4$,
$\lfloor 3\rfloor = 3$.
The ceiling of $x$, denoted $\lceil x\rceil$,
is its rounded-up value. For example,
$\lceil 3.2\rceil=4$, $\lceil -3.2\rceil = -3$,
$\lceil 3\rceil = 3$
12.55 NOTATION (local, i.e., just for this class)
$S(n,t) = \sum_{k=0}^{\infty} \binom{n}{kt}$.
Note that the right-hand side is a finite sum, the last non-zero term
corresponds to $k=\lfloor n/t\rfloor$, so we could have written
$S(n,t) = \sum_{k=0}^{\lfloor n/t \rfloor} \binom{n}{kt}$.
12.60 DO Review the two proofs (combinatorial, algebra) of
the following identity:
$$ S(n,2) = \begin{cases} 1 & n=0 \\
2^{n-1} & n\ge 1
\end{cases} $$
Solution. Note that
$S(n,2)=\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\dots$
counts the even subsets of $[n]$,
so in our previous notation (Ex. 6.82), $S(n,2)=E_n$; let
$O_n = \sum_{k=0}^{\infty} \binom{n}{2k+1}$ be the number of odd subsets.
Prove: (1) $O_n+E_n=2^n$ and
(2) $O_n-E_n= \begin{cases} 1 & n=0 \\
0 & n\ge 1
\end{cases} $
Adding these two identities we get the value of $2E_n$.
So the key is to prove (2). 6.82 suggests a combinatorial (bijective)
proof (for $n\ge 1$). In addition, give an algebra proof:
substitute $x=-1$ in the simplified Binomial Theorem (12.42).
12.65 DO $S(n,3)=\binom{n}{0}+\binom{n}{3}+\binom{n}{6}+\dots$
counts the subsets of which the size is divisible by $3$.
It would be natural to suggest that (for large $n$) this value is $2^n/3$.
Prove: this suggestion is always wrong:
$(\forall n)(S(n,3) \neq 2^n/3)$.
Proof The right-hand side is never an integer.
This follows from Euclid's Lemma (9.96): If $3$ divides
the product $2\cdot 2\cdot\ldots\cdot 2$ then it must divide
one of the terms of the product, but $3\nmid 2$.
12.68 Challenge Prove that the suggestion was nonetheless
pretty good:
$$(\forall n\ge 0)(|S(n,3)-2^n/3| < 1)$$
This result can be proved by clever, albeit somewhat tedious, induction.
There is also a strikingly elegant proof using complex numbers
(the "proof from the book").
12.75 ORD (4 points, due Oct 31) Let $p$ be a prime number and let $1\le k\le p-1$. Prove that $p\mid \binom{p}{k}$. Explicitly refer to Euclid's Lemma (9.96).
12.80 ORD (4 points, due Oct 31) Let $p$ be a prime number. Prove: $(a+b)^p\equiv a^p+b^p \pmod{p}$.
12.82 Bonus (4 points, due Oct 31) Let $p$ be a prime number. Prove: $a^p\equiv a \pmod{p}$. Use the preceding result. For $a\ge 0$ proceed by induction. Then extend the result to negative $a$.
12.84 Bonus (3 points, due Oct 31) Show that Fermat's little Theorem (2.72) follows from the preceding result.
12.88 Bonus (5 points, due Oct 31) Prove: if $\gcd(a,481)=1$ then $a^{36}\equiv 1 \pmod{481}$. $(481=13\cdot 37)$.
12.95 ORD (5 points, due Oct 31) Prove that the binomial coefficients increase until the middle and then decrease, i.e., if $1\le k\le n/2$ then $\binom{n}{k-1} < \binom{n}{k}$ and if $n\ge k\ge 1+n/2$ then $\binom{n}{k-1} > \binom{n}{k}$.
12.98 ORD (5 points, due Oct 31) Prove: If $1\le k\le n$ then $\displaystyle{\binom{n}{k}\ge \left(\frac{n}{k}\right)^k}$.
12.102 Bonus (4+1 points, due Oct 31)
(a) Prove:
$\displaystyle{(\forall k\ge 1)\left(k! >\left(\frac{k}{\eee}\right)^k\right)}$
Hint Use the power series expansion
$\eee^x = \sum_{i=0}^{\infty} \frac{x^i}{i!}$
(b) Why does this not follow from Stirling's formula (ASY 2.9)?
12.105 DO If $0\le k\le n$ then $\binom{n}{k} \le \frac{n^k}{k!}$
12.108 Bonus (4 points, due Oct 31) If $1\le k\le n$ then $\displaystyle{\binom{n}{k} < \left(\frac{\eee n}{k}\right)^k}$
12.110 Reward If $1\le k\le n$ then $$\sum_{j=0}^k \binom{n}{j} < \left(\frac{\eee n}{k}\right)^k$$
Class 11 (problem session), Wed 10-19
Class 10, Tue 10-18 Gcd definition, proof of existence
via Euclid's Algorithm, Bézout's Lemma. Counting permutations.
Uniform partitions, counting equivalence classes, counting
$k$-subsets of an $n$-set, binomial coefficients,
Newton's binomial coefficients. Complement, De Morgan's Laws,
Pascal's Triangle, symmetry of Pascal's Triangle,
Pascal's identity stated
All problems are due Oct 24, unless otherwise stated,
plus one problem from Class 9 (9.108 Bonus).
10.05 STUDY the "Euclid's algorithm and multiplicative inverse" handout. Click "Texts" on the banner. Make sure you open the latest version: under the title it should say "Last updated at 12:40pm on 10-19-2022." If you do not see "12:40pm" in this statement, refresh your browser; if this is not sufficient, clear your browser's cache or try another browser.
10.06 REFERENCE Below, "EUCL 2.6" refers to Exercise 2.6 in the "Euclid's algorithm and multiplicative inverse" handout.
10.08 CONVENTION In all problems related to divisibility and gcd, the universe is $\zzz$.
10.10 DO EUCL 1.2, 1.3, 1.4, 1.5 (basic properties of divisibility and the sets $\Div(a)$).
10.12 DO Carefully study EUCL 1.7 (def of "greatest common divisors"). Understand the statement that "the greatest common divisors of 30 and 78 are $\pm 6$."
10.14 DO Understand that the following two statements
are equivalent by EUCL Ex. 1.8 and EUCL Convention 1.9:
(a) The greatest common divisors of $a$ and $b$ are $d$ and $-d$.
(b) $\gcd(a,b)=|d|$.
10.16 DO Verify:
(a) $(\forall a)(\gcd(a,0)=|a|)$
with special attention to the case $a=0$: $\gcd(0,0)=0$
(b) $(\forall a)(\gcd(a,a)=|a|)$
10.20 ORD (4+4 points) EUCL 1.8:
$d$ is a greatest common divisor of $a$ and $b$ if and only if
$\Div(a,b)=\Div(d)$.
The problem requires to show the equivalence of this statement
to the definition given in EUCL, Def 1.7. Part (a) of this problem is to
show Def 1.7 $\Rightarrow$ $\Div(a,b)=\Div(d)$, part (b) is the converse.
Note that to prove that two sets, $A$ and $B$, are equal, you
need to show two facts: $A\subseteq B$ and $B\subseteq A$. So
part (a) of this exercise breaks into two parts: under the conditions
of EUCL 1.7, show that (a1) $\Div(a,b)\subseteq \Div(d)$ and
(a2) $\Div(d) \subseteq \Div(a,b)$.
In every part of your proof, clearly state, what are the assumptions,
what are the desired conclusions, and which of the two desired
conclusions you are proving.
10.25 ORD (Euclid's gcd Lemma, 5 points) EUCL 1.15: $\Div(a-b,b)=\Div(a,b)$
10.27 ORD (4 points) EUCL 1.16: $\Div(a-kb,b)=\Div(a,b)$
For $k\ge 0$, proof by induction -- on what parameter?
Make sure to state your inductive hypothesis.
10.29 ORD (Division Theorem, 4 points) EUCL 1.17
10.31 ORD (4 points) Study EUCL Notation 1.18.
Assume $b\neq 0$.
Prove: $r=(a \bmod b)$ if and only if $r\equiv a \pmod b$ and
$0\le r < |b|$.
In other words, $r$ is the smallest non-negative remainder
of $a$ modulo $b$.
10.33 ORD (2 points) Evaluate $(-117 \bmod{-19})$. Reason your answer using the preceding exercise.
10.40 Euclid's algorithm: sample run Let us use
Euclid's algorithm (as described in EUCL, Sec. 2) to calculate
$\gcd(-30,78)$. First we observe that $\gcd(-30,78)=\gcd(78,30)$.
Then the algorithm progresses in rounds, and each round produces
a pair $(A,B)$, starting with $(78,30)$:
$(78,30)$, $(30,18)$, $(18,12)$, $(12,6)$, $(6,0)$.
The conclusion is that $\gcd(-30,78)=6.$ We also say that
the algorithm runs in 4 rounds (4 transitions from a
pair $(A,B)$ to the next pair $(A,B)$), so altogether
we see 5 pairs $(A,B)$.
10.42 ORD (3 points) Describe the progress of the computation of $\gcd(56,-136)$ as above by listing the pairs $(A,B)$. State the number of rounds.
10.44 ORD (3 points) EUCL 2.1 (Euclid's algorithm terminates)
10.46 ORD (4 points) EUCL 2.2 (loop invariant)
10.48 Bonus (5 points) EUCL 2.3 (efficiency of Euclid's algorithm)
10.50 DO EUCL 2.5 (more efficient version of Euclid's algorithm)
10.52 ORD (4 points) EUCL 2.6 (Euclid's original gcd lemma)
Do not use Euclid's algorithm; use the key lemma lemma leading to
the algorithm.
10.54 ORD (3 points) Prove: if $a\equiv b\pmod m$ then $\gcd(a,m)=\gcd(b,m)$.
10.60 ORD (Bézout's Lemma, 5 points) EUCL 4.2--4.3 (Prove Bézout's Lemma by induction on $|a|+|b|$)
10.62 ORD (2+4 points) (a) Use Euclid's algorithm
to verify that $\gcd(80, 17)=1$. Describe the sequence
of applications of the Division Theorem, so each line
in your description should look like $A=Bq+R$, for instance,
$80=17\cdot 4+12$.
(b) Write 1 as a linear combination of 80 and 17. Follow the steps
of Euclid's algorithm in reverse. In each round, you represent 1 as
a linear combination of the current pair $(A,B)$. Describe each round.
10.64 Bonus (4 points) EUCL 4.4 (if a common divisor is a linear combination then it is a greatest common divisor)
10.66 STUDY the multiplicative inverse EUCL Sections 6, 7
10.68 ORD (5+3)
(a) Compute $(17^{-1} \bmod{80})$ using the method of EUCL Sec. 6.
(b) Use the result to write 1 as a linear combination of 80 and 17.
Do not use your work on 10.57b. This will give an alternative,
more transparent method to write $\gcd(a,b)$ as a linear combination
of $a$ and $b$.
10.70 Bonus (6+4 points) Let $a=5k+2$ and $b=17k+19$.
(a) Prove: for every $k\in\zzz$, $\gcd(a,b)\in\{1,61\}$.
(b) Find a value $k$ such that $\gcd(a,b)=61$.
There is a very elegant solution to part (a); elegance counts.
Hint: think linear combinations.
10.75 NOTATION (dilation) Let $A\subseteq\zzz$ and $k\in\zzz$. We write $kA = \{ka\mid a\in A\}$.
10.77 Example Let $A=\{-4,-1,0,7\}$. Then $-3A =\{12,3,0,-21\} = \{-21,0,3,12\}$.
10.79 WARNING Note that $2A$ is NOT the sumset $A+A$.
10.81 DO $2A\subseteq A+A$.
10.83 Reward Characterize the sets $A\subseteq\zzz$ that
satisfy $2A=A+A$. You need to prove: "$2A=A+A$ if and only if BLANK."
Fill in the BLANK with a very simple description of $A$.
Recall: "Reward problems" are between "DO" exercises and "Challenge problems"
in difficulty and status. No deadline, no point value. Let the instructor
know if you solved them.
10.85 DO $a\in k\zzz$ if and only if $k\mid a$.
10.88 NOTATION (shift) Let $A\subseteq\zzz$ and $\ell\in\zzz$.
We write $A+\ell = \{a+\ell\mid a\in A\}$.
Note that $A+\ell = A+\{\ell\}$ (using the sumset notation).
10.90 DO $m\zzz+k = m\zzz+\ell$ if and only if $k\equiv \ell \pmod{m}$.
10.92 DO Let $m\neq 0$. The mod $m$ residue classes are $m\zzz, m\zzz+1, \dots,m\zzz+(|m|-1)$.
10.94 Observation The set $a\zzz+b\zzz$ is the set of linear combinations of $a$ and $b$ (with integer coefficients).
10.96 ORD (6+2 points, due Oct 31)
(a) Describe the set $30\zzz+18\zzz$.
Give a very concise description using the notation above. You need
to use only 2 symbols to state the answer. Prove your answer.
(b) Give a concise description of the set $a\zzz+b\zzz$.
The proof should be analogous to the proof you gave in part (a),
no details are required.
10.100 DEF A permutation of a set $\Omega$ is a bijection $\pi:\Omega\to\Omega$.
10.102 DO If $|\Omega|=n$ then the number of permutations
of $\Omega$ is $n!$.
This is true for every $n\ge 0$, including $n=0$: the empty set has
1 permutation (the empty permutation), and $0!=1$ (the empty product).
10.104 REPRESENTATION. If $|\Omega|=n$ and $\pi$ is a
permutation of $\Omega$ then we can represent $\pi$
as a $2\times n$ matrix where the first row lists the elements
of $\Omega$ (in any order), and under each elements $x\in\Omega$,
we write $\pi(x)$. For instance, here are two representations
of the same permutation of $[6]$:
$$\begin{equation*}
\pi =
\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\
4 & 2 & 6 & 5 & 1 & 3
\end{pmatrix} =
\begin{pmatrix} 3 & 6 & 2 & 1 & 4 & 5 \\
6 & 3 & 2 & 4 & 5 & 1
\end{pmatrix}
\end{equation*}$$
Both matrices indicate that $\pi(1)=4$, $\pi(2)=2$, $\pi(3)=6$,
$\pi(4)=5$, $\pi(5)=1$, $\pi(6)=3$.
There are $n!$ equivalent representations, determined by the $n!$ orderings of the top row.
If $\Omega=[n]$ and we agree that the top row is arranged in its natural order (as in the first matrix) then it is sufficient to list the second row, which gives a linear order of the elements of $\Omega$. This establishes a bijection between the permutations and the linear orders of $\Omega$. With this convention we can write $$ \pi = [4\ \ 2\ \ 6\ \ 5\ \ 1\ \ 3]$$
10.125 DEF A $k$-permutation (also called a $k$-variation)
of a set $\Omega$ is an ordered list of $k$ distinct elements
of $\Omega$.
For instance, if $\Omega=[6]$ then $[5\ \ 2\ \ 6]$ is a 3-permutation
of $\Omega$.
10.128 TERMINOLOGY An $n$-set is a set of $n$ elements. A $k$-subset of a set $\Omega$ is a subset of size $k$.
10.130 DO The number of $k$-permutations of an $n$-set is $n(n-1)\cdot\ldots\cdot(n-k+1)$. Note that there are $k$ terms in this product.
10.132 DO The number of $k$-permutations of an $n$-set is equal to the number of injections $[k]\to [n]$.
10.135 NOTATION We denote the set of $k$-subsets of
$\Omega$ by $\binom{\Omega}{k}$. If $\Omega$ is an $n$-set then
we denote the cardinality of $\binom{\Omega}{k}$ by $\binom{n}{k}$.
So $\binom{n}{k}$ is the number of $k$-subsets of an $n$-set.
WARNING: $\binom{\Omega}{k}$ is a set and
$\binom{n}{k}$ is a number. The number $\binom{n}{k}$ is
called a binomial coefficient.
10.137 Example Let $\Omega=\{a,b,c,d\}$. Then
$\binom{\Omega}{2}=\{\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}\}$
and $\binom{4}{2}=6$.
10.139 DEF (set-subtraction) Let $A,B$ be sets. We define $A\setminus B :=\{x\in A\mid x\notin B\}$.
10.141 DEF (complement) Let $A\subseteq \Omega$. The complement of $A$ (with respect to $\Omega$) is the set $\Abar = \Omega\setminus A$.
10.143 DO (De Morgan's Laws) Let $A,B\subseteq\Omega$. Prove: $$\overline{A\cup B} = \Abar\cap \Bbar\quad \text{and}\quad \overline{A\cap B} = \Abar\cup \Bbar $$
10.145 DO (symmetry of the Pascal triangle)
For $0\le k\le n$ we have
$$\binom{n}{k} = \binom{n}{n-k}$$
Give a bijective proof (a bijection from $\binom{\Omega}{k}$
to $\binom{\Omega}{n-k}$).
Solution Map each $A\in\binom{\Omega}{k}$ to its
complement $\Abar = \Omega\setminus A$.
10.160 DO (Pascal's identity) For all $n,k \ge 0$ we have $$ \binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1} $$
10.165 DO For all $n,k\ge 0$ we have
$$\binom{n}{k}=\frac{n(n-1)\cdot\ldots\cdot(n-k+1)}{k!}
= \frac{\prod_{j=0}^{k-1}(n-j)}{k!}$$
This is true even if $k > n$: if $k > n$ then $\binom{n}{k}=0$
(because an $n$-set has no subsets of size greater than $n$),
and the formula of the right-hand side indeed gives $0$ because
one of the terms on the numerator will be $0$.
Sketch of proof. Let $P$ denote the set of
$k$-permutations of $\Omega$. So the numerator is $P$.
Let us define a function $f:P\to\binom{\Omega}{k}$ by
assigning to each $k$-permutation $\sigma$ the set of elements
of $\sigma$. For instance, if $\sigma = [5\ \ 2\ \ 6]$
then $f(\sigma)=\{2,5,6\}$. Let us make the following observations.
(1) $\binom{n}{k}=|\ker(f)|$.
(2) Each block of the partition $\ker(f)$ has the same size,
namely, $k!$.
(3) Therefore the number of blocks is $|P|/k!$, as claimed.
10.167 DO Verify: $\binom{n}{0}=\binom{n}{n}=1$, $\binom{n}{1}=\binom{n}{n-1}=n$, $\binom{n}{2}=\binom{n}{n-2}=\frac{n(n-1)}{2}$, $\binom{n}{3}=\frac{n(n-1)(n-2)}{6}$.
10.169 DO For $0\le k\le n$ we have $$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $$ Note that for small values of $k$, the formula in 10.165 is much more convenient that this formula.
10.172 DEF (Newton's binomial coefficients) A further advantage of the formula in 10.165 is that it makes sense for any real or complex value of $n$, as long as $k$ is a non-negative integer. For $x\in\rrr$ (or $x\in\ccc$) we define $$\binom{x}{k}=\frac{x(x-1)\cdot\ldots\cdot(x-k+1)}{k!} = \frac{\prod_{j=0}^{k-1}(x-j)}{k!}$$
10.174 Examples $$\binom{x}{2}=\frac{x(x-1)}{2}.\quad\text{ For instance}\quad \binom{1+i}{2}=\frac{(1+i)i}{2}=\frac{i-1}{2}=-\frac{1}{2}+\frac{1}{2}i \quad\text{ where }\quad i^2 = -1$$
10.176 HW Let $k\in\nnn_0$ (non-negative integer).
(a) ORD (4 points, due Oct 31)
Compute $\binom{-1}{k}$. Your answer should
be a very simple closed-form expression.
(b) Bonus (5 points, due Oct 31) Prove:
$$ \binom{-1/2}{k} = \frac{(-1)^k}{4^k}\binom{2k}{k}$$
10.177 ORD (5 points, due Oct 31) Let $0\le k\le \ell$ be integers. Prove the following identity by induction on $\ell-k$. $$\sum_{n=k}^{\ell} \binom{n}{k}=\binom{\ell+1}{k+1}$$
More to follow. Please check back later. Please report any errors.
Class 9, Thu 10-13 Summation and product symbols,
empty sum, empty product. Set of common divisors,
gcd definition, Euclid's Lemma stated, Fundamental
Theorem of Arithmetic stated
All problems are due Oct 17, unless otherwise stated,
plus some problems from Class 7.
In the exercises below, $\Omega$ is always a finite set.
9.10 DEF Summation symbol. Let $f:\Omega\to\rrr$ be a function, where $\Omega$ is a finite set. We write $\sum_{x\in\Omega} f(x)$ to denote the sum of the values of $f$ for all elements of $\Omega$. So if $\Omega=\{a_1,\dots,a_n\}$ then $$\sum_{x\in\Omega} f(x) = f(a_1)+\dots+f(a_n)\,.$$ We shall refer to $\Omega$ as the domain of the summation.
9.12 CONVENTION $\sum_{x\in\emptyset} f(x) = 0$ (the empty sum is zero)
9.13 DO $\sum_{x\in\Omega} 1 = |\Omega|$.
(Here we are summing the constant function $f(x)=1$.)
9.14 DO Prove: If $A,B$ are disjoint finite sets and $\Omega=A\dot\cup B$ then $$\sum_{x\in\Omega} f(x) = \sum_{x\in A} f(x) +\sum_{x\in B} f(x)\,.$$ Observe that the proof requires Convention 9.12. This shows that 9.12 is the only reasonable way to define the empty sum.
9.15 DO Prove: If $A,B$ are finite sets and $\Omega=A\cup B$ then $$\sum_{x\in\Omega} f(x) = \sum_{x\in A} f(x) +\sum_{x\in B} f(x)$$ holds if and only if $\sum_{x\in A\cap B} f(x) = 0$.
9.16 NOTATION $\sum_{i=1}^k f(i) :=\sum_{i\in [k]} f(i)$.
9.18 DO Let $h_1(n)=\sum_{i=1}^n i$. So for instance $h_1(4)=1+2+3+4=10$. Give a simple closed-form expression for $h_1(n)$ (no summation signs, no dot-dot-dots).
9.20 DO Let $h_k(n)=\sum_{i=1}^n i^k$. So for instance
$h_3(4)=1^3+2^3+3^3+4^3 = 100$.
(a) Prove: $h_2(n) = n(n+1)(2n+1)/6$.
(b) Prove: $h_3(n) = (h_1(n))^2$.
9.22 NOTATION
$$\sum_{1\le i\le j\le n} f(i,j) := \sum_{(i,j)\in \Delta} f(i,j)$$
where $\Delta=\{(i,j)\mid 1\le i\le j\le n\}$.
More generally, what we write under the summation sign should
specify the domain of the summation.
9.24 ORD (3 points) Determine $\sum_{1\le i\le j\le n} 1$.
Your answer should be a simple closed-form expression. Reason your answer.
9.26 Bonus (3 points) Determine $\sum_{1\le i\le j\le n} j$.
Your answer should be a simple closed-form expression. Reason your answer.
You may use any exercises, including DO exercises above and from earlier
classes.
9.28 DO Prove: $$\left(\sum_{i=1}^n a_i\right)^2 = \sum_{i=1}^n a_i^2 + 2\cdot\sum_{1\le i < j \le n} a_ia_j\,.$$
9.30 DO$^*$ (Cauchy--Schwarz inequality: the most important
inequality in mathematics)
Let $f,g : \Omega\to\rrr$ be functions. Then
$$\left(\sum_{x\in\Omega} f(x)^2\right)\cdot
\left(\sum_{x\in\Omega} g(x)^2\right) \ge
\left(\sum_{x\in\Omega} f(x)\cdot g(x)\right)^2\,.$$
9.33 DO Let $\Pi=\{B_1,\dots,B_k\}$ be a partition of the
finite set $\Omega$. Observe:
$$\sum_{x\in\Omega} f(x) = \sum_{i=1}^k \sum_{x\in B_i} f(x)\,.$$
9.35 DO Let $\Pi=\{B_1,\dots,B_k\}$ be a partition of the finite set $\Omega$. Verify: $$ |\Omega| = \sum_{i=1}^k |B_i|\,. $$ Show that this is an immediate consequence of the preceding exercise.
9.37 DEF Product symbol. Let $f:\Omega\to\rrr$ be a function, where $\Omega$ is a finite set. We write $\prod_{x\in\Omega} f(x)$ to denote the product of the values of $f$ for all elements of $\Omega$. So if $\Omega=\{a_1,\dots,a_n\}$ then $$\prod_{x\in\Omega} f(x) = f(a_1)\cdot\ldots\cdot f(a_n)\,.$$ We shall refer to $\Omega$ as the domain of the product.
9.38 CONVENTION $\prod_{x\in\emptyset} f(x) = 1$ (the empty product is 1)
9.39 DO Observe the following special cases of this convention: $0!=1$, and $(\forall a\in\rrr)(a^0=1)$. In particular, $0^0=1$.
9.41 OBSERVE: This convention is consistent with our counting result that $\left|B^A\right|=|B|^{|A|}$ since the set $\emptyset^{\emptyset}$ contains exactly one function (the empty function). (See Notation 6.25.)
9.43 DO Prove: If $A,B$ are disjoint finite sets and $\Omega=A\dot\cup B$ then $$\prod_{x\in\Omega} f(x) = \left(\prod_{x\in A} f(x)\right)\cdot\left(\prod_{x\in B} f(x)\right)\,.$$ Observe that the proof requires Convention 9.38. This shows that Convention 9.38 is the only reasonable way to define the empty product.
9.45 DO Define/verify the product version of item 9.33.
9.47 DO Let $f:\Omega \to \rrr^+$ be a function that takes positive values. Let $b > 0, b\neq 1$. Observe: $$ \log_b \left(\prod_{x\in\Omega} f(x)\right) = \sum_{x\in\Omega} \log_b(f(x))\,.$$ Observe that this exercise requires both conventions 9.12 and 9.38. In other words, if we wish this exercise to hold for $\Omega=\emptyset$ then these two conventions are equivalent (each follows from the other).
9.50 HW (a) DO Prove:
$$ \prod_{i=1}^n (1+x_i) = \sum_{I\subseteq [n]} \prod_{i\in I} x_i\,.$$
(b) ORD (2 points) What is the number of terms of the sum on
the right-hand side? Reason your answer.
(c) ORD (3 points) Expand this identity for $n=2$ and $n=3$
to closed-form expressions (no summation symbols, no dot-dot-dots).
(d) ORD (2 points) Explain the role of Convention 9.38 in this identity.
(e) Bonus (3 points) State the analogous identity for the expression
$$ \prod_{i=1}^n (1-x_i)\,.$$
Give a very short proof of your answer, based on part (a).
9.52 DO Prove that the number of terms in the sum $\sum_{1\le i\le j\le n} a_ia_j $ is $n(n+1)/2$.
9.53 Bonus (5 points) Prove that the number of terms in the sum $\sum_{1\le i\le j\le k\le n} a_ia_ja_k $ is $n(n+1)(n+2)/6$.
9.55 DO Let $|\Omega|=n$. Prove: $\sum_{B\subseteq \Omega} 1 = 2^n$.
9.57 Bonus (5 points) Let $|\Omega|=n$. Determine
$\sum_{B\subseteq \Omega} |B|\,.$
Your answer should be a simple closed-form expression in terms of $n$.
9.70 DEF $\Div(a)=\{b\,:\, b\mid a\}$ denotes the set of divisors of $a$.
9.72 Examples (verify!) $\Div(6)=\{\pm1,\pm2,\pm3,\pm 6\}$,
so $|\Div(6)|=8$
$\Div(5) =\{\pm 1, \pm 5\}$, $\Div(1)=\{\pm 1\}$,
$\Div(0) = \zzz$ (the set of integers)
9.74 DO $\Div(-a) = \Div(a)\,.$
9.76 DO $\Div(a) = \Div(b) \Leftrightarrow a\mid b \wedge b\mid a \Leftrightarrow a = \pm b \Leftrightarrow |a|=|b|\,.$
9.80 DEF $p\in \zzz$ is a prime number if $b\ge 1$ and $|\Div(p)|=4$.
9.82 DO The integer $p$ is a prime number if and only if $p\ge 2$ and the only positive divisors of $p$ are $1$ and $p$.
9.84 Examples The smallest prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, $\dots$
9.86 DEF Let $n\ge 1$. A prime factorization of $n$ is a list of prime numbers, $p_1,\dots,p_k$, such that $n=\prod_{i=1}^k p_i\,.$
9.88 Examples $12=3\cdot 2\cdot 2=2\cdot 3\cdot 2=2\cdot 2\cdot 3$ are the three prime factorizations of $12$.
9.90 Observation $1 = \prod_{i\in\emptyset} p_i$ is the prime factorization of the number $1$.
9.92 ORD (4 points) Prove that every natural number (positive integer) has a prime factorization. Prove by induction.
9.94 FUNDAMENTAL THEOREM OF ARITHMETIC (uniqueness of prime
factorization, Euclid, cca. 300 BCE)
The prime factorization of each positive integer is unique up to
the order of the factors.
9.96 Euclid's Lemma The following result is at the heart
of the proof of the Fund. Thm. of Arithmetic.
If $p$ is a prime number and $p\mid ab$ then $p\mid a$ or $p\mid b$.
9.98 COMMENT. The proof of Euclid's Lemma is nontrivial and will follow from the study of the greatest common divisiors and specifically from a result called "Bezout's Lemma."
9.100 DEF Let $n\ge 1$. We say that $n$ is a composite number if $n\neq 1$ and $n$ is not a prime number.
9.102 DO Let $n$ be an integer.
Prove that the following three statements are equivalent.
(a) $n$ is composite.
(b) $n\ge 1$ and $|\Div(n)| > 4$.
(c) $n\ge 1$ and $(\exists a,b)(a,b \ge 2 \wedge n=ab)$.
9.104 Examples The smallest composite numbers are 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, $\dots$.
9.106 ORD (3 points) Prove that the following statement is false
for every composite number $n$:
"If $n \mid ab$ then $n\mid a$ or $n\mid b$."
9.108 Bonus (4 points, due Oct 24) Prove that the FTA (Fund. Thm. of Arithm.) follows from Euclid's Lemma. Prove this by induction on $n$ where $n$ is the number to be factored.
Class 8 (problem session), Wed 10-12
Class 7, Tue 10-11 Trichotomous relations, linear orders
(read below; not discussed in class). Equivalence relations, partitions.
Proof of the Fundamental Theorem of Equivalence Relations (outline).
Equivalence classes. Residue classes mod $m$ (see below).
Greatest common divisor (first attempt at definition)
All homework problems are due Monday, October 17, 23:00, except where
otherwise stated, along with some problems from Class 6.
7.10 DEF A relation $R\subseteq\Omega\times\Omega$ is trichotomous if $(\forall a,b\in\Omega)($ exactly one of the following holds: $aRb$, $a=b$, $bRa)$.
7.12 DO If $R$ is trichotomous then $R$ is irreflexive.
7.14 EXAMPLE The order relation "$<$" on $\zzz$ is trichotomous. The same is true on $\qqq$ and $\rrr$.
7.16 DEF A linear order on $\Omega$ is a transitive trichotomous relation on $\Omega$.
7.18 EXAMPLE The order relation on $\zzz$ is a linear order. The same is true on $\qqq$ and $\rrr$.
7.20 ORD (3 points) Find a set $\Omega$ and a relation $R$ on $\Omega$ such that $R$ is trichotomous but not a linear order. Find the smallest $\Omega$ on which this is possible. You do not need to prove that it is smallest or that it is trichotomous but prove that it is not transitive.
7.22 ORD (3 points) Let $|\Omega|=n$ and let $R$ be a trichotomous relation on $\Omega$. Determine $|R|$ as a (simple) function of $n$. Reason your answer.
7.25 ORD (4 points) Let $|\Omega|=n$. Count the trichotomous relations on $\Omega$. Your answer should be a simple formula in terms of $n$. Briefly reason your answer.
7.27 ORD (3+4 points) (a) List all linear order relations on $[n]$ for $n=0,1,2,3$. (b) Count the linear order relations on $[n]$ for all $n$. Your answer should be a simple formula in terms of $n$. Briefly reason your answer.
7.29 HW Let $|\Omega|=n\ge 2$. Let $T(n)$ denote
the number of transitive relations on $\Omega$.
(a) ORD (4 points) Determine $T(2)$.
(b) Bonus (6 points) Prove: $T(n) > 2^{n^2/4}$.
The proof should be simple. Simplicity counts.
7.35 Challenge ("there is some order in every disorder") Let $|\Omega|=n\ge 1$. Let $R$ be a trichotomous relation on $\Omega$. Prove that there exists a subset $\Delta\subseteq \Omega$ such that (a) $R\cap (\Delta\times \Delta)$ (the restriction of $R$ to $\Delta$) is a linear order of $\Delta$ and (b) $|\Delta| \ge \lceil \log_2(n+1)\rceil$.
7.38 Recall that a partition $\Pi=\{A_1,\dots,A_k\}$
of $\Omega$ determines an equivalence relation $\sim_{\Pi}$ on $\Omega$,
defined as follows:
7.40
Recall the
Fundamental Theorem of Equivalence Relations (6.150)
Let $R$ be an equivalence relation on the set $\Omega$. Then $R$
arises from a partition. In other words,
$(\exists\text{ partition }\Pi\text{ of }\Omega)(R = \sim_{\Pi})$.
7.42 DEF We call the blocks of $\Pi$ the equivalence classes of $R$.
7.45 PROOF of the Fundamental Theorem of Equivalence Relations.
For $a\in \Omega$ let $[a]=\{b\in \Omega\mid aRb\}$.
We refer to this as the "candidate equivalence class of $a$."
We need to prove that the candidate equivalence classes partition $\Omega$,
i.e., $\Psi=\{[a] \mid a\in \Omega\}$ is a partition of $\Omega$,
and that $R=\sim_{\Psi}$. The proof proceeds by a series of observations.
Each observation needs to be supported by properties of the equivalence
relation $R$.
We need to show that
7.45(a) $(\forall a\in\Omega)([a]\subseteq\Omega)$
7.45(b) $(\forall a\in\Omega)([a]\neq\emptyset)$
Prove this by showing that
7.45(b1) $(\forall a\in\Omega)(a\in [a])$ (use reflexivity of $R$)
7.45(c) $(\forall a,b\in\Omega)([a]=[b] \vee [a]\cap [b]=\emptyset)$
7.45(d) $\bigcup_{a\in \Omega} [a]=\Omega$ (from (a) and (b1))
7.47 DO Prove 7.45(a),(b1),(b),(d). At each step, state what property of the equivalence relation $R$ you are using and/or what already proven property of the candidate equivalence classes you are using.
7.50 ORD (7 points) Prove 7.45(c). You may use 7.45(a),(b),(b1),(d). At each step, state what you are using (either a property of the equivalence relation $R$ (reflexivity, etc.) or an already proven property of the candidate equivalence classes (such as (b1)). Break your proof into a sequence of smaller observations (claims), and refer to them when you use them.
7.55 DEF The equivalence classes of congruence modulo $m$ are called mod $m$ residue classes.
7.57 ORD (2+2+2+2 points) (a) Describe the mod 2 residue classes in plain English with very few words. Count the residue classes you got. (b) Describe the mod (-3) residue classes by listing their nine or ten elements nearest to zero. Count the residue classes you got. (c) Give a simple description the mod 1 residue classes. Count the residue classes you got. (d) Describe the mod 0 residue classes. Use the set-maker notation. Count the residue classes you got.
More to follow. Please check back later. Please report any errors.
Class 6, Thu 10-6 Functions, injective and surjective fuctions.
The Pigeon Hole Principle. Counting injections.
Equivalence relations, partitions.
All homework problems are due Monday, October 10, 23:00, except where
otherwise stated, along with the problems from Class 4.
Read all material below carefully,
the notes include some definitions and notation not discussed in class.
In particular, the $B^A$ notation for the set of $A\to B$ functions
is explained below (6.25). Also, collisions are formally defined below.
6.10 DEF Let $R\subseteq A\times B$ be a relation from the set
$A$ to the set $B$. We can represent $R$ as a diagram where an arrow
$a\to b$ represents the membership $(a,b)\in R$. (See NOTES.)
We define the opposite (or reverse) of $R$ by reversing all
the arrows: $R^{\op}=\{(b,a) \mid (a,b)\in R\} \subseteq B\times A$.
Note that $\domain(R^{\op})=B=\codomain(R)$ and $\codomain(R^{\op})=A=
\domain(R)$.
6.15 DEF Let $A$ and $B$ be sets. A function $f:A\to B$ is a relation with domain $A$ and codomain $B$, with the following property:
6.16 NOTE ON TERMINOLOGY. The term "unique" means there is only one. This is the traditional meaning of this term in mathematics. For instance, we talk about unique prime factorization of positive integers, meaning they have only one prime factorization (if we write the factors in non-decreasing order). We say that a differential equation has a unique solution if there is only one function that satisfies the equation. This usage differs from recently introduced usage in Computer Science and commerce where one talks about "unique members of a list" (unique callers, unique customers) meaning the distinct members of the list. "Distinct" is the traditional term for this concept, and this is the term we shall use in this course. So we shall say that the list $[a,c,b,c,a]$ has three distinct members, namely $\{a,b,c\}$ (instead of "three unique members"). The element distinctness problem is the algorithmic problem that asks to determine whether all elements of a list are distinct.
6.18 DO Prove that a relation $f\subseteq A\times B$ is a
function if and only if it satisfies the following two conditions:
(a) $(\forall a\in A)(\exists b\in B)((a,b)\in f)$
(b) $(\forall a\in A)(\forall b_1, b_2\in B)
((a,b_1)\in f \wedge (a,b_2)\in f) \Rightarrow (b_1=b_2))$
6.24 DO
Consider the following relations between the sets $[5]$ and $[3]$.
(a) $R=\{(1,3), (4,1), (3,1), (5,3), (2,1)\}$
(b) $S=\{(1,3), (4,1), (5,3), (2,1)\}$
(c) $T=\{(1,3), (4,1), (5,3), (1,2), (3,1), (2,2)\}$
(d) $U=\{(1,3), (4,1), (5,3), (1,2), (2,2)\}$
Prove that $R$ is a function but $S,T,U$ are not functions.
For each of $S,T,U$ determine, which of the two conditions in
Exercise 6.18 are violated.
6.25 NOTATION. We denote the set of functions $f: A\to B$ by $B^A$. So $B^A$ is the set of those functions of which the domain is $A$ and the codomain is $B$. WARNING: The domain goes into the exponent, the codomain in the base! There is a reason for this; see the next exercise.
6.27 DO Let $A,B$ be finite sets, $|A|=k$, $|B|=\ell$.
Prove: $\left|B^A\right|=\ell^k$.
In other words, $\left|B^A\right|=|B|^{|A|}$, explaining
the $B^A$ notation.
So, for instance, the number of functions $[n]\to [3]$ is $3^n$.
This function grows exponentially as a functions of $n$.
On the other hand, the number of functions $[3]\to [n]$ is $n^3$.
This function grows polynomially as a functions of $n$.
We shall study rates of growth later.
Hint Show that $|B^A|$ is the same as the number of
strings of length $k$ over the alphabet $B$. (Represent the functions
$A\to B$ as a table with two columns: the first column lists the
elements of the domain $A$, the second column the corresponding values
of $f$. So each row of the table is of the form $(x,f(x))$ where $x\in A$.)
6.28 DEF The range of the function $f\in B^A$
is the set $\range(f)=\{f(x)\mid x\in A\}$.
6.29 DEF Let $f\in B^A$. Prove: $(\forall y\in B)(y\in\range(f) \Leftrightarrow (\exists x\in A)(y=f(x)))$
6.30 DO For all function $f$ we have $|\range(f)| \le |\domain(f)|$.
6.32 DEF Let $f\in B^A$ be a function. Let $a_1, a_2\in A$, $a_1\neq a_2$. We say that $a_1$ and $a_2$ collide if $f(a_1)=f(a_2)$. In this case, we call the unordered pair $\{a_1,a_2\}$ a collision. Let us write $\coll(f)$ for the number of collisions of $f$.
6.33 DO Let $f\in B^A$ be a function. Let $|A|=n$. (a) Prove: $\coll(f)\le n(n-1)/2$. (b) Prove that $\coll(f)=n(n-1)/2$ if and only if $f$ is a constant function, i.e., $(\exists b\in B)(\forall a\in A)(f(a)=b)$.
6.38 DEF We call the function $f:A\to B$ an injection or an injective function if $\coll(f)=0$ (there are no collisions).
6.40 DO Observe: the function $f\in B^A$ is injective if and only if $(\forall x,y\in A)(f(x)=f(y) \Rightarrow x=y)$.
6.42 DO Observe: there exists an $A\to B$ injection if and only if $|B| \ge |A|$. The "only if" part is a famous principle we state next.
6.44 Pigeonhole principle If $|A| > |B|$ and $f\in B^A$ then $\coll(f)\ge 1$ ($f$ is not injective).
6.46 Bonus (7 points, due Oct 17) Let $n\ge 1$ and let $S\subseteq [2n]$ be a subset of size $|S|\ge n+1$. Prove: $(\exists a,b\in S)(a\neq b$ and $a\mid b)$.
6.47 ORD (4 points) Prove that in the previous exercise,
the lower bound $|S|\ge n+1$ is tight for every $n\ge 1$,
i.e., the conclusion fails if we permit $S$ to have $n$ elements.
So what you need to do is the following. For every $n\ge 1$, find a subset
$T_n\subseteq [2n]$ such that $|T_n|=n$ and
$(\forall a,b\in T_n)(a\mid b \Rightarrow a=b)$.
6.50 DO Let $|A|=k$ and $|B|=\ell$.
Count the $A\to B$ injections.
Show that the number of $A\to B$ injections is
$$ \ell(\ell-1)\cdots(\ell-k+1)\,.
\qquad\qquad\qquad\qquad\qquad (*)$$
Note that this product has $k$ terms.
Formula $(*)$ is valid even if $\ell < k$, in which case the
number of injections is zero. Indeed, if $\ell < k$, then one
of the terms in $(*)$ will be zero. (DO: Verify!)
6.51 DO Let $|A|=k$ and $|B|=\ell$. Assume $\ell \ge k$.
Prove that the number of $A\to B$ injections is $\frac{\ell!}{(\ell-k)!}$.
Note that this formula makes no sense if $\ell < k$ because the
denominator will be the factorial of a negative number which is
undefined.
Expression $(*)$ is also preferable to the expression $\ell!/(\ell-k)!$
when $k$ is small compared to $\ell$ because the product $(*)$ has
only $k$ terms while this factorial quotient has a total of $2\ell-k$
terms.
6.55 DEF We call the function $f:A\to B$ a
surjection or a surjective function if
$\range(f) = \codomain(f)$.
In this case we say that $f$ maps $A$ onto $B$.
6.57 DO Observe that the function $f\in B^A$ is surjective if and only if $(\forall b\in B)(\exists a\in A)(f(a)=b)$. In other words, all elements of $B$ occur as values of $f$.
6.59 FACT If $f\in B^A$ is surjective then $|B|\le |A|$.
6.65 DEF A function $f\in B^A$ is called a bijection if $f$ is both injective and surjective.
6.68 DO Prove: the function $f:A\to B$ is a bijection if and only if its converse $f^{\op}$ (see Ex. 2.28) is also a function. In this case we call $f^{\op}$ the inverse of $f$ and denote it by $f^{-1}$.
6.70 ORD (3 points) Find a bijection from the set $\rrr^+$ (positive real numbers) to the real numbers in the open interval $(0,1)$. Describe your bijection with a simple formula. Argue that your function is bijective by stating its inverse. You are not required to prove that your stated inverse is indeed the inverse. The entire solution should fit on two lines.
6.75 DO Let $A,B$ be finite sets. A bijection $A\to B$ exists if and only if $|A|=|B|$.
6.77 TERMINOLOGY Often we are given two sets, $A$ and $B$,
and we are asked to prove that $|A|=|B|$. According to the preceding
exercise, one way to prove this is by constructing a bijection from
$A$ to $B$. We refer to this method as a bijective proof.
Sometimes we need to prove that $|A|\le |B|$. We can prove this by
finding an $A\to B$ injection (injective proof) or
by finding a $B\to A$ surjection (surjective proof).
We shall see examples of these methods below.
6.80 ORD (3 points) Let $A$ be a finite set.
Recall that $\calP(A)$ denotes the powerset of the set $A$
(the set of all subsets of $A$). Prove:
$|\calP(A)|=2^n$. Give a bijective proof: construct a simple
bijection from $\calP(A)$ to $\{0,1\}^n$ (the set of strings
of length $n$ over the alphabet $\{0,1\}$.
Argue that your function is bijective by stating its inverse.
You are not required to prove that your stated inverse is indeed
the inverse. Since we already know that $|\{0,1\}^n|=2^n$
(Ex. 4.56), the desired conclusion follows.
[A non-bijective proof will earn you $\le 1$ point.]
6.82 ORD (6 points, due Oct 17)
Let $O_n$ denote the set of odd subsets of $[n]$
(subsets of odd size), and $E_n$ the set of even subsets of $[n]$.
Claim. $|O_n|=|E_n|$ unless $n$ is [BLANK]. (Fill the blank;
there is just one exception.) State the values of $|O_n|$ and $|E_n|$
in the exceptional case. For all other cases, give a simple bijective
proof by constructing a bijection $f_n: O_n\to E_n$.
Argue that your function is bijective by stating its inverse.
You do not need to prove that your stated inverse is indeed the inverse.
The definition of $f_n$ should be very simple. Elegance counts.
6.85 DO Count the $[n]\to [2]$ surjections. Your answer should be a closed-form expression (no summation sign of dot-dot-dots). Briefly reason your answer. (Done in class.)
6.88 Bonus (6 points, due Oct 17) Count the $[n]\to [3]$ surjections. Your answer should be a simple closed-form expression (no summation sign or dot-dot-dots). Prove your answer.
6.90 DEF We say that the sets $A$ and $B$ are disjoint if $A\cap B=\emptyset$. We say that the sets $A_1,\dots,A_k$ are disjoint if they are pairwise disjoint, i.e., for every $i\neq j$ we have $A_i\cap A_j=\emptyset$. A disjoint union is the union of disjoint sets. A disjoint union is indicated by a dot on top of the union sign: $A_1\dot\cup A_2\dot\cup\dots\dot\cup A_k$.
6.91 DEF A partition of a set $\Omega$ is a representation of $\Omega$ as the union of non-empty disjoint sets. We write $\Pi=\{A_1,\dots,A_k\}$ for the partition $\Omega=A_1\dot\cup\dots\dot\cup A_k$ where the dots indicate that these sets are pairwise disjoint. The $A_i$ are called the blocks of $\Pi$.
6.92 Example The set $[3]$ has 5 partitions: $\Pi_1=\{\{1,2,3\}\}$, $\Pi_2=\{\{1,2\},\{3\}\}$, $\Pi_3=\{\{1,3\},\{2\}\}$, $\Pi_4=\{\{2,3\},\{1\}\}$, $\Pi_5=\{\{1\},\{2\},\{3\}\}$.
6.94 DEF The $n$-th Bell number $B_n$ is defined as the number of partitions of $[n]$.
6.95 DO Verify: $B_0=1$, $B_1=1$, $B_2=2$, $B_3=5$.
6.96 ORD (5 points, due Oct 17) Prove: $B_n\le n^n\,.$ Give a very simple surjective solution: find a surjection that maps the set $[n]^{[n]}$ (the set of $[n]\to [n]$ functions, see Notation 6.25) onto the set of partitions of $[n]$. Give a clear definition of your surjection. Do not prove that it is indeed a surjection.
6.97 Bonus (6 points, due Oct 17)
Prove: $B_n\le n!$
Find an injective solution: give an injection from the set of
partitions of $[n]$ to the set of permutations of $[n]$.
(A permutation of a set $A$ is an $A\to A$ bijection.)
Give a clear definition of your injection. Do not prove
that it is indeed an injection.
A solution to this problem does not earn you credit for 6.96; you
need to separately execute the instruction in 6.96 to earn credit
for that problem.
6.98 Bonus (6 points, due Oct 17) Prove: If $0\le k\le n$ then $B_n \ge k^{n-k}$. Give an injective solution: construct an injection from the set $[k]^{[n-k]}$ to the set of partitions. What you need to do is assign a partition to each function $f:[n-k]\to [k]$ such that distinct functions do not collide (they are not assigned the same partition). Give a clear definition of your injection. Do not prove that it is indeed an injection.
6.100 DEF Let $f:A\to B$ be a function. The preimage
of $b\in B$ is the set $f^{-1}(b) :=\{a\in A \mid f(a)=b\}$.
Example: Let $g:\rrr\to\rrr$ denote the function $g(x)=x^2$.
Then $g^{-1}(4)=\{-2,2\}$, $g^{-1}(0)=\{0\}$,
$g^{-1}(-1)=\emptyset$.
6.102 DO
Let $f:\Omega\to\Gamma$ be a function and $b\in\Gamma$. Observe
that $f^{-1}(b)\neq\emptyset$ if and only if $b\in\range(f)$.
"Observe" means
"notice that it follows immediately from the definition."
6.105 DEF (Kernel of a function) Let $\Omega$ and $\Gamma$ be sets. A function $f:\Omega\to\Gamma$ defines a partition $\Pi_f$ of the domain of $f$ as follows: $$\Pi_f = \{f^{-1}(b)\mid b\in \range(f)\}$$ The partition $\Pi_f$ is called the kernel of the function $f$.
6.108 DO Show that in the preceding exercise, $\Pi_f$ is indeed a partition of $\Omega$.
6.110 Example Consider a set $\Omega$ of bright-colored plastic toy bears. (Each bear has just one color.) Let $\Gamma$ be the set of colors. Let $f:\Omega\to\Gamma$ be the function that assigns its color to each bear, so $f(x)=$BLUE means bear $x$ is BLUE. Observe that the kernel of $f$ groups the bears by color.
6.112 ORD (2+3+1+1 points) Consider the function $f:[30]\to \nnn_0$ which, to every integer $x\in [30]$, assigns the number of (not necessarily distinct) prime factors of $x$. For instance, $12=2\cdot 2\cdot 3$ and therefore $f(12)=3$. State (a) the range and (b) the kernel of $f$. State the sets (c) $f^{-1}(3)$ and (d) $f^{-1}(5)$. Just give the answers, no proof required.
6.115 ORD (4 points, due Oct 17) Prove that every partition is the kernel of some function. More formally, prove the following. Given a partition $\Pi$ of the set $\Omega$, there exists a set $\Gamma$ and a function $f:\Omega\to\Gamma$ such that $\Pi = \Pi_f$.
6.117 COMMENT The preceding exercise asks you to perform one of the basic tasks of intelligence: naming the blocks of a partition. Different languages have different words for "red," "blue," etc., but all of them solve precisely this exercise in relation to the partition of objects (toy bears) by color (the partition $\Pi_f$).
6.130 DEF Let $R\subseteq \Omega\times\Omega$ be a relation on the set $\Omega$. We say that $R$ is an equivalence relation if
6.132 DO Observe:
(a) The divisibility relation on $\zzz$ is reflexive
$(x\mid x)$ and transitive but not symmetric:
$4\mid 12$ but $12\nmid 4$, so divisibility is not
an equivalence relation.
(b) The ordering relation "$\le$" on $\rrr$ is reflexive
$(x\le x)$ and transitive but not symmetric:
$4\le 6$ but $6\not\le 4$, so order is not an equivalence
relation on $\rrr$.
6.135 Examples of equivalence relations
6.140 DEF Given a partition $\Pi=\{A_1,\dots,A_k\}$ of the set
$\Omega$, define the relation $\sim_{\Pi}$ on $\Omega$
as follows: for $a,b\in \Omega$ we say that
$a \sim_{\Pi} b$ if $(\exists i)(a,b\in A_i)$, i.e., $a$ and $b$ belong
to the same block of the partition.
LaTeX for the tilde symbol $\sim$ is "\sim".
6.142 DO (Partitions vs. equivalence relations) Prove: $\sim_{\Pi}$ is an equivalence relation on $\Omega$. We call $\sim_{\Pi}$ the equivalence relation defined by the partition $\Pi$.
6.144 DO (uniqueness of partition) Prove: Different partitions define different equivalence relations. In other words, let $\Pi$ and $\Psi$ be two partitions of the set $\Omega$. Prove: if $\sim_{\Pi} = \sim_{\Psi}$ then $\Pi = \Psi$.
6.150 Fundamental Theorem of Equivalence Relations Let $R$ be an equivalence relation on the set $\Omega$. Then $R$ arises from a partition. In other words, $(\exists\text{ partition }\Pi\text{ of }\Omega)(R = \sim_{\Pi})$.
6.152 COMMENT This partition is unique by 6.144. So every equivalence relation uniquely defines a partition.
6.155 DEF The blocks of $\Pi$ are called the equivalence classes
of the equivalence relation $R$.
With these classes in mind, we can informally summarize the Theorem
as saying that equivalence relations classify.
6.157 COMMENT: The role of equivalence relations in concept formation.
This result is fundamental to understanding how intelligent
beings create concepts such as numbers, colors, etc. Natural numbers
arise from the observation that certain pairs of sets have a bijection
between them, and this relation among sets is an equivalence relation.
Members of one of its equivalence classes are "three trees," "three mountain
peaks," "three goats," etc., giving rise to the number "3". Each
equivalence class corresponds to a natural number.
What intelligent beings recognize is not the word "three" but
the equivalence class named "three" in English,
"kolme" in Finnish, "san" in Chinese, etc.
The names are different across cultures but the equivalence
relation is the same, and so are the equivalence classes.
This equivalence relation is the concept
of natural numbers. Similarly, the concept of "color"
arises from the relation among objects of having the same color,
and while the names of the colors differ across cultures, the
equivalence relation does not.
Concept formation being the key function of
(natural or artificial) intelligence, arguably,
the Fundametal Theorem of Equivalence Relations could be
called the Fundamental Theorem of Intelligence.
As the example of colors shows, in practical concept formation,
there are borderline (hard-to-classify) cases. The problem
that intelligence needs to solve is, given a relation $R$ that
is not quite an equivalence relation, find an equivalence
relation that is "close" to $R$. There are interesting methods
that give often quite reasonable solutions to this problem using
linear algebra ("spectral clustering"). Such methods are widely
used in Image Segmentation and other areas of Machine Learning.
More to follow. Please check back later. Please report any errors.
Class 5 (problem session), Wed 10-5
Class 4, Tue 10-4 Sumset, counting strings, relations
Review all problems by Thursday, October 5, 11:00 (before class).
All homework problems are due Monday, October 10, 23:00, except where
otherwise stated.
4.05 DO STUDY Y20HW01, items 1.10--1.62. Solve all the DO and HW problems in this set; do not hand them in.
4.10 DO STUDY Y20HW02, items 2.10--2.40. Solve all the DO and HW problems on that site; do not hand them in.
4.15 DEF (sumset) Let $A,B$ be subsets of $\zzz$, the set of integers. We define their sumset as $A+B = \{a+b \mid a\in A, b\in B\}$. This is an example of the "setmaker bar" notation; the bar reads "such that." (This definition appears as DEF 2.16 in Y20HW02. Study the related problems there.)
4.17 Example Let $A=\{3,4,6\}$ and $B=\{-1,2\}$. Then $A+B = \{2,3,5,6,8\}$.
4.18 DO $A+\emptyset = \emptyset$.
4.19 NOTATION For a set $A$ we write $|A|$ to denote the number of elements of $A$, also called the cardinality of $A$, or simply the size of $A$. For instance, $|\{a,c,a,b,c\}|=3.$
4.20 NOTATION For $n\ge 0$ we write $[n]=\{1,2,\dots,n\}$. By convention, we write $[0]=\emptyset$.
4.22 DO Let $k,\ell \ge 1$. Determine the set $[k]+[\ell]$. What is the cardinality of this set?
4.23 ORD (2+2 points) Let $k,\ell, m \ge 1$. (a) Determine the set $[k]+[\ell]+[m]$. (b) What is the cardinality of this set? No proofs required.
4.25 HW (6+2+4 points)
Let $A$ and $B$ be non-empty finite subsets of $\zzz$.
Let $|A|=$ and $|B|=\ell$.
(a) Bonus Prove: $|A+B| \ge k+\ell-1$.
(b) ORD Prove that this inequality is tight
in the following sense.
For all $k,\ell\ge 1$ there exist finite sets $A,B\subseteq\zzz$
such that $|A|=k$, $|B|=\ell$, and $|A+B|=k+\ell-1$. (Reproduce
from class.)
(c) Bonus Prove: For all $k,\ell\ge 1$ there exist
finite sets $A,B\subseteq\zzz$ such that $|A|=k$, $|B|=\ell$,
$|A+B|=k+\ell-1$, and neither $A$,
nor $B$ contains consecutive integers.
4.28 HW (4+5 points)
Let $A$ and $B$ be finite subsets of $\zzz$.
Let $|A|=k$ and $|B|=\ell$.
(a) ORD Prove: $|A+B|\le k\ell$. Give
a surjective proof (see 6.77), i.e., a proof by constructing a
surjection from a set of known size $k\ell$ onto $A+B$.
[A non-surjective proof will earn you $\le 2$ points.]
(b) Bonus Prove that this inequality is tight
in the following sense.
For all $k,\ell\ge 0$ there exist finite sets $A,B\subseteq\zzz$
such that $|A|=k$, $|B|=\ell$, and $|A+B|=k\ell$.
4.30 Bonus (4 points) Let $A, B$ be finite subsets of $\zzz$ such that
$|A+B|=|A|\cdot|B|$. Let $C\subseteq A$ and $D\subseteq B$. Prove:
$|C+D|=|C|\cdot |D|$. State a lemma that gives a simple necessary
and sufficient condition for $|A+B|=|A|\cdot|B|$ to hold; use that lemma.
(A "lemma" is an auxiliary result used to prove a theorem.)
4.35 HW (5+4 points) Let $A$ be a finite subset of $\zzz$. Let $|A|=n$.
(a) ORD Prove: $|A+A|\le n(n+1)/2.$ Give a surjective proof
(see 6.77).
[A non-surjective proof will earn you $\le 2$ points.]
(b) Bonus Prove that this inequality is tight
in the following sense.
For all $n\ge 0$ there exists a finite set $A\subseteq\zzz$
such that $|A|=n$ and $|A+A|=n(n+1)/2$.
4.38 Challenge (No deadline, no point value. Hand in by email.)
Prove that for every $n\ge 0$ there exists a set $A\subseteq\zzz$
of size $|A|=n$ such that $|A+A|=n(n+1)/2$ and $A\subseteq [100n^2]$.
4.50 DEF We call any finite set of symbols an alphabet.
We shall usually denote our alphabet of reference by $\Sigma$
(LaTeX: \Sigma).
The most frequently used alphabets in mathematic are $\Sigma=\{0,1\}$,
$\Sigma=\{A,B,C\}$, the Greek l.c. alphabet
$\Sigma=\{\alpha,\beta,\gamma,\delta,\epsilon,\zeta,\eta,\vartheta,
\iota,\kappa,\lambda,\mu,\nu,\xi,o,\pi,\rho,\sigma,\tau,\upsilon,
\vf,\chi,\psi,\omega\}$, and the Roman (English) alphabet.
4.52 DEF A string of length $n$ over the
alphabet $\Sigma$ is a seuqence $a_1\dots a_n$ of $n$ symbols from $\Sigma$.
The set of strings of length $k$ over $\Sigma$ is denote $\Sigma^n$.
4.53 Examples. $00010\in\{0,1\}^5$, $ACCBCB\in\{A,B,C\}^6$,
$AAAAAA\in\{A,B,C\}^6$.
$\{0,1\}^3 = \{000,001,010,011,100,101,110,111\}$
$\{A,B,C\}^2=\{AA,AB,AC,BA,BB,BC,CA,CB,CC\}$.
4.54 Empty string. There is only one string of length zero: the empty string. It is usually denoted $\Lambda$ (LaTeX: \Lambda).
4.56 ORD (counting strings, 4 points)
Notice that $|\{0,1\}^3|=8=2^3$ and
$|\{A,B,C\}^2|=9=3^2$. Generalize these observations:
Prove: if $|\Sigma|=k$ then $|\Sigma^n|=k^n$.
Proceed as follows. Let $u_n$ denote the number
of strings of length $n$ over $\Sigma$. We need to prove that $u_n = k^n$.
First, prove the recurrence
$$ u_n = k\cdot u_{n-1} $$
for all $n\ge 1$.
Then use this recurrence to prove $u_n = k^n$ by induction on $n$.
(Don't forget the base case $n=0$.)
4.60 DEF The powerset $\calP(A)$ of the set $A$ is the set of all subsets of $A$: $\calP(A)= \{B\mid B\subseteq A\}$.
4.62 DO Prove: if $|A|=n$ then $|\calP(A)|=2^n$.
(See Ex. 6.80.)
4.70 DEF Let $A,B$ be sets. The Cartesian product of $A$ and $B$ is the set $A\times B =\{(a,b) \mid a\in A, b\in B\}$.
4.72 Example Let $A=\{a,b,k\}$ and $B=\{2,7\}$. Then $A\times B = \{(a,2), (a,7), (b,2), (b,7), (k,2), (k,7)\}$.
4.74 DO Prove: $A\times B=\emptyset \Leftrightarrow (A=\emptyset)\vee(B=\emptyset)$
4.76 FACT
If $|A|=k$ and $|B|=\ell$ then $|A\times B|=k\times\ell$.
This is not a theorem, but, in essence, the definition of multiplication
of non-negative integers. (Think of how our prehistoric forebears
came to the idea of multiplication.)
4.78 FACT
If $|A|=k$ and $|B|=\ell$ and the sets $A$ and $B$ are disjoint,
i.e., $A\cap B=\emptyset$, then $|A\cup B|=k+\ell.
Again, this is not a theorem, but, inessence, the definition
of addition of non-negative integers.
4.80 DEF
Let $A,B$ be sets. A relation from $A$ to $B$ is a set
$R\subseteq A\times B$. We say that $A$ is the domain
and $B$ is the codomain of $R$: $A=\domain(R)$ and
$B=\codomain(R)$. Notation: instead of $(a,b)\in R$ we usually
write $aRb$.
If $A=B$ then we say that $R$ is a relation on $A$, or
a relation among the elements of $A$.
So a relation on $A$ is a set $R\subseteq A\times A$.
4.81 Examples The following are important relations among
integers, i.e., relations on $\zzz$:
"$<$" (the set of pairs $(a,b)$ such that $a < b$), "$\le$",
divisibility, congruence modulo a given number $m$,
being relatively prime (having $\gcd=1$).
The following are relations among humans, i.e., relations on the set $H$ of
humans:
"parent", i.e., $\{(a,b) \mid a,b\in H, a$ is a parent of $b\}$. Other
relations include "ancestor", "sibling" (those who share both parents).
4.82 DO Let $|A|=k$ and $|B|=\ell$. (a) Show that the number of relations from $A$ to $B$ is $2^{k\ell}$. Show that the number of relations on $A$ is $2^{k^2}$.
4.85 DEF Let $R$ be a relation on the set $A$.
We say that $R$ is
(a) reflexive if $(\forall a\in A)(aRa)$
(b) symmetric if $(\forall a,b\in A)(aRb)\Rightarrow (bRa)$
(c) transitive if
$(\forall a,b,c\in A)(aRb)\wedge(bRc)\Rightarrow (aRc)$
4.88 ORD (4+4+3 points) Let $|A|=n$. The answers to the
questions below should be simple expressions in terms of $n$.
No proof required.
(a) Count the reflexive relations on $A$.
(b) Count the symmetric relations on $A$.
(c) Count those relations on $A$ that are both symmetric and reflexive.
Simplicity of your expressions counts.
4.90 DEF Let $R$ be a relation on the set $A$.
We say that $R$ is
(a*) irreflexive if $(\forall a\in A)(\neg(aRa))$
(none of the elements of $A$ is related to itself)
(b*) antisymmetric $(\forall a,b\in A)((aRb)\Rightarrow \neg(bRa))$
4.91 DO For each of the relations listed in item 4.81, decide whether it is (a) reflexive (b) irreflexive (c) symmetric (d) antisymmetric (e) transitive. Reason your answers.
4.93 DO Prove: every antisymmetric relation is irreflexive.
4.95 ORD (3 points) Is it possible that a relation on the
set $A$ is both reflexive and irreflexive? Your answer should depend on the
set $A$:
"There exists a relation on the set $A$ that is both
reflexive and irreflexive if and only if $A$ is [BLANK]."
Fill in the BLANK with a very simple statement about $A$. Reason your answer.
4.97 DO "The empty relation $R=\emptyset$ on the set $A$ is reflexive if and only if $A$ is [BLANK]." Fill in the blank with a very simple statement about $A$. Reason your answer. (Discussed in the problem session.)
4.99 ORD (2+2+2+2+2) Let $R\subseteq \nnn\times\nnn$
denote the relation of being relatively prime. ($\nnn$ is
the set of natural numbers (positive integers). The numbers $a$ and $b$
are relatively prime if $\gcd(a,b)=1$.) Is the relation $R$
(a) reflexive? (b) irreflexive?
(c) symmetric? (d) antisymmetric?
(e) transitive?
Briefly reason your answers.
Class 3, Thu 9-29 Congruence modulo $m$
All problems are due Monday, October 3, 23:00, except where
otherwise stated.
In all problems in this section, the universe is $\zzz$ (the set of integers).
2.05 DO STUDY Y20HW01, all items (1.10--1.128) except 1.70--1.80 (the Divisor Game, a fun set of problems). Solve all the DO and HW problems in this set; do not hand them in.
2.10 ORD (additivity of divisibility) (4 points) Prove: $$(\forall a,b,c\in\zzz)((a\mid b \wedge a\mid c)\Rightarrow a\mid b+c)\,.$$ State, what property of arithmetic you use in the proof. Point out, where in the proof you use it.
2.12 DO (additivity of divisibility continued) Prove: $$(\forall a,b,c\in\zzz)((a\mid b \wedge a\mid c)\Rightarrow a\mid b-c)\,.$$
2.20 ORD (3 points) Let $S = \{a : (\forall x)(a\mid x)\}$. Describe the set $S$ as an explicit list of its elements. Prove the correctness of your answer. Note that this entails two jobs: you need to prove that (a) the elements you list belong to $S$, and (b) no other integer belongs to $S$.
2.30 ORD (3 points) Let $T = \{b : (\forall y)(y\mid b)\}$. Describe the set $S$ as an explicit list of its elements. Prove the correctness of your answer.
The next part of this section (2.31-2.XX) is concerned with the notion of congruence among integers. In all problems on this subject, the universe is $\zzz$.
2.31 DEF (congruence) We say that $a$ is congruent to $b$ modulo $m$ if $m\mid a-b$. We denote this circumstance by $a\equiv b\pmod m$. In LaTeX: a\equiv b\pmod{m}. The negation of this statement is "$a$ is not congruent to $b$ modulo $m$" (LaTeX: a\not\equiv b\pmod{m}.
2.32 Examples. $5\equiv 26 \pmod 7$, $4\equiv -21 \pmod 5$, $3\equiv 1\pmod 2$, $5\not\equiv 20 \pmod 7$.
2.33 DO Express in simple and common English, without referring to the concept of divisibility, when two numbers are congruent (a) modulo 2, (b) modulo 1, (c) modulo 0.
2.34 DO Fill in the blank: "$a\equiv 0 \pmod m$" if and only if "BLANK". Your answer should be a very simple statement in terms of divisibility. No proof required.
2.35 DO Prove that every number is congruent to (a) 0 or 1 modulo 2 (b) 0 or $\pm1$ modulo 3 (c) 0, $\pm1$, $\pm2$, or 3 modulo 6.
2.37 DO Prove that "congruence modulo $m$" is a reflexive relation on $\zzz$, i.e., $(\forall a)(a\equiv a \pmod{m})$.
2.38 DO Prove that "congruence modulo $m$" is a symmetric relation on $\zzz$, i.e., $(\forall a,b)((a\equiv b \pmod{m})\Rightarrow (b\equiv a \pmod{m})$.
2.39 DO Prove that "congruence modulo $m$" is
a symmetric relation on $\zzz$, i.e.,
$(\forall a,b,c)((a\equiv b \pmod{m})\wedge (b\equiv c \pmod{m})
\Rightarrow (a\equiv c\pmod{m})$.
State what property of divisibility you are using.
(This was done in class; the property used is the
additivity of divisibility.)
2.40 ORD (additivity of congruence mod $m$) (4 points)
Prove: if $a\equiv b \pmod{m}$
and $c\equiv d \pmod{m}$ then $a+c\equiv b+d \pmod{m}$
and $a-c\equiv b-d \pmod{m}$.
State what property of divisibility you are using.
Do not go down to the lower-level definition of divisibility (DEF 1.01).
First translate the assumptions and the desired conclusion to
the language of divisibility; then refer to a result about divisibility.
Note: this is a universally quantified statement. By convention, we omitted the quantifiers $(\forall a,b,c,d,m)$.
2.50 ORD (scaling a congruence mod $m$) (3 points) Prove: if $a\equiv b\pmod{m}$ then $ax\equiv bx\pmod{m}$. State, what property of divisibility you are using.
2.60 ORD (multiplicativity of congruences mod $m$) (5 points)
Prove: if $a\equiv b \pmod{m}$ and $c\equiv d \pmod{m}$ then
$ac\equiv bd \pmod{m}$.
State what previously stated properties of congruences you are using
in each step.
Do not go down to the lower-level definition of congruence (DEF 2.31)
or divisibility (DEF 1.01). You solution should be a few lines only,
with reference to previously stated properties of congruences.
Elegance counts.
2.70 Bonus (4 points) Prove: if $a\equiv b \pmod{m}$ and $k\ge 1$ then $a^k\equiv b^k \pmod m$. Prove this by induction.
2.72 Fermat's little Theorem (FlT) Let $p$ be a
prime number and $p\nmid a$. Then $a^{p-1}\equiv 1\pmod{p}$.
(We shall prove this result later.)
2.74 DO (FlT for small primes) Prove FlT for $p=2,3$.
(Done in class. Use the fact that every integer is congruent
to 0 or 1 mod 2, and congruent to 0 or $\pm 1$ mod 3.)
2.80 Bonus (3 points) Prove FlT for $p=5$.
2.84 DO Prove: If $p$ is a prime number and $p\neq 2$ then $p\equiv \pm 1\pmod 4$.
2.85 DO Prove: If $p$ is a prime number and $p\ge 5$ then $p\equiv \pm 1\pmod 6$.
2.87 DO Prove: If $x$ is odd then $x^2\equiv 1\pmod{8}$.
Class 2 (problem session), Wed 09-28
Class 1, Tue 09-27 Quantifiers, formulas, free and bound variables,
hierarchy of concepts, divisibility, setmaker notation
1.01 DEF (divisibility) Our universe is $\zzz$ (the set of
integers). We say that $a$ divides $b$ (notation: $a\mid b$) if
$(\exists x)(ax=b)$. For instance, $5\mid 35$ and $6\nmid 35$.
Other verbal expressions used to descibe that $a\mid b$:
"$a$ is a divisor of $b$", or "$b$ is a multiple of $a$".
1.10 HW (due Thursday, Sep 29, before class, handwritten on paper)
Let $B =\{x\in\zzz\ :\ x+1\mid x-3\}$. Determine the set $B$.
Your answer should be given as an explicit list of the elements of $B$.
Prove your answer. You may use any other exercises stated in class.
1.20 DO Prove that "divisibility" is a transitive relation on $\zzz$: $$(\forall x,y,z\in\zzz)((x\mid y \wedge y\mid z)\Rightarrow x\mid z)\,.$$ What property of arithmetic does your proof use? (Answer: associativity of multiplication. Point out where in your proof do you use it.)
1.25 LOGIC, DIVISIBILITY, and SET NOTATION in LaTeX.
The $\forall$ symbol (LaTeX: \forall) means "for all"
The $\exists$ symbol (LaTeX: \exists) means "there exists $\dots$
such that"
For example, $(\exists x)(x^2=5)$ means "there exists an $x$ such that
$x^2=5$". Note that this statement is false if our universe is $\zzz$
(integers) and true if our universe is $\rrr$ (real numbers).
The $\wedge$ symbol (LaTeX: \wedge) denotes AND.
The $\vee$ symbol (LaTeX: \vee) denotes OR.
The $\neg$ symbol (LaTeX: \neg) denotes negation.
The $\Rightarrow$ symbol (LaTeX: \Rightarrow)
denotes the "if $\dots$ then" relation between
mathematical statements: if $S,T$ are statements then
$S\Rightarrow T$ means "if $S$ then $T$".
$S\Leftrightarrow T$ (LaTeX: S\Leftrightarrow T)
means "$S$ if and only if $T$". In other words,
$S\Rightarrow T$ means $(S\Rightarrow T)\wedge(T\Rightarrow S)$.
$a\mid b$ (LaTeX: a\mid b) means "$a$ divides $b$".
$a\nmid b$ (LaTeX: a\nmid b) means "$a$ does not divide $b$".
More notation will be added, please check back later.