Homework Assignments

Homework will be due once a week. This page will be updated every time a new problem set is posted. Solutions for each problem set will be posted on this page after the assignment is due.

The overall guiding principle in your writing is to remember that your work is meant to be read by a skeptical peer; your job is to write a (logically) convincing argument to this audience. Your answers should always be written in narrative form; you should of course include relevant computations and equations, but these should be situated in the framework of some overall narrative that explains your reasoning, and they should always be naturally integrated into the structure of your writing. You should follow standard rules of composition: write in complete sentences, include appropriate punctuation, group sentences with a common theme into a paragraph, provide appropriate narrative transition when your reasoning takes a significant turn, etc. When writing formal proofs, you should not use abbreviations like $\forall$, $\exists$, $\Rightarrow$. It is acceptable to use the notation $\in$ when describing elements in a formal proof (e.g., "Since $2 \in \mathbb{Z}$, we see that ..."). As a general rule, a mathematical symbol should never start a sentence or follow punctuation; the exception is that you can write a mathematical symbol after a colon which is announcing the beginning of a list of mathematical objects. Of course your work should be legible and neat.

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Though you are welcomed to collaborate with the instructor or your classmates on problems, you are not permitted to reference outside sources or people when completing homework problems. For example, it is a violation of the Honor Code to use any of the following resources to find a solution to a problem: using a search engine to mine the internet for a solution, visiting an online mathematics discussion group, or collaborating with students not registered for this course.

Starting with assignment 2, your homeworks will typically be submitted in two parts, "Part A" and "Part B"). The two parts of this assignment will be submitted in separate folder, and will be graded by separate graders. Please be sure you've written your solutions in a way that allow you to submit your solutions for Part A separate from your solutions for Part B!

assignments

Assignment 1 (due Friday, January 27 at 4pm)

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Not only should your submission include any relevant computational work necessary to reach a numeric solution, but should also include text that justifies your solution. Solutions that are submitted without appropriate justification will receive reduced credit.

1. Complete problem 8 from section 5.1 of the text.
2. Complete problem 10 from section 5.1 of the text.
3. Complete problem 16 from section 5.1 of the text.
4. Complete problem 18 from section 5.1 of the text.
5. Complete problem 22 from section 5.1 of the text.
6. Complete problem 24 from section 5.1 of the text.

Here are the Solutions.

Assignment 2 (due Friday, February 3 at 4pm)

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Not only should your submission include any relevant computational work necessary to reach a numeric solution, but should also include text that justifies your solution. Solutions that are submitted without appropriate justification will receive reduced credit.

Part A

1. Complete problem 10 from section 5.2 of the text.
2. Complete problem 14 from section 5.2 of the text.
3. Complete problem 34 from section 5.2 of the text. (Ignore the part of the problem that asks you to comment on certain values.)
4. Complete problem 44 from section 5.2 of the text.
5. Complete problem 72 from section 5.2 of the text.

Part B

6. A standard deck of card contains 52 cards in total. Each card is decorated with one of four suits ($\heartsuit, \diamondsuit, \clubsuit,\spadesuit$) and one of thirteen values ($2,3,4,5,6,7,8,9,10,J,Q,K,A$). In a game called 5-card draw, players are given 5 cards to form a hand. The order of the cards in their hand doesn't matter, but the worth of the hand is determined by keeping track of certain possible configuations that can appear.
   1. Which is more likely: that a person gets "a pair" for their hand, or that they get "high card" for their hand? (To say that a player gets "a pair" means they have two cards of the same value, with the remaining three cards all of different value from each other and the value of the paired cards. To say that a player gets "high card" means that all five cards are of different value AND not all cards are the same suit AND that the values are not consecutive (for this, the "A" value is funny, because it can either count as $1$ or as the value higher than king).)
   2. What is the probability that a person gets "two pair" for their hand? (This means they have two cards of one value, two cards of a different value, and a fifth card that matches neither of these two values.)
   3. What is the probability that a person gets a "full house"? (This means that they have three cards of one value, and two cards of a different value.)
7. Complete problem 8 from section 5.3 of the text.
8. Complete problem 22 from section 5.3 of the text.
9. Complete problem 34 from section 5.3 of the text.

Here are the Solutions.

Assignment 3 (due Friday, February 10 at 4pm)

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Not only should your submission include any relevant computational work necessary to reach a numeric solution, but should also include text that justifies your solution. Solutions that are submitted without appropriate justification will receive reduced credit.

Part A

1. Complete problem 32 from section 5.3 of the text.
2. Complete problem 18 from section 5.4 of the text.
3. Complete problem 44 from section 5.4 of the text.
4. Complete problem 2(b) from section 5.5.

   [Note: when the book says to verify the identity by block-walking, it means to give a combinatorial proof of the result in which the relevant quantities are thought of in terms of block walking.]

5. Give a combinatorial proof of problem 10 from section 5.5.

Part B

6. Complete problem 8 from section 5.4 of the text.
7. Complete problem 38 from section 5.4 of the text.
8. Complete problem 46 from section 5.4 of the text.
9. Complete problem 64 from section 5.4 of the text.
10. Prove that for any positive integer $n$, one has $$1+2+\cdots+n = \binom{n+1}{2}.$$

    [Hint: Don't prove this with induction, but instead prove that for any positive integer $k$ we have $k = \binom{k+1}{2}-\binom{k}{2}$ and then creatively apply this knowledge.]

Here are the Solutions.

Assignment 4 (due Friday, February 17 at 4pm)

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Not only should your submission include any relevant computational work necessary to reach a numeric solution, but should also include text that justifies your solution. Solutions that are submitted without appropriate justification will receive reduced credit.

Part A

1. Complete problem 19 from section 5.5 of the text.
2. Complete problem 4 from section 6.1 of the text.
3. Complete problem 14 from section 6.1 of the text.
4. Complete problem 16 from appendix A.2 of the text.

Part B

5. Complete problem 22 from section 5.5 of the text. [Hint: what do you get if you compute the derivative of $(1+x)^n$? What special value for $x$ might then be related to the expression in this question?]
6. Complete problem 12 from section 6.1 of the text.
7. Complete problem 24 from section 6.1 of the text.
8. Complete problem 12 from appendix A.2 of the text. [You'll need to use two base cases plus strong induction.]

Non-assigned problems

• Complete problem 2 from appendix A.2 of the text.
• In class we discussed the notion of block-walking and thought of it as answering the question of moving from the origin $(0,0)$ to some other point $(x,y)$ in the first quadrant (where only "right" and "up" movements are allowed). Imagine instead that we want to do a "three dimensional" block walk, where we move from the original $(0,0,0)$ in three-space to some other point $(x,y,z)$ (where $x,y,$ and $z$ are non-negative integers), and the only allowable moves are increasing the first coordinate by $1$, or the second coordinate by $1$, or the third coordinate by $1$. (For instance, we could walk from $(0,0,0)$ to $(2,1,2)$ by going from $(0,0,0)$ to $(0,0,1)$ to $(0,1,1)$ to $(0,1,2)$ to $(1,1,2)$ to $(2,1,2)$.

  Compute the number of ways to walk from the origin to $(105,213,57)$.

• The Fibonacci sequence $F_1,F_2,F_3,\cdots$ is the sequence of positive integers defined by $F_1=1, F_2 = 1$, and so that for all $n \geq 3$ we have $F_n = F_{n-1}+F_{n-2}$. Use induction to prove that for all $n \geq 1$ we have $F_{n+1}F_{n} = F_1^2+\cdots+F_n^2$.
• Show that for every positive integer $k$ there exists some integer $t$ so that $k^5-k=5t$.

Here are the Solutions.

Fake Assignment 5 (due never at 4pm)

This problem set is "fake" in the sense that you will not be submitting your work on these problems to be graded. On the other hand, it is very much "real" in the sense that it covers topics that are relevant for the first midterm. You should spend some time thinking about these problems. Solutions will be posted as soon as they can be written up.

1. For each of the parts of problem 4 from section 6.1 from the text, compute $a_r$.
2. How many ways can you distribute $20$ identical balls between $5$ distinct boxes if each box has between $2$ and $7$ balls?
3. Find the number of integer solutions to $e_1+e_2+e_3=16$ if $e_1 \in \{3,6,9,\cdots\}$ and $e_2 \in \{-1,3,7\}$ and $e_3 \geq -2$.

   (Note: this problem was updated over the weekend to correct the possible values of $e_1$; I had initially mis-typed them.)

   Hint: Here are some handy factorizations: $$ \begin{align*}1-x^3 &= (1-x)(1+x+x^2)\\ 1-x^4 &= (1-x)(1+x)(1+x^2)\\ 1-x^{12} &= (1-x)(1+x)(1+x+x^2)(1+x^2)(1-x+x^2)(1-x^2+x^4). \end{align*}$$

4. Suppose you roll 6 distinct dice, with the first three returning some even number and the second three returning some odd number. How many ways can the total sum of your rolls equal $17$?

   Hint: After you've contracted using our old friends, you will have some factors of $1-x^2$ in the denominator instead of the factors of $1-x$ that we're used to. If you temporarily think of $x^2$ as a new variable (e.g., "$y$"), then you can think about how this denominator would be expressed using the bagel identity.]

5. Complete problem 2 from section 7.1 of the text.
6. Complete problem 9 from section 7.1 of the text.

Here are the Solutions.

Assignment 6 (due Friday, March 3 at 4pm)

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Not only should your submission include any relevant computational work necessary to reach a numeric solution, but should also include text that justifies your solution. Solutions that are submitted without appropriate justification will receive reduced credit.

For all recurrence relations you deduce in these problems, be sure you give a proof of your assertion!

Part A (Please note the instruction in bold at the top of this assignment)

1. Complete problem 4 from section 7.1 of the text.
2. Complete problem 18 from section 7.1 of the text.
3. Complete problem 49(a) from section 71 of the text.
4. Find a recursive formula that counts the number $a_n$ of ways to flip $n$ coins in order so that at least $2$ heads appear, and so that the first two occurrences of heads are nonconsecutive.

Part B (Please note the instruction in bold at the top of this assignment)

5. Complete problem 6 from section 7.1 of the text.
6. Complete problem 24 from section 7.1 of the text.
7. Complete problem 26 from section 7.1 of the text.
8. Complete problem 49(c) from section 7.1 of the text

Non-assigned problems

• Complete problem 11 from section 7.1 of the text.
• Complete problem 23 from section 7.1 of the text.
• Complete problem 45 from section 7.1 of the text.
• Complete problem 46 from section 7.1 of the text.

Here are the Solutions.

Assignment 7 (due Friday, March 10 at 4pm)

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Not only should your submission include any relevant computational work necessary to reach a numeric solution, but should also include text that justifies your solution. Solutions that are submitted without appropriate justification will receive reduced credit.

Part A

1. Find a closed form expression for the sequence $a_n$ which satisfies $a_0=0$ and $a_n=2a_{n-1}+1$ for $n \geq 1$.

   [Hint: $\frac{1}{1-x}\cdot\frac{1}{1-2x} = \frac{2}{1-2x}-\frac{1}{1-x}.$]

2. Find a closed form expression for the sequence $a_n$ which satisfies $a_0=1$ and $a_n = a_{n-1}+n$ for $n \geq 1$.

   [Hint: You will be interested in finding a function whose series expansion is $0+x^1+2\cdot x^2+3\cdot x^3+\cdots$. The bagel identity shows that $\left(\frac{1}{1-x}\right)^2$ is pretty close to the function you want.]

3. Complete problem 8 from section 8.1 of the text.
4. Complete problem 12 from section 8.1 of the text.

Part B

5. Find a closed form expression for the sequence $a_n$ which satisfies $a_0=1$ and $a_n=2a_{n-1}+2^{n-1}$ for $n \geq 1$.
6. Find a closed form expression for the sequence $a_n$ which satisfies $a_0=0, a_1=4, a_2=9$, and $a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}$ for $n \geq 3$. [Hint: You might find it useful to know that $a_0+(a_1-3a_0)x+(a_2-3a_1+3a_0)x^2 = 1+2(1-x)-3(1-x)^2$ for these particular values of $a_0,a_1$ and $a_2$.]
7. Complete problem 10 from section 8.1 of the text.
8. Complete problem 14 from section 8.1 of the text.

Here are the Solutions.

Assignment 8 (due Friday, March 17 at 4pm)

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Not only should your submission include any relevant computational work necessary to reach a numeric solution, but should also include text that justifies your solution. Solutions that are submitted without appropriate justification will receive reduced credit.

Part A

1. Complete problem 36 from section 8.1 of the text.
2. Complete problem 10 from section 8.2 of the text.
3. Complete problem 18 from section 8.2 of the text.
4. Complete problem 40 from section 8.2 of the text. (To say ``at most one void in a suit" means that the hand has either $3$ or the $4$ suits appearing, or all $4$ suits appearing.)

Part B

5. Complete problem 30 from section 8.1 of the text.
6. Complete problem 8 from section 8.2 of the text.
7. Complete problem 12 from section 8.2 of the text.
8. Complete problem 16 from section 8.2 of the text. In addition, answer the following question: how many secret codes are there in which EITHER each vowel (A,E,I,O,U) is assigned to a (unique) different vowel, OR each consonant is assigned to a (unique) different consonant. (Note this is the "inclusive or," meaning that it includes those secret codes where each vowel to be assigned to a unique different vowel and each consonant is assigned to a unique different consonant.)

Non-assigned problems

• Complete problem 2 from section 8.2 of the text.
• Complete problem 22 from section 8.2 of the text.
• Complete problem 28 from section 8.2 of the text.

Here are the Solutions.

Fake Assignment 9 (due never)

This problem set is "fake" in the sense that you will not be submitting your work on these problems to be graded. On the other hand, it is very much "real" in the sense that it covers topics that are relevant for the second midterm. You should spend some time thinking about these problems. Solutions will be posted as soon as they can be written up.

1. Let $p_n$ be the number of block walking paths from $(0,0)$ to $(n,n)$ which have the property that they never pass through a point $(x,y)$ where $y>x$. Prove that $p_n = C_n$.
2. Let $k_n$ be the number of ways to form a sequence of $n$ integers $$1 \leq a_1 \leq a_2 \leq \cdots \leq a_n$$ in such a way that $a_i \leq i$. For example, $k_3 = 5$ since the relevant sequence of length $3$ are $$111 \qquad 112 \qquad 113 \qquad 122 \qquad 123.$$ Prove that $k_n = C_n$.

   [Hint: For any path as described in the previous problem, connect the ``area under a path" from $(0,0)$ to $(n,n)$ to a sequence in $k_n$.]

3. How many block walking paths are there from $(0,0)$ to $(20,20)$ which have ALL of the following properties
   • the path passes through $(10,10)$
   • as the path goes from $(0,0)$ to $(10,10)$, it passes through some point $(x,y)$ for which $y > x$
   • as the path goes from $(10,10)$ to $(20,20)$, it passes through some point $(x,y)$ for which $y < x$
   [Note: the statement of this problem was updated since original posting.]
4. Complete problem 2 from section 1.3 of the text.
5. Complete problem 6 from section 1.3 of the texrt.
6. Write the negation of the following statement: for any positive real numbers $a$ and $b$ there exists some real number $c$ so that $a^c = b$.

Here are the Solutions.

Assignment 10 (due Friday, April 7 at 4pm)

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Not only should your submission include any relevant computational work necessary to reach a numeric solution, but should also include text that justifies your solution. Solutions that are submitted without appropriate justification will receive reduced credit.

For this assignment, you are only required to submit one part (you may choose either Part A or Part B). If you choose to submit both parts, you will earn an additional dropped homework grade to be used at the end of the semester.

Part A

1. Complete problem 16 from section 1.1 of the text.
2. Complete problem 4 from section 1.2 of the text.
3. Complete problem 6(a)-(c) from section 1.2 of the text.
4. Complete problem 14 from section 1.2 of the text.

Part B

5. Complete problem 18 from section 1.1 of the text.
6. Complete problem 2 from section 1.2 of the text. (For this problem, ignore the word "directed" in the problem prompt.)
7. Complete problem 6(d)-(f) from section 1.2 of the text.
8. Complete problem 8 from section 1.2 of the text.

Here are the Solutions.

Assignment 11 (due Friday, April 14 at 4pm)

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Not only should your submission include any relevant computational work necessary to reach a numeric solution, but should also include text that justifies your solution. Solutions that are submitted without appropriate justification will receive reduced credit.

Part A

1. Give planar representations for the graphs from problem 3(e) and 3(g) from section 1.4 of the text.
2. Complete problem 8 from section 1.4 of the text. Additionally, give a planar representation of a graph which satisfies these properties.
3. Complete problem 12(a,b) from section 1.4 of the text. [Hint: you can use the fact that neither of these graphs has crossing number $0$.]
4. A local math club starts a competition where they ask participants to draw a connected plane graph representation of a graph with $8$ vertices and $10$ edges. The club asks entrants to try to maximize the number of regions in their depiction.
   1. Draw a graph that you can enter into the competition.
   2. Your friend Sally is very competitive. She sees your drawing and insists that she can come up with another entry that will beat yours. What do you say to Sally?

Part B

(These problems will require some ideas that we'll discuss in class on Monday, April 10.)

5. Complete problem 14 from section 1.4 of the text.
6. Complete problem 16 from section 1.4 of the text.
7. Complete problem 18(a) from section 1.4 of the text.
8. Complete problem 24 from section 1.4 of the text.

Here are the Solutions

Assignment 12 (due Friday, April 21 at 4pm)

If you collaborate with anyone on this problem set, include this information at the top of your submission (write something like ``I collaborated with..."). Problems marked "($\star$)" should be completed by yourself, or with assistance from the instructor.

Not only should your submission include any relevant computational work necessary to reach a numeric solution, but should also include text that justifies your solution. Solutions that are submitted without appropriate justification will receive reduced credit.

Part A

1. For the left graph on problem 6(c) and the left graph on problem 6(d) from section 1.2 of the text, answer the following questions.
   1. What does the $3|v|-6$ theorem say about the planarity of the graph?
   2. Can you use the $2|v|-4$ theorem to say anything about the planarity of the graph?
   3. Find either a $K_5$ or a $K_{3,3}$ configuration,
2. Compete problem 26 from section 1.4 of the text.

   [Note: this problem shows us that we can't draw "nice" Venn diagrams for $4$ sets.]

3. Compete problem 8 from section 2.1 of the text.
4. Compete problem 12(c) from section 2.1 of the text. (This problem involves direct Euler cycles on a direct graph. A directed graph is just like a regular graph, but now the edges have a direction (moving from one vertex to another vertex). When walking along the edges of a direct graph, you are only allowed to walk in the direction of the edge.)

Part B

5. Compete problem 6 from section 1.4 of the text.
6. Compete problem 2 from section 2.1 of the text.
7. Compete problem 10 from section 2.1 of the text.
8. Compete problem 16 from section 2.1 of the text.

Here are the Solutions.

Fake Assignment 13 (due never)

This problem set is "fake" in the sense that you will not be submitting your work on these problems to be graded. On the other hand, it is very much "real" in the sense that it covers topics that are relevant for the third midterm. You should spend some time thinking about these problems. Solutions will be posted as soon as they can be written up.

1. In class we gave a sufficient condition for Hamiltonian-ness. Prove that the converse of this result is false by finding a Hamiltonian graph with at least $n$ vertices and such that $\deg(x)+\deg(y) < |V(G)|$ for some pair of non-adjacent vertices $x,y \in V(G)$.
2. Complete problem 2 from section 2.2 of the text.
3. Complete problem 4(a,d,e,f) from section 2.2 of the text.
4. Complete problem 6 from section 2.2 of the text.
5. Complete problem 16 from section 2.2 of the text.
6. Draw all non-isomorphic tress with six vertices.
7. Prove that any tree is planar.
8. A forest is a graph whose connected components are all trees. Suppose that $G$ is a forest with $n$ disconnected components. How many edges does $G$ have?

Here are the Solutions.

Fake Assignment 14 (due never)

This problem set is "fake" in the sense that you will not be submitting your work on these problems to be graded. On the other hand, it is very much "real" in the sense that it covers topics that are relevant for the final exam. You should spend some time thinking about these problems. Since all assigned problems are odd numbered, I won't be posting solutions.

1. Complete problem 1(c,d,e,i) from section 2.3 of the text.
2. Complete problem 7 from section 2.3 of the text.
3. Complete problem 9 from section 2.3 of the text. [Hint: Iowa]
4. Complete problem 11 from section 2.3 of the text.
5. Complete problem 1 from section 2.4 of the text.
6. Complete problem 7(a) from section 2.4 of the text.
7. Complete problem 9(a) from section 2.4 of the text.