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.
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.
11.
14.
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.
7.
8.
10.
12.
14.
15.
16.
17.
19.
20.
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:
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
5.
Additional Exercises
3.
6.
7.
8.
11.
12.
13.
14.
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.
4.
Hint.
Try ExerciseΒ 2.
5.
7.
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.
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.
15.
16.
2.3 Planar Graphs
Additional Exercises
3.
5.
11.
14.
15.
2.4 Euler Trails and Circuits
Additional Exercises
7.
9.
10.
2.5 Coloring
Additional Exercises
6.
6.c
7.
7.a
10.
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.
2.8 Chapter Summary
Chapter Review
2.8.23.
3 Counting
3.2 Combining Outcomes
Practice Problems
9.
Additional Exercises
2.
3.3 Non-Disjoint Outcomes
Practice Problems
6.
Additional Exercises
1.
2.
3.4 Combinations and Permutations
Additional Exercises
1.
3.5 Counting Multisets
Practice Problems
6.
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.
4.
6.
Hint.
Try ExerciseΒ 5.
7.
8.
9.
13.
Hint.
This one might remind you of ExampleΒ 3.6.6
14.
16.
3.7 Applications to Probability
Practice Problems
7.
Additional Exercises
4.
3.9 Chapter Summary
Chapter Review
3.9.16.
4 Sequences
4.1 Describing Sequences
Practice Problems
4.
5.
Additional Exercises
8.
9.
12.
13.
15.
16.
4.2 Rate of Growth
Additional Exercises
5.
6. Telescoping to find a sum.
4.4 Exponential Sequences
Practice Problems
3.
4.5 Proof by Induction
Additional Exercises
9.
11.
15.
17.
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.
24.
Hint.
25.
4.6 Strong Induction
Additional Exercises
1.
2.
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.
8.
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{.}\)