The notation "MN" refers to the Matoušek--Nešetříl text (second edition). The first edition is also entirely adequate for this class. Note that a new Chapter 2 has been inserted in the second edition so for $i\ge 3$ if you can find something in Chapter $i$ in the second edition, it will appear in Chapter $i-1$ in the first edition.
The notation "LIN" refers to the instructor's Linear Algebra notes, currently in progress.
The notation "PZ" refers to the puzzle problem set from the instructor's 2011 REU course.
"DO" problems are strongly recommended to check your understanding of the concepts; do not hand them in.
Problems labeled "HW" must be handed in at the beginning of the next class unless expressly stated otherwise.
BONUS PROBLEMS are not mandatory but the same deadline applies as to ordinary homework.
CHALLENGE PROBLEMS have no point value (but they earn you the instructor's attention) and no deadline (except they expire when discussed in class). Make sure you hand them in on a separate sheet, state your name, the fact that this is a challenge problem solution, and indicate the problem being solved. One further request: if you hand in a solution to a challenge problem, send email to the instructor giving the problem number and a brief indication of the problem (copied from the problem announcement: like "n+1 numbers" or "another limit related to the def of "e"" -- no detailed description needed, this suffices to remind me which problem it was). Such email will create an easy record and help avoid mistakes in bookkeeping.
REWARD PROBLEMS are challenge problems that you should NOT hand in. The solution is its own reward. No deadline. Of course you are welcome to discuss your thoughts with the TA, the instructor, and your peers.
If you hand in material before its due date, make sure you put it on a separate sheet since solutions are graded in batches by their due dates.
11.1 DO: Prove: the graph $G$ has a spanning tree if and only if $G$ is connected.
11.2 DO: Verify Euler's formula for the five Platonic solids. (Learn their names how to draw them.) Verify the duality relations between.
11.3 HW: Assume both the graph $G$ and its complement are trees. Prove: $n = 1$ or $n=4$. (4 points)
11.4 STUDY the chapter on "Asymptotic notation" in LN. Note the conventions regarding fractions of the form $0/0$ in the definitions of asymptotic equality and the the little-oh notation. Note that $a_n = o(1)$ means $a_n \to 0$ and $b_n = O(1)$ means that $|b_n|$ is bounded.
11.5 DO: Let $\{a_n\}$ be a sequence of real numbers. Prove: $a_n \sim 0$ (i.e., $a_n$ is asymptotically equal to the all-zero sequence) if and only if $a_n$ is eventually $0$, i.e., for all sufficiently large $n$ we have $a_n=0$. (Use the definition stated in class today (11-8) which you can also find in LN.
11.6 DO: Prove: if $a_n\sim b_n$ and $a_n = o(b_n)$ then both sequences are eventually zero.
11.7 DO: Prove: $a_n \sim b_n$ if and only if $a_n = b_n(1+o(1))$. The meaning of the latter is that $a_n = b_n(1+z_n)$ for some sequence $z_n$ such that $z_n = o(1)$.
11.8 HW: Find sequences $a_n \ge 1$ and $b_n\ge 1$ such that neither the relation $a_n = O(b_n)$ nor the relation $b_n = O(a_n)$ holds. Not only should your sequences satisfy these conditions but it should be straightforward to verify that they do. (2 points)
11.9 DO: Prove that the $\Theta$ relation is an equivalence relation among sequences.
11.10 DO: Prove: if $a_n \sim b_n$ then $a_n = \Theta(b_n)$. Prove that the converse does not hold.
11.11 DO: Prove: if $a_n = o(b_n)$ then $a_n = O(b_n)$. Prove that the converse does not hold.
11.12 HW: Prove: if $a_n\to\infty$ and $b_n\to \infty$ and $a_n = \Theta(b_n)$ then $\ln a_n \sim \ln b_n$. (7 points)
11.13 DO: Suppose $b_n \neq 0$ and the quotients $a_n/b_n$ have a (finite or infinite) limit: $\lim_{n\to\infty} a_n/b_n = L$. Observe: if $L=0$ then $a_n=o(b_n)$ and if $L=\infty$ then $b_n = o(a_n)$. Prove: if $0 < L <\infty$ then $a_n = \Theta(b_n)$.
11.14 DO: Recall that the Prime Number Theorem says $\pi(x)\sim x/\ln x$. Prove: $x/\ln x \sim \Li(x)$ where $\Li(x) = \int_2^x (1/t)dt$ (logarithmic integral). Note: $\Li(x)$ is a better approximation to $\pi(x)$ than is $x/\ln x$. The statement that $\pi(x) - \Li(x) = O(\sqrt{x}\ln x)$ is equivalent to the Riemann Hypothesis.
11.15 HW: Let $\vf = \frac{1+\sqrt{5}}{2}$ (the golden ratio). Prove: $F_n = O(\vf^n)$. Do not use results about Fibonacci numbers we did not prove in class (e.g., the explicit formula for $F_n$). Hint. Select an appropriate constant $C$ and prove by induction that $F_n \le C\vf^n$. What is the smallest constant $C$ for which your proof works? (Explanatory note added on 11-10, 7pm: You do not need to get the best possible constant. Just state the best constant achieved by your proof. You will not lose points if another proof gets a better constant.) (6 points)
11.16 HW: We shall prove that if a planar graph has $n\ge 3$ vertices then it has $m\le 3n-6$ edges. Use this result, but no other results not proved in class. (a) Show that this bound is tight: construct, for every $n\ge 3$, a planar graph with $3n-6$ edges. (b) Prove that $K_5$ is not planar. (c) Prove: every planar graph has a vertex of degree $\le 5$. (d) Prove: every planar graph $G$ is 6-colorable ($\chi(G)\le 6$). (e) Prove: if $n$ is sufficiently large then the probability that a random graph on a given set of $n$ vertices is planar is less than $2^{-0.49n^2}$. (5+2+3+5+10 points)
11.17 CHALLENGE. Let $p$ be an odd prime number. Prove: if $(\exists x)(x^2\equiv -1 \pmod p)$ then $p\equiv 1\pmod 4$. Do not use any theorems not proven in class. (Hint: FlT)
11.18 DO: We roll $n$ dice. What is the expected value of the product of the $n$ numbers shown on the dice? (Each of these numbers is an integer between 1 and 6.)
10.1 DO: Recall the Erdös-Rado arrow symbol: We say that "$n\to (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}$. Prove (Erdös--Szekeres): $$\binom{k+\ell}{k} \to (k+1,\ell+1).$$ Prove this by induction on $k+\ell$. The base cases are those with $k=1$ or $\ell = 1$ (infinitely many base cases)
10.2 HW: Define what the statement $17\to (3,3,3)$ should mean. Prove this statement. (9 points)
10.3 DO (Esther Klein): We say that a set of points in the plane is in general position if no three are on a line. Prove: Given five points in the plane in general position, prove that four of the form a convex 4-gon.
10.4 DO: Prove: $k$ points in the plane for a convex $k$-gon if and only if every 4 of them form a convex 4-gon.
10.5 DO: Deduce from Ramsey's theorem on quadruples that $(\forall k)(\exists n)($given any $n$ points in the plane, $k$ of them form a convex $k$-gon) (Erdös -- Szekeres)
10.6 DO: (a) Suppose $p_1 < p_2 < \dots < p_k$ are prime numbers and they form an arithmetic progression. Prove: the increment of the progression is divisible by all primes $< k$. (So for instance the increment of a 6-term arithmetic progression must be divisible by 30; the sequence 7,37,67,97,127,157 is an example showing this bound is tight.) (b) (Challenge): Let $P(x)$ be the product of all primes $\le x$. Prove: $\ln P(x) \sim x$ (so $P(x)$ is about $\eee^x$). (Use the PNT. In fact, this statement is equivalent to the PNT.)
10.7 DO: What is the dual of the $k\times \ell$ grid? Verify Euler's formula for the $k\times \ell$ grid.
10.8 DO: Prove: almost all graphs are not planar. What this means is the following. Let $p_n$ denote the probability that a random graph on a given set of $n$ vertices is planar. Prove: $\lim_{n\to\infty} p_n = 0$.
9.0 DO: solve Quiz 2 without the time pressure. (Quiz 2 has been posted, see the link on the course home page, click the "Grading and tests" tab on the banner.)
9.1 STUDY LN Chap. 7 (Finite probability spaces) Sections 7.1 - 7.4.
9.2 DO: Prove: (a) If the events $A_1,\dots,A_k$ are independent then the events $A_1,\dots,A_{k-1}, {\overline A_k}$ are also independent. (b) Infer form this that for any subset $T\subseteq [k]$ the events $B_1,\dots,B_k$ are independent, where $B_i = A_i$ if $i\in T$ and $B_i = {\overline A_i}$ if $i\notin T$. (We can negate any subset of the events.)
9.3 DO: Prove: If there exist $k$ nontrivial independent events in the probability space $(\Omega,P)$ then $|\Omega|\ge 2^k$.
9.4 CHALLENGE. Find a probability space $(\Omega,P)$ and $k$ pairwise independent events $A_i\subseteq\Omega$ such that $P(A_i)=1/2$ and $|\Omega|\le 2k$.
9.5 DO: Prove: (a) If the events $A_1,\dots,A_k$ are independent then the $k-1$ events $A_1\cap A_2, A_3,\dots,A_k$ are also independent. (b) Quickly infer from part (a) and from Problem 9.2 that the same holds with $A_1\cup A_2$ in the place of $A_1\cap A_2$. (c) Let us split $[k]$ into $t$ disjoint blocks $[k]=R_1\cup\dots\cup R_t$ and let the event $B_j$ be a Boolean combination of the events $\{A_i : i\in R_j\}$. Prove: If the events $A_1,\dots,A_k$ are independent then the events $B_1,\dots,B_t$ are independent. (Boolean combinations of disjoint subsets of independent events are independent.)
9.6 DEFINITION. The random variables $X_1,\dots,X_k$ are independent if $$(\forall x_1,\dots, x_k\in {\mathbb R})\left(P\left(\bigwedge_{i=1}^k X_i=x_i\right) = \prod_{i=1}^k P(X_i = x_i)\right).$$ (The wedge symbol $\bigwedge$ denotes "AND.")
9.7 DO: Prove: any subset of a set of independent events is independent.
9.8 DO: Prove: the events $A_1,\dots,A_k$ are independent if and only if their indicator variables are independent.
$\DeclareMathOperator{\cov}{Cov}$ $\DeclareMathOperator{\var}{Var}$ 9.9 DEFINITION: Recall that the covariance of the random variables $X$ and $Y$ is $\cov(X,Y)=E(XY)-E(X)E(Y)$. We say that $X$ and $Y$ are positively correlated if $\cov(X,Y) >0$, negatively correlated if $\cov(X,Y) < 0$, and uncorrelated if $\cov(X,Y) = 0$.
9.10 DO: Prove: If the random variables $X$ and $Y$ are independent then they are uncorrelated.
9.11 HW: Prove that the converse of the previous exercise is false: construct a probability space and two random variables that are uncorrelated but not independent. Make your sample space as small as possible; you don't need to prove that it is smallest possible (but you get 2 bonus points if you give an elegant proof that it is smallest possible). (10 points)
9.12 DO: Prove: If the random variables $X_1,\dots,X_k$ are independent then $E\left(\prod_{i=1}^k X_i\right) = \prod_{i=1}^k E(X_i)$.
9.13 DO: LN 7.3.10 (the inequality $E(X^2) \ge (E(X))^2$ is equivalent to the Cauchy-Schwarz inequality).
9.14 HW: Let $T$ denote the number of triangles in a random graph on a given set of $n$ vertices. Determine $\var(T)$ (a) exactly (give a closed-form expression) (b) asymptotically (find constants $a,b$ such that $\var(T)\sim an^b$). (10+4 points) Hint: Recall from class: if $X = Y_1 +\dots + Y_k$ then $$\var(X) = \sum_i \var(Y_i) + \sum_{i\neq j} \cov(Y_i,Y_j).$$ (Clarfication added on 11-05 at 5:15pm: The sum of the covariances is over all ordered pairs $(i,j)$ such that $i$ is not equal to $j$. Please let me know if your browser does not display "not equal" under the large summation sign.)
9.15 CHALLENGE. LN 7.2.15 (expected number of distinct prime divisors of a random integer between 1 and $N$ is asymptotically $\ln\ln N$).
9.16 DO: LN 7.2.16 (expected number of letters in the right envelope)
9.17 DO: LN 7.4.4 (functions of independent random variables are independent)
9.18 DO: LN 7.4.5 (functions of disjoint blocks of independent random variables are independent)
9.19 HW: Consider a random graph on the vertex set $V=[n]$. Let $A$ be the event that $\deg(1)=3$ and $B$ the event that $\deg(2)=3$. (a) Determine the limit $P(B\mid A)/P(A)$. (b) How are the events $A$ and $B$ correlated (for large $n$)? (Positively or negatively correlated or independent?) (8+3 points)
8.1 HW: Write the following (generalized) binomial coefficients as simple closed-form expressions in terms of "ordinary" binomial coefficients (those we have studied previously, that make combinatorial sense): (a) $\binom{-1}{k}$ (b) $\binom{-1/2}{k}$ (c) Asymptotically evaluate (b): find constants $a,b,c$ such that $\binom{-1/2}{k} \sim a k^b c^k$ (1+6+4 points)
8.2 DO: Find the number of terms in the expansion of $(x_1+\dots+x_k)^n$ according to the Multinomial Theorem. Your answer should be a simple binomial coefficient.
8.3 DO: Draw all 6-vertex trees up to isomorphism. State how many you found.
8.4 HW: Draw all 7-vertex trees up to isomorphism. State how many you found. (7 points) You will lose 2 points per mistake (get 0 points if you make 4 or more mistakes). Watch out for two kinds of mistakes: you draw two trees that are isomorphic, or you miss an isomorphism class.
8.5 DO: Prove: In a tree with $n\ge 2$ vertices, the endpoints of a maximal path have degree 1.
8.6 DO: Prove: If the graph $G$ is connected and $x$ is a vertex of degree 1 then $G\setminus x$ is connected.
8.7 DO: If $G$ is connected then $m\ge n-1$.
8.8 DO: Prove: $G$ is a tree if and only if $G$ is connected and $m = n-1$.
8.9 DO: (a) For all graphs $G$ the inequality $m\ge n-c$ holds, where $c$ is the number of connected components. (b) $G$ is a forest (cycle-free graph) if and only if $m=n-c$.
8.10 DO: Prove: $G$ is a tree if and only if $(\forall x,y\in V(G))(\exists!\ x-\dots-y$ path$)$. (The symbol $\exists!$ reads "exists a unique.")
8.11 DO: Let $d_1,\dots,d_n$ be positive integers such that $\sum_{i=1}^n d_i = 2n-2$. Prove: the number of trees with vertex set $V=[n]$ such that $\deg(i)=d_i$ is $\frac{(n-2)!}{\prod_{i=1}^n (d_i-1)!}$.
8.12 HW: Deduce Cayley's formula from 8.11. Cayley's formula states that the number of trees on a given set of $n$ vertices is $n^{n-2}$. (8 points)
8.13 DO: Prove "baby Ramsey:" If we color the edges opf $K_6$ red/blue then there will be a monochromatic triangle (a triangle with only one color).
8.14 DO: (The gourmet mouse problem): The $3\times 3\times 3$ cheese has no Hamilton path ending in center.
7.1 STUDY: LN Chapters 7.1, 7.2 (finite probability spaces, random variables) and Chapter 6.1 (graph terminology), especially the definitions on pp. 45-46 and 48.
7.2 DO: Prove that the two graphs drawn on p.52 of LN are isomorphic. (Petersen's graph)
7.3 DO: Verify that the girth (length of the shortest cycle) of Petersen's graph is 5. Count the cycles of length 5 in Petersen's graph.
7.4 DO: Prove: if a regular graph of degree $k$ has girth $\ge 5$ then it has $n\ge k^2+1$ vertices. - Do we know cases when $n=k^2+1$ ?
7.5 HW: For what values of $k$ and $\ell$ is the $k\times\ell$ grid graph Hamiltonian (has a Hamilton cycle)? (The $4\times 10$ grid appears in LN, p.49. The $k\times\ell$ grid has $k\ell$ vertices.) Prove your answers. Your proof for the cases when there is no Hamilton cycle should be very simple and convincing (just a short sentence). (7 points)
7.6 DO: Prove: if $G$ is a connected regular graphs of degree 2 (every vertex has degree 2) then $G$ is a cycle.
7.7 DO: Prove: if a graph is disconnected then its complement is connected.
7.7 DO: Find two nonisomorphic connected regular graphs of the same degree on 6 vertices.
7.8 HW: Prove: if $G$ is self-complementary (isomorphic to its complement) then $n\equiv 0$ or $1 \pmod 4$ where $n$ is the number of vertices. (5 points)
7.9 DO: Prove: if $n\equiv 0$ or $1 \pmod 4)$ then there exists a self-complementary graph with $n$ vertices.
7.10 DO: Prove: if all cycles in a graph are even then the graph is bipartite.
7.11 DO: Prove: $\chi(G)\le 1+\deg_{\max}.$ (Here $\chi(G)$ denotes the chromatic number of $G$ and $\deg_{\max}$ the maximum of the degrees of the vertices.)
7.12 DO: Prove: $\chi(C_n) = 2$ if $n$ is even and $3$ if $n$ is odd. (Here $C_n$ denotes the cycle of length $n$.)
7.13 HW: Prove: $\alpha(G)\chi(G)\ge n$. Here $\alpha(G)$ is the independence number (size of the largest independent set). (6 points)
7.14 DO: Determine the chromatic number of the complement of $C_n$.
7.15 DO: LN 6.1.17: Find a triangle-free graph (no $K_3$ in the graph) of chromatic number 4. Let the graph have $n=11$ vertices and a symmetry of order 5 with 1 fixed point. Once done, you will have constructed Grötzsch's graph.
7.16 CHALLENGE PROBLEM. Prove: triangle-free graphs can have arbitrarily large chromatic number.
7.17 DO (chromatic polynomial): Let $G$ be a graph on $n$ vertices and $x$ a positive integer. Let $f_G(x)$ denote the number of legal colorings $f\,:\,V(G)\to [x]$. (a) Compute $f_G(x)$ for the complete graph $K_n$, the complement of $K_n$, the path $P_n$ of length $n-1$, the cycle $C_n$ of length $n$. (b) Show that $f_G$ is a polynomial of $x$ of degree $n$.
7.18 DO: Prove: a bipartite graph has at most $n^2/4$ edges.
7.19 CHALLENGE PROBLEM (Mantel - Turán Theorem): Prove: a triangle-free graph has at most $n^2/4$ edges.
7.20 CHALLENGE PROBLEM: LN 6.1.22 (Köváry - Turán - Sós): a graph without 4-cycles has no more than $O(n^{3/2})$ edges.
7.21 HW (due Thu, Nov 1): A tree is a connected graph without cycles. Count and draw all trees on seven vertices up to isomorphism. (11 points) Lose 2 points per error. Error: (a) you miss an isomorphism class; (b) you draw a redundant graph (that is isomorphic to a graph previously listed). (The deductions stop at zero, so you get zero points if you make 6 or more errors.)
6.1: Review LN Chap. 7.1 (Finite Probability Spaces and Events) from 7.1.1 to 7.1.15, including the concept of conditional probability. Review LN Chap 7.2 (Random Variables and Expected Value) except Ex. 7.2.14 and Ex. 7.2.17.
6.2 HW: Consider the uniform probability space over a sample space $\Omega$ with $|\Omega|=p$ a prime number. Prove: If events $A,B\subseteq \Omega$ are independent then one of them is a trivial event. (A trivial event is an event with probability 0 or 1.) (5 points)
6.3 HW (due Tue, Oct 30) (correlation of divisibility): Let $n$ be a positive integer. Pick a number $x\in [n]$ at random. Let $A(n)$ denote the event that $2\mid x$ and $B(n)$ the event that $3\mid x$. (a) Determine (a1) $P(A(n))$ (a2) $P(B(n))$ (a3) $P(A(n)\cap B(n))$ (b) Depending on the residue class of $n$ modulo 6, determine whether $A(n)$ and $B(n)$ are independent, positively correlated, or negatively correlated. (Your answer should be a list of 6 statements of the form: "if $n\equiv i\pmod 6$ then $A(n)$ and $B(n)$ are ..." ($i=0,1,\dots,5$). (2+2+2+10 points)
6.4 DO: LN 7.1.2 (questions about bridge cards)
6.5 DO: LN 7.1.3 ("modular equation")
6.6 DO: LN 7.1.5 (union bound)
6.7 DO: LN 7.1.7 (conditional probabilities multiply)
6.8 DO: LN 7.1.11 (independence via conditional probabilities)
6.9 DO: LN 7.1.12 (independence of complement)
6.10 DO: LN 7.1.13 (independence of die events)
6.11 DO: LN 7.1.8 (sum of three dice)
6.12 DO: LN 7.1.14 (independence/correlation of "sum of dice" events)
6.13 DO: LN 7.1.9 (Theorem of Complete Probability)
6.14 HW (Probability of causes) Diseases $A$ and $B$ have similar symptoms. Let $W$ be the population of all patients showing these symptoms. The two diseases can only be differentiated by costly tests. We know (from sampling the population and performing these costly tests) that $70\%$ of $W$ have disease $A$, $25\%$ have disease $B$, and $5\%$ have some other disease. We consider the effectiveness of treatment $T$. We know that $60\%$ of the patients with disease $A$ respond to $T$, while only $12\%$ of the patients with disease $B$ respond to treatment $T$. From the rest of the population $W$, $40\%$ respond to treatment $T$.
(a) A new patient arrives at the doctor's office. The doctor determines that the patient belongs to $W$. What is the probability that the patient will respond to treatment $T$?
(b) The patient's insurance will not pay for the expensive tests to differentiate between the possible causes of the symptoms. The doctor bets on treatment $T$. A week later it is found that the patient did respond to the treatment. What is the probability that the patient had disease $A$? Show all the intermediate results you need to compute. (8+8 points)
6.15 DO: LN 7.2.3 (computing expected value as sum over range)
6.16 DO: LN 7.2.4 (expected value is between min and max)
6.17 DO: LN 7.2.5, 7.2.6 (additivity, linearity of expected value)
6.18 (expected value of indicator variable): LN 7.2.8.
6.19 DO: LN 7.2.9 (a) CHALLENGE: LN 7.2.9 (b) (random variables vs. indicator variables)
6.20 DO: LN 7.2.11 (expected number of runs of $k$ heads)
6.21 HW (due Tuesday, Oct 30): LN 7.2.13 (club with 2000 members). Assume the club serves vodka to all its members. - Make sure you give a clear definition of the random variables you use. The clarity of the definition accounts for 3/4 of the credit. Hint. Learn about indicator variables (LN 7.2.6, 7.2.7). Represent the number of lucky members as a sum of indicator variables. (8 points) What is the size of the sample space for this experiment? (1 point)
6.22 HW (Bernoulli trials, due Tuesday, October 30): Let $0 < p < 1$ be the probability that a biased coin lands on heads. Let $b(n,k)$ denote the probability that out of $n$ flips of our biased coin, exactly $k$ land on heads. Recall that $b(n,k) = \binom{n}{k}p^k(1-p)^{n-k}$. Prove that the sequence $b(n,0), b(n,1),\dots, b(n,n)$ is unimodal, meaning that it increases to its maximum and then it decreases. The increase and decrease are strict except that the two largest (consecutive) terms may be equal. For what value of $k$ is $b(n,k)$ maximal among all $b(n,j)$ $(0\le j\le n)$? (14 points)
6.23 DO: Find all values of $k$ such that $\gcd(7k+2,9k-5)=53.$
6.24 CHALLENGE PROBLEM. Let $M_n$ denote the least common multiple of the numbers $1,2,\dots,n$. Prove: $\ln M_n \sim n$. (Use the Prime Number Theorem.)
6.25 DO: Prove: If there are $k$ independent nontrivial events then the cardinality of the sample space is at least $2^k$.
6.26 HW (due due Tuesday, October 30): Construct a probability space and 3 events that are pairwise but not fully independent. Make your sample space as small as possible. (5 points)
6.27 DO: For every $k\ge 3$, construct a probability space and $k$ events that are $(k-1)$-wise but not fully independent. Make your sample space as small as possible.
5.1 DO: solve Quiz 1 without the time pressure. (Quiz 1 has been posted, see the link on the course home page, "Grading and tests" tab on the banner.)
HW 5.2: Count the monotone non-decreasing functions $[k]\to [\ell]$. Here $[k]$ denotes the set $\{1,2,\dots,k\}$; a function $f\,:\,[k]\to [\ell]$ is monotone non-decreasing if $x\le y \ \Rightarrow \ f(x)\le f(y)$. Your answer should be a very simple closed-form expression involving a binomial coefficient. (6 points)
5.3 DO: Prove Bonferroni's inequalities (truncated inclusion-exclusion formula) Let $A_1,\dots,A_k$ be subsets of the universe $\Omega$ (a finite set). Let $B = \Omega\setminus \bigcup_{i=1}^k A_i$. Recall that the Inclusion-Exclusion Formula says that $|B| = S_0 - S_1 + S_2 - + \dots$ where $S_j$ is the sum of the cardinalities of the $j$-wise intersections of the $A_i$. (Review this from the text and/or web sources.) Prove: $|B| \le S_0 - S_1 + S_2.$ More generally, prove that
5.4 DO: In class we gave a combinatorial proof of the identity $\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}$. Give an "algebra proof:" use the binomial theorem. Hint: consider the identity $(1+x)^{2n} = (1+x)^{n}(1+x)^{n}$. Compare the coefficients of $x^n$ on each side.
4.1 HW (gcd as linear combination): (a) Find integers $x,y$ such that $47x+63y =1$. Show your work. (You lose points if you only give the answer and do not show the steps that led you to the answer.) (b) Find $47^{-1} \bmod{63}$. (4+2 points)
4.2 HW (CRT) Consider the following system of simultaneous
congruences:
$x\equiv 5 \pmod{24}$
$x\equiv 2 \pmod {33}$
$3x\equiv 7 \pmod {26}$
Prove that this system has a solution. Your proof should be short and elegant, involve no calculation, only correct references to results learned in class. Do not calculate a solution, only prove it exists. (7 points)
4.3 DO: Find all solutions of the system of congruences given in the preceding exercise.
4.4 DO (CRT?)
Decide whether or not the following system of simultaneous
congruences has a solution. Prove your answer.
$x\equiv 11 \pmod{21}$
$x\equiv 5 \pmod{12}$
$x\equiv 1 \pmod{14}$
Your proof should be very short, only a few lines.
4.5 DO: Prove: If $p$ is a prime number and $x^2\equiv 1 \pmod p$ then $x\equiv \pm 1\pmod p$.
4.6 HW: Let $p,q$ be distinct odd primes.
Prove: $(\exists x)(x^2\equiv 1\pmod{pq}$ but
$x\not\equiv \pm 1 \pmod{pq} )$.
(Note: you don't get to chose $p,q$. In the problem,
$p$ and $q$ are "given," i.e., you have to prove
the result for all possible choices of $p$ and $q$.)
(12 points)
4.7 DO: Prove: if $p$ is a prime and $p\ge 5$ then $p\equiv\pm 1\pmod 6$.
4.8 DO: Let $\nnn =\{0,1,2,\dots\}$ denote the set of nonnegative integers. Prove that the set-difference $\nnn\setminus (5\nnn + 8\nnn)$ is finite. Find the largest number in this set.
4.9 HW: We say that the integers $a_1,\dots,a_k$ are relatively prime if their gcd is 1. Find three integers $x,y,z$ that are relatively prime but no two among them is relatively prime. In other words, you need that $\gcd(x,y,z)=1$ but $\gcd(x,y)\neq 1$, $\gcd(y,z)\neq 1$, $\gcd(x,z)\neq 1$. (State your numbers, do not prove.) (3 points)
4.10 HW (number of divisors, due Thu, Oct 18): LN 4.1.15 (c) (12 points)
4.11 DO: LN 1.2.5 (d)(f)(h) (logic and numbers)
4.12 DO: LN 4.1.27 (logic and gcd)
4.13 DO: Determine the gcd of all numbers of the form $p^2-1$ where $p\ge 11$ is prime.
4.14 DO: Find a prime $p$ such that $100^2 \equiv -1 \pmod p$. Tell how you found $p$. (You may use computer tools.)
4.15 DO: Consider the system of $k$ congruences $x\equiv a_i \pmod{m_i}$, $i=1,\dots,k$. A solution to the system is a number $x$ that simultaneously satisfies all the congruences. Prove: if every pair of these congruences has a solution then the entire system has a solution. In other words, if the system as a whole is contradictory (no simultaneous solution exists) then there exist two among these congruences so that already those two contradict each other.
4.16 DO: Consider the system of $2$ congruences $x\equiv a \pmod{m}$ and $x\equiv b \pmod{n}$. Prove: this system has a solution if and only if $a\equiv b \pmod d$ where $d = \gcd(m,n)$.
4.17 DO: True or false? Give very simple proofs. Remember: to prove the statement, you need to devise a winning strategy for the existential player (tell its moves as a function of the history of the game so far); to disprove it, you need to devise a winning strategy for the universal player. (The domain of the variables is $\zzz)$.
(a) $(\forall x)(\exists y)(\forall z)(z\mid x+y)$.
(b) $(\forall x)(\exists y)(x+y \mid x^2+y^2)$.
(c) $(\exists x,y)(\forall z)(\gcd(x+z,y+z) \mid \gcd(x+z+1,y+z+1))$
(d) $(\forall x,y)(\exists z)(\gcd(x+z,y+z) \mid \gcd(x+z+1,y+z+1))$
4.18 DO: Find a sequence of real numbers which is bounded but has no limit.
4.19 DO: Determine the limits of the following sequences as $n\to\infty$.
(a) $\frac{7n^2+3n-100}{3n^2+10n+1000}$ ; (b) $\frac{\ln n}{\sqrt{n}}$ ; (c) $\frac{n^{100}}{1.001^n}$.
4.20 DO: Determine the limits of the following functions as $x\to 0$.
(a) $\frac{\ln(1+x)}{x}$ ; (b) $\frac{\sin x}{x}$; (c) $\frac{\sqrt{1+x} -1}{x}$;
4.21 DO: Recall that two sequences $a_n$ and $b_n$ are asymptotically equal if $\lim_{n\to\infty} a_n/b_n = 1.$ Notation: $a_n \sim b_n$. Here, fractions of the form $0/0$ are replaced by 1. Find very simple expressions that are asymptotically equal to each of the following expressions.
(a) $3n^4 +5n -100$ (b) $n + \cos n$ ; (c) $\sqrt{n^2+1}$ ; (d) $\sqrt{n^2+1}-n$ ; (e) $\binom{n}{5}$ ; (f) $\sum_{k=1}^n 1/k$.
4.22 DO: Prove: $\ln(n!) \sim n\ln n.$ Do not use any theorems, just the definition of asymptotic equality and basic properties of limits and logarithms. (Hint: notice that trivially, $\ln(n!) \le n\ln n$. Prove that for every $k$ we have $k^{n-k} < n!$ (assuming $1\le k\le n$). Choose $k=\lfloor n/\ln n \rfloor$ to get a lower bound that is asymptotically equal to $n\ln n$.)
4.23 DO: True or false (prove): If $a_n \sim b_n$ then
(a) $a_n^2 \sim b_n^2$ ; (b) $\sqrt{a_n} \sim \sqrt{b_n}$ ; (c) $2^{a_n} \sim 2^{b_n}$.
4.24 HW: Assume $a_n, b_n > 1$.
Consider the following statement:
"If $a_n\sim b_n$ then $\ln a_n \sim \ln b_n.$"
(a) Prove that the statement is false. (Remember: $a_n, b_n >1$.)
(b) Prove that the statement becomes true if $a_n$ is bounded away from 1, i.e., $(\exists c>0)$ such that $a_n \ge 1+c$ for all sufficiently large $n$. (5+8 points)
4.25 HW: Find real constants $a,b,c$ such that $\binom{2n}{n} \sim a n^b c^n.$ Prove your answer. (6 points) (Note: the original posting said "positive constants." This is incorrect. Thank you to the student who pointed this out. This update was posted on 10-15 at 4:50 pm.)
4.26 CHALLENGE PROBLEM. True or false? $(1+1/n)^{n^2} \sim {\mathrm e}^n$.
4.27 DO: (Uniqueness of solutions of simultaneous congruences) Consider the system of $k$ congruences $x\equiv a_i \pmod{m_i}$, $i=1,\dots,k$. Let $M$ denote the least common multiple of the $m_i$. Recall that a solution to the system is a number $x$ that simultaneously satisfies all the congruences. Prove that if a solution exists, it is unique modulo $M$. In other words, suppose that $x_0$ is a solution. Prove that $(\forall x)(x$ is a solution if and only if $x\equiv x_0 \pmod{M})$.
In particular, if the condition of the CRT holds (the moduli are pairwise relatively prime) then a solution exists and is unique modulo the product of the moduli. (Note: by error, this problem was previously numbered 4.47.)
4.28 DO: Consider four sequences of real numbers, $\{a_n\},$ $\{b_n\},$ $\{u_n\},$ $\{v_n\}.$ Prove: if $a_n\sim b_n$ and $u_n\sim v_n$ then $a_n u_n \sim b_n v_n$ and $a_n/u_n \sim b_n/v_n$. In the case of the quotients, we need to assume that for all sufficiently large $n$, the value $u_n$ is not zero, i.e., $u_n=0$ occurs only for a finite number of values of $n$. (Prove that this assumption implies that the same also holds for the sequence $v_n$.) Notice in particular that if $u_n\sim v_n$ and $u_n\neq 0$ for all sufficiently large $n$ then $1/u_n\sim 1/v_n$. (Note: by error, this problem was previously numbered 4.48.)
3.1 HW (gcd vs linear combinations): Prove: if the number $d$ is a common divisor of $a$ and $b$ and $d$ can be written as a linear combination $ax+by$ then $d$ is a greatest common divisor of $a$ and $b$. (Note: this is a converse if what we proved in class, namely, that the greatest common divisor can be written as a linear combination.) (4 points)
3.2 HW (existence of multiplicative inverse): Recall that $x$ is a multiplicative inverse of $a$ modulo $m$ if $ax\equiv 1 \pmod m$; notation: $x = a^{-1} \bmod m$. Prove: $a$ has a multiplicative inverse modulo $m$ if and only if $\gcd(a,m)=1$. (6 points)
3.3 HW (computing multiplicative inverses): Find the following multiplicative inverses:
(a) $6^{-1} \pmod{19}$.
(b) $k^{-1} \pmod{2k+1}$. (Here $k\ge 1$.)
(c) $k^{-1} \pmod{3k+1}$. (Here $k\ge 1$.)
Show your work (show how you got the answer). Each answer should be a positive integer that is less than the modulus. (2+4+4 points)
3.4 HW (Fermat's little Theorem) Compute $10^{10^{10^{10}}} \bmod {17}$. Show all your work. (6 points) (Your answer should be an explicit integer between $0$ and $16$.)
3.5 DO (composite modulus) Assume $\gcd(m,n)=1$. Prove: $(\forall a,b)(a\equiv b \pmod{mn}) \Leftrightarrow a\equiv b \pmod{m}$ AND $a\equiv b \pmod{n}$)
3.6 HW (due Tuesday, October 16) Prove: $(\forall a)(a^{13}\equiv a\pmod{65})$. Use Problem 3.5 without proof. (6 points)
3.7 DO: (a) Prove: if $a\mid bc$ and $\gcd(a,b)=1$ then $a\mid c$.
(b) Prove: if $ax \equiv ay \pmod m$ and $\gcd(a,m)=1$ then
$x\equiv y \pmod m$.
(c) Prove: if $ax\equiv ay \pmod m$ and $m\neq 0$ then
$x\equiv y \pmod{m/d}$ where $d = \gcd(a,m)$.
3.8 DO: (a) Define the least common multiple in analogy with our definition of the greatest common divisor.
(b) Prove that l.c.m. exists. Hint: do not try to mimic the proof of the existence of a g.c.d.; use instead the fact that every set of integers (even an infinite set) has a g.c.d. Represent the l.c.m. as the g.c.d. of a certain set of numbers (which numbers?).
(c) LN 4.2.10: $\gcd(a,b)\lcm(a,b)= |ab|$.
3.9 DO: Recall the notation that for $A, B\subseteq \zzz$ we write
$A+B$ to denote the set $A+B =\{a+b \mid a\in A, b\in B\}$
and $cA = \{ca\mid a\in A\}$. Prove:
(a) $a\zzz + b\zzz = d\zzz$ where $d = \gcd(a,b)$.
(b) $a\zzz \cap b\zzz = m\zzz$ where $m = \lcm(a,b)$.
3.10 DO:
(a) Let us say that $M\subseteq \zzz$ is a module
if $M$ is not empty and $M$ is closed under subtraction, i.e.,
$(\forall a,b)($ if $a,b\in M$ then $a-b\in M)$. Observe
that $(\forall d)(d\zzz$ is a module. Prove that these
are the only moduli, i.e., if $M$ is a module then
$(\exists d)(M=d\zzz)$. Do not use the existence of gcd in the proof.
Use the Division Theorem.
(b) (elegant alternative proof of the existence of gcd):
Fix $a$ and $b$. Notice that the set $M(a,b):= a\zzz + b\zzz$
is a module. Therefore, by part (a), there exists $d$ such that
$M(a,b) = d\zzz$. Prove: $d$ is a gcd of $a$ and $b$
and $d$. Note that this will also prove with no further effort
that the gcd can be written as a linear combination of $a$ and $b$.
3.11 DO: (Division Theorem): $(\forall a,b)$ if $b\neq 0$ then $(\exists q,r)(a=bq+r$ and $0\le r < |b|)$. Prove this by induction on $a$.
3.12 CHALLENGE PROBLEM. Assume $a\ge b \ge 0$. Prove: if $a$ has $n$ digits in binary then Euclid's algorithm finds $\gcd(a,b)$ in $\le 2n$ rounds. (One round consists of one execution of the Division Theorem.)
3.13 CHALLENGE PROBLEM (Erdös). Let $A\subseteq \{1,2,\dots,2n\}$. Assume $|A|=n+1$. Prove: $A$ includes two numbers that are relatively prime. (Paul Erdös (1913-1986), the most prolific mathematician of all time, used to challenge the "epsilons" -- mathematically inclined youngsters -- with this problem.)
3.14 CHALLENGE PROBLEM. Prove: if $p$ is a prime number and $p^t \mid \binom{n}{k}$ then $p^t \le n$.
3.15 CHALLENGE PROBLEM. An integer $n$ is called a Carmichael number if $(\forall a)($ if $\gcd(a,n)=1$ then $a^{n-1}\equiv 1 \pmod n)$. (a) Find a Carmichael number of the form $3pq$ where $3 < p < q$ are primes. (b) Prove: no number of the form $pq$ is a Carmichael number (where $p$ and $q$ are primes).
2.0 HW: Review mathematical induction.
2.1 HW (set of divisors): Let $\div(a)$ denote the set of divisors of $a$. Prove: $\div(a,b) = \div(a-b,b)$. (4 points)
2.2 HW: Prove that consecutive Fibonacci numbers are relatively prime. (4 points)
2.3 HW: LN 4.2.6: Prove: $\gcd(a^k-1, a^{\ell}-1)=a^d-1$ where $d = \gcd(k,\ell)$. (6 points)
2.4 HW: Prove: if $a\equiv b \pmod m$ then $\gcd(a,m)=\gcd(b,m)$. (4 points)
2.5 DO: (a) Prove by induction that every positive integer is a product of prime numbers. (b) (Fundamental Theorem of Arithmetic) Prove the uniqueness of prime factorization. Use the theorem, proved in class, that the prime numbers have the prime property, i.e., $(\forall$ prime numbers $p)(\forall a,b)($ if $p \mid ab$ then $p\mid a$ or $p\mid b))$.
2.6 DO: Prove that the greatest common divisor is unique up to sign.
2.7 DO: Prove: $d$ is a greatest common divisor of $a$ and $b$ if and only if $\div(a) \cap \div(b) = \div(d)$.
2.8 DO: Prove: $\gcd(a,b) = \gcd(a-b, b)$. (Use HW 2.1. Note: for uniqueness, we use the notation $\gcd(a,b)$ to denote the unique nonnegative integer $d$ which is a greatest common divisor of $a,b$. So for instance $\gcd(a,a) = |a|$.)
2.9 DO (equivalence relations vs partitions): Prove that every equivalence relation arises from a partition. (So there is a one-to-one correspondence between the equivalence relatinos on the set $A$ and the partitions of the set $A$.)
2.10 CHALLENGE PROBLEM: LN 4.2.8 (gcd of Fibonacci numbers): $\gcd(F_k,F_{\ell}) = F_d$ where $d=\gcd(k,\ell)$.
1.1 HW Prove: if $u+1\mid u$ then $u= 0$ or $u=-2$. (4 points) (1 bonus point added for elegance)
1.2 DO: Prove: $(\forall k, \ell \ge 1)(\forall a)($ if $k\equiv\ell \pmod 6$ then $a^k\equiv a^{\ell} \pmod 7)$.
1.3 DO: True or false? $(\forall x\ge 1)(\exists y >x)( x+y\mid x^2+y^2)$. What if we require $x\ge 2$? Prove your answers.
1.4 DO: prove the uniqueness of prime factorization using the theorem that the prime numbers have the prime property (if a prime $p$ divides a product $ab$ then $p\mid a$ or $p\mid b$). (Do not hand in the solution of "DO" exercises.)
1.5 DO (multiplication of congruences): Prove: if $a\equiv x \pmod m$ and $b\equiv y \pmod m$ then $ab\equiv xy \pmod m$. (Hint: first prove that if $r\equiv s \pmod m$ then $rx\equiv sx \pmod m$; then use transitivity of congruence mod $m$.)
1.6 DO: Prove by induction on $k\ge 0$: If $a\equiv b \pmod m$ then If $a^k\equiv b^k \pmod m$.
1.7 DO: (a) Calculate $2^{1,000,000} \pmod{101}$ (b) $2^{1000} \pmod{13}$. Your answers should be integers between zero and the modulus.
1.8 CHALLENGE PROBLEM. Find two infinite sets $A, B$ of nonnegative integers such that every nonnegative integer $n$ can be uniquely written as $n=a+b$ for some $a\in A$ and $b\in B$.
1.9 CHALLENGE PROBLEM (Divisor game, LN 4.2.2, part 2). Prove that in the divisor game over the positive divisors of the number $n\ge 2$, the first player has a winning strategy.
If you hand in solutions to CHALLENGE PROBLEMS, please put them on a separate sheet clearly marked "CHALLENGE."