3.
Hint.
First figure out what each statement is saying. For part (c), you don’t need to assume the domain is an infinite set.
Appendix A Selected Hints
1 Logic and Proofs
1.1 Mathematical Statements
Additional Exercises
1.2 Implications
Additional Exercises
4.
Hint.
Of course there are many answers. It helps to assume that the statement is true and the converse is not true. Think about what that means in the real world, and then start saying it in different ways. Some ideas: Use “necessary and sufficient” language, use “only if,” consider negations, use “or else” language.
1.3 Rules of Logic
Additional Exercises
1.
Hint.
You could probably reason through the cases by hand, but try making a truth table. Use two statements, \(P\) being “we are cousins” and \(Q\) being “we are both knaves”.
4.
Hint.
You should write down three statements using the symbols \(P, Q, R, S\text{.}\) If Geoff is a truth-teller, then all three statements would be true. If he was a liar, then all three statements would be false. But in either case, we don’t yet know whether the four atomic statements are true or false, since he hasn’t said them by themselves.
A truth table might help, although it is probably not entirely necessary.
8.
Hint.
- There will be three rows in which the statement is false.
- Consider the three rows that evaluate to false, and say what the truth values of \(T\text{,}\) \(S\text{,}\) and \(P\) are there.
- You are looking for a row in which \(P\) is true and the whole statement is true.
9.
Hint.
Write down three statements, and then take the negation of each (since he is a liar). You should find that Tommy ate one item and drank one item. (\(Q\) is for cucumber sandwiches.)
11.
Hint.
What do these concepts mean in terms of truth tables?
14.
Hint.
Try an example. What if \(P(x)\) was the predicate, “\(x\) is prime”? What if it was, “If \(x\) is divisible by 4, then it is even”? Of course examples are not enough to prove something in general, but that is entirely the point of this question.
15.
Hint.
It might help to translate the statements into symbols and then use the formulaic rules to simplify negations (i.e., rules for quantifiers and De Morgan’s laws). After simplifying, you should get \(\forall x(\neg E(x) \wedge \neg O(x))\) for the first one, for example. Then translate this back into English.
1.4 Proofs
Additional Exercises
6.
Hint.
One of the implications will be a direct proof; the other will be a proof by contrapositive.
7.
Hint.
This is really an exercise in modifying the proof that \(\sqrt{2}\) is irrational. There you proved things were even; here they will be multiples of 3.
8.
Hint.
Part (a) should be a relatively easy direct proof. Look for a counterexample for part (b).
10.
Hint.
A proof by contradiction would be reasonable here, because then you get to assume that both \(a\) and \(b\) are odd. Deduce that \(c^2\) is even, and therefore a multiple of 4 (why? and why is that a contradiction?).
12.
Hint.
Use a different style of proof for each part.
14.
Hint.
Note that if \(\log(7) = \frac{a}{b}\text{,}\) then \(7 = 10^\frac{a}{b}\text{.}\) Can any power of 7 be the same as a power of 10?
15.
Hint.
What if there were? Deduce that \(x\) must be odd, and continue towards a contradiction.
16.
Hint.
Prove the contrapositive by cases. There will be 4 cases to consider.
17.
Hint.
Your friend’s proof is a proof, but of what? What implication follows from the given proof? Is that helpful?
19.
Hint.
Consider the set of numbers of friends that everyone has. If everyone had a different number of friends, this set must contain 20 elements. Is that possible? Why not?
20.
Hint.
This feels like the pigeonhole principle, although a bit more complicated. At least, you could try to replicate the style of proof used by the pigeonhole principle. How would the episodes need to be spaced out so that no two of your sixty were exactly 4 apart?
1.5 Proofs about Discrete Structures
Additional Exercises
1.
Hint.
To prove that \(A \subseteq B\) if and only if \(A \cup B = B\text{,}\) you need to prove two implications:
- If \(A \subseteq B\text{,}\) then \(A \cup B = B\text{.}\)
- If \(A \cup B = B\text{,}\) then \(A \subseteq B\text{.}\)
To prove two sets are equal, we usually prove that each is a subset of the other.
2 Graph Theory
2.1 Problems and Definitions
Practice Problems
6.
Hint.
Remember that \(P_n\) is the path that contains \(n\) edges and \(n+1\) vertices.
Additional Exercises
3.
Hint.
Both situations are possible. Go find some examples.
6.
Hint.
The bipartite graph is a little tricky. You will definitely want a complete bipartite graph, but it could be \(K_{5,5}\) or maybe \(K_{1,9}\text{,}\) or …
7.
Hint.
The first graph is bipartite, which can be seen by labeling it as follows.
Two of the remaining three are also bipartite.
8.
Hint.
\(C_4\) is bipartite; \(C_5\) is not. What about all the other values of \(n\text{?}\)
11.
Hint.
You should be able to deduce everything directly from the definition. However, perhaps it would be helpful to know that the \(N\) stands for neighborhood.
12.
Hint.
Be careful to make sure the edges are not “directed.” In a graph, if \(a\) is adjacent to \(b\text{,}\) then \(b\) is adjacent to \(a\text{.}\) In the language of relations, we say that the edge relation is symmetric.
13.
Hint.
You might want to answer the questions for some specific values of \(n\) to get a feel for them, but your final answers should be in terms of \(n\text{.}\)
14.
Hint.
Try a small example first: Any graph with 8 vertices must have two vertices of the same degree. If not, what would the degree sequence be?
15.
Hint.
Use the handshake lemma 2.1.8. What would happen if all the vertices had degree 2?
2.2 Trees
Additional Exercises
3.
Hint.
Careful: the graphs might not be connected.
4.
Hint.
Try Exercise 2.
5.
Hint.
Try a proof by contradiction, and consider a spanning tree of the graph.
7.
Hint.
For part (b), trying some simple examples should give you the formula. Then you just need to prove it is correct.
8.
Hint.
Examining the proof of Proposition 2.2.2 gives you most of what you need, but make sure to just give the relevant parts, and take care to not use proof by contradiction.
9.
Hint.
Minimality here should be in terms of the number of vertices. If you had a minimum counterexample and removed a leaf vertex, the resulting graph will be a smaller tree, so...
10.
Hint.
If \(e\) is the root, then \(b\) will have three children (\(a\text{,}\) \(c\text{,}\) and \(d\)), all of which will be siblings and have \(b\) as their parent. \(a\) will not have any children.
In general, how can you determine the number of children a vertex will have, if it is not a root?
14.
Hint.
There is an example with 7 edges.
15.
Hint.
The previous exercise will be helpful.
16.
Hint.
Note that such an edge, if removed, would disconnect the graph. We call graphs that have an edge like this 1-connected.
2.3 Planar Graphs
Additional Exercises
3.
Hint.
What would Euler’s formula tell you?
5.
Hint.
You can use the handshake lemma to find the number of edges, in terms of \(v\text{,}\) the number of vertices.
11.
Hint.
What is the length of the shortest cycle? (This quantity is usually called the girth of the graph.)
14.
Hint.
The girth of the graph is 4.
15.
Hint.
What has happened to the girth? Careful: We have a different number of edges as well. Better check Euler’s formula.
2.4 Euler Trails and Circuits
Additional Exercises
7.
Hint.
This is harder than the previous three questions. Think about which “side” of the graph the Hamilton path would need to be on at every other step.
9.
Hint.
If you read off the names of the students in order, you would need to read each student’s name exactly once, and the last name would need to be of a student who was friends with the first. What sort of a cycle is this?
10.
Hint.
Draw a graph with 6 vertices and 8 edges. What sort of walk would be appropriate?
2.5 Coloring
Additional Exercises
7.
Hint.
For (a), you will want the teams to be vertices and games to be edges. Which does it make sense to color?
10.
Hint.
The chromatic number is 4. Now prove this!
Note that you cannot use the 4-color theorem, or Brooke’s theorem, or the clique number here. In fact, this graph, called the Grötzsch graph, is the smallest graph with chromatic number 4 that does not contain any triangles.
13.
Hint.
You can color \(K_5\) in such a way that every vertex is adjacent to exactly two blue edges and two red edges. However, there is a graph with only 5 edges that will result in a vertex incident to three edges of the same color, no matter how they are colored. What is it, and how can you generalize?
14.
Hint.
The previous exercise is useful as a starting point.
2.8 Chapter Summary
Chapter Review
2.8.23.
Hint.
You might want to give the proof in two parts. First prove by induction that the cycle \(C_n\) has \(v=e\text{.}\) Then consider what happens if the graph is more than just the cycle.
3 Counting
3.2 Combining Outcomes
Practice Problems
9.
Hint.
Break the question into 3 cases.
Additional Exercises
2.
Hint.
For a simpler example, there are 4 divisors of \(6 = 2\cdot 3\text{.}\) They are \(1 = 2^0\cdot 3^0\text{,}\) \(2 = 2^1\cdot 3^0\text{,}\) \(3 = 2^0\cdot 3^1\text{,}\) and \(6 = 2^1\cdot 3^1\text{.}\)
3.3 Non-Disjoint Outcomes
Practice Problems
6.
Hint.
To find out how many numbers are divisible by 8 and 9, for example, take \(790/(8\cdot9)\) and round down.
Additional Exercises
1.
Hint.
For part (a) you could use the formula for PIE, but for part (b) you might be better off drawing a Venn diagram.
2.
Hint.
You could consider cases. For example, any number of the form ODD-ODD-EVEN will have an even sum. Alternatively, how many three-digit numbers have the sum of their digits even if the first two digits are 54? What if the first two digits are 19?
3.4 Combinations and Permutations
Additional Exercises
1.
Hint.
If you pick any three points, you can get a triangle, unless those three points are all on the \(x\)-axis or on the \(y\)-axis. There are other ways to start this as well, and any correct method should give the same answer.
3.5 Counting Multisets
Practice Problems
6.
Hint.
The probability will be 1 divided by however many different combinations of 11 coins your friend could have.
Additional Exercises
3.
3.b
Hint.
This really requires proving four facts. That every multiset corresponds to at least one diagram, and that every diagram corresponds to at least one multiset. Then that every multiset corresponds to at most one diagram, and that every diagram corresponds to at most one multiset. In other words, we must prove that the function is well defined, injective, and surjective.
3.6 Combinatorial Proofs
Additional Exercises
3.
Hint.
There will be 185 triangles. But to find them …
- How many vertices of the triangle can be on the horizontal axis?
- Will any three dots work as the vertices?
4.
Hint.
The answer is 120.
6.
Hint.
Try Exercise 5.
7.
Hint.
What if you wanted a pair of co-maids-of-honor?
8.
Hint.
For the combinatorial proof: What if you don’t yet know how many bridesmaids you will have?
9.
Hint.
Count handshakes.
13.
Hint.
This one might remind you of Example 3.6.6
14.
Hint.
For the lattice paths, think about what sort of paths \(2^n\) would count. Not all the paths will end at the same point, but you could describe the set of end points as a line.
16.
Hint.
How many edges does \(K_n\) have? One of the two graphs will not be connected (unless \(j=1\) ).
3.7 Applications to Probability
Practice Problems
7.
Hint.
You could list out all the ways you can get a 6, or use sticks and stones.
Additional Exercises
4.
Hint.
Use complementary probabilities. And don’t be surprised if your answer is larger than you would have expected.
3.9 Chapter Summary
Chapter Review
3.9.16.
Hint.
Use stars and bars.
4 Sequences
4.1 Describing Sequences
Practice Problems
4.
Hint.
Try adding or subtracting the same small number from each term to see if you recognize the sequence.
5.
Hint.
Try adding, subtracting, or dividing each term by a constant to make the sequence more recognizable.
For part (d), try expressing the sequence as the sum of two well known sequences.
Additional Exercises
8.
Hint.
You will want to write out the sequence, guess a closed formula, and then verify that you are correct.
9.
Hint.
Write out the sequence, guess a recursive definition, and verify that the closed formula is a solution to that recursive definition.
12.
Hint.
Try an example: When you draw the 4th line, it will cross three other lines and so will be divided into four segments, two of which are infinite. Each segment will divide a previous region into two.
13.
Hint.
Consider three cases: The last digit is a 0, a 1, or a 2. Two of these should be easy to count, but strings ending in 0 cannot be proceeded by a 2, so they require a little more work.
15.
Hint.
Think recursively, like you did in Pascal’s triangle.
16.
Hint.
There is only one way to tile a \(2 \times 1\) board, and two ways to tile a \(2\times 2\) board (you can orient the dominoes in two ways). In general, consider the two ways the domino covering the top left corner could be oriented.
4.2 Rate of Growth
Additional Exercises
5.
Hint.
We can write the recurrence relation as \(\frac{a_n}{a_{n-1}} = r\text{.}\) What happens when you multiply all the different versions of this recurrence relation (for different values of \(n\)) together?
6. Telescoping to find a sum.
Hint.
Using the fact that \(T_n = \frac{n(n+1)}{2}\text{,}\) each term in the sequence is \(\frac{2}{n(n+1)}\text{.}\)
What is the result of the following fraction subtraction: \(\frac{2}{3}- \frac{2}{4}\text{,}\) or \(\frac{2}{4}-\frac{2}{5}\text{?}\) What is happening in general?
4.4 Exponential Sequences
Practice Problems
3.
Hint.
Use telescoping or iteration.
4.5 Proof by Induction
Additional Exercises
9.
Hint.
It is not possible to score exactly 11 points. Can you prove that you can score \(n\) points for any \(n \ge 12\text{?}\)
11.
Hint.
Start with \((k+1)\)-gon, and divide it up into a \(k\)-gon and a triangle.
15.
Hint.
For the inductive step, you can assume you have a strictly increasing sequence up to \(a_k\) where \(a_k \lt 100\text{.}\) Now you just need to find the next term \(a_{k+1}\) so that \(a_{k} \lt a_{k+1} \lt 100\text{.}\) What should \(a_{k+1}\) be?
17.
Hint.
For the inductive case, you will need to show that \((k+1)^2 + (k+1)\) is even. Factor this out, and locate the part of it that is \(k^2 + k\text{.}\) What have you assumed about that quantity?
18.
Hint.
This is similar to Exercise 15, although there you were showing that a sequence had all its terms less than some value, and here you are showing that the sum is less than some value. But the partial sums forms a sequence, so this is actually very similar.
19.
Hint.
We have already proved this without using induction, but looking at it inductively sheds light onto the problem (and is fun).
The question you need to answer to complete the inductive step is, how many new handshakes take place when a person \(k+1\) enters the room? Why does adding this give you the correct formula?
20.
Hint.
Here’s the idea: Since every entry in Pascal’s triangle is the sum of the two entries above it, we can get the \(k+1\)st row by adding up all the pairs of entry from the \(k\)th row. But doing this uses each entry on the \(k\)th row twice. Thus each time we drop to the next row, we double the total. Of course, row 0 has sum \(1 = 2^0\) (the base case). Now try to make this precise with a formal induction proof. You will use the fact that \({n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\) for the inductive case.
21.
Hint.
To see why this works, try it on a copy of Pascal’s triangle. We are adding up the entries along a diagonal, starting with the 1 on the left-hand side of the 4th row. Suppose we add up the first 5 entries on this diagonal. The claim is that the sum is the entry below and to the left of the last of these 5 entries. Note that if this is true, and we instead add up the first 6 entries, we will need to add the entry one spot to the right of the previous sum. But these two together give the entry below them, which is below and left of the last of the 6 entries on the diagonal. If you follow that, you can see what is going on. But it is not a great proof. A formal induction proof is needed.
23.
Hint.
You are allowed to assume the base case. For the inductive case, group all but the last function together as one sum of functions, and then apply the usual sum of derivatives rule, and then the inductive hypothesis.
24.
Hint.
For the inductive step, we know by the product rule for two functions that
\begin{equation*}
(f_1f_2f_3 \cdots f_k f_{k+1})' = (f_1f_2f_3\cdots f_k)'f_{k+1} + (f_1f_2f_3\cdots f_k)f_{k+1}'\text{.}
\end{equation*}
Then use the inductive hypothesis on the first summand, and distribute.
25.
Hint.
You can inductively assume that from the first \(n-2\) implications you can deduce \(P_1 \imp P_{n-1}\text{.}\) Then you can use a truth table to verify that this simplified deduction rule is valid.
4.6 Strong Induction
Additional Exercises
1.
Hint.
If you have three base cases, can you always be sure you can get three points more?
2.
Hint.
Start with a \((k+1)\)-gon, and divide it into two smaller polygons.
4.
Hint.
As with the previous question, we will want to subtract something from \(n\) in the inductive step. There we subtracted the largest power of 2 less than \(n\text{.}\) So what should you subtract here?
Note that you will still need to take care here that the sum you get from the inductive hypothesis, together with the number you subtracted, will be a sum of distinct Fibonacci numbers. In fact, you could prove that the Fibonacci numbers in the sum are non-consecutive!
6.
Hint.
You will need to use strong induction. For the inductive case, try multiplying \(\left (x^k + \frac{1}{x^{k}}\right)\left(x+\frac{1}{x}\right)\text{,}\) and collect which terms together are integers.
8.
Hint.
You will need three base cases. This is a very good hint actually, as it suggests that to prove \(P(n)\) is true, you would want to use the fact that \(P(n-3)\) is true. So somehow you need to increase the number of squares by 3.
4.7 Chapter Summary
Chapter Review
4.7.14.
Hint.
- \((n+1)^{n+1} > (n+1) \cdot n^{n}\text{.}\)
- This should be similar to the other sum proofs. The last bit comes down to adding fractions.
- Write \(4^{k+1} - 1 = 4\cdot 4^k - 4 + 3\text{.}\)
- One 9-cent stamp is 1 more than two 4-cent stamps, and seven 4-cent stamps is 1 more than three 9-cent stamps.
- Be careful to actually use induction here. The base case: \(2^2 = 4\text{.}\) The inductive case: Assume \((2n)^2\) is divisible by 4, and consider \((2n+2)^2 = (2n)^2 + 4n + 4\text{.}\) This is divisible by 4 because \(4n +4\) clearly is, and by our inductive hypothesis, so is \((2n)^2\text{.}\)
4.7.15.
Hint.
This is a straight-forward induction proof. Note that you will need to simplify \(\left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3\) and get \(\left(\frac{(n+1)(n+2)}{2}\right)^2\text{.}\)
4.7.16.
Hint.
There are two base cases \(P(0)\) and \(P(1)\text{.}\) Then, for the inductive case, assume \(P(k)\) is true for all \(k \lt n\text{.}\) This allows you to assume \(a_{n-1} = 1\) and \(a_{n-2} = 1\text{.}\) Apply the recurrence relation.
5 Discrete Structures Revisited
5.1 Sets
Exercises
7.
Hint.
You should be able to write all of them out. Don’t forget \(A\) and \(B\text{,}\) which are also candidates for \(C\text{.}\)
14.
Hint.
It might help to think about what the union \(A_2
\cup A_3\) is first. Then think about what numbers are not in that union. What will happen when you also include \(A_5\text{?}\)
17.
Hint.
We are looking for a set containing 16 sets.
18.
Hint.
Write these out, or at least start to and look for a pattern.
29.
Hint.
It looks like you should be able to define the set \(A\) like this. But consider the two possible values for \(\card{A}\text{.}\)
5.2 Functions
Exercises
2.
Hint.
Since the domain and codomain are the same size, is it possible for a function to be injective but not surjective, or surjective but not injective?
20.
Hint.
Work with some examples. What if \(f = \twoline{1\amp 2 \amp 3}{a \amp a \amp b}\) and \(g = \twoline{a\amp b \amp c}{5
\amp 6 \amp 7}\text{?}\)
25.
Hint.
To find the recurrence relation, consider how many new handshakes occur when person \(n+1\) enters the room.
29.
Hint.
One of these is not always true. Try some examples!
6 Additional Topics
6.1 Generating Functions
Exercises
10.
Hint.
You should “multiply” the two sequences.
6.2 Introduction to Number Theory
Exercises
13.
Hint.
First reduce each number modulo 9, which can be done by adding up the digits of the numbers.
18.
Hint.
Solve the Diophantine equation \(13x + 20 y = 2\) (why?). Then consider which value of \(k\) (the parameter in the solution) is optimal.
