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 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.
9.
11.
14.
15.
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.
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.
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
7.
10.
13.
Hint.
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 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 st row by adding up all the pairs of entry from the th row. But doing this uses each entry on the th row twice. Thus each time we drop to the next row, we double the total. Of course, row 0 has sum (the base case). Now try to make this precise with a formal induction proof. You will use the fact that 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.
25.
4.6 Strong Induction
Additional Exercises
1.
2.
4.
Hint.
As with the previous question, we will want to subtract something from in the inductive step. There we subtracted the largest power of 2 less than 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.
-
This should be similar to the other sum proofs. The last bit comes down to adding fractions.
-
Write
-
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:
The inductive case: Assume is divisible by 4, and consider This is divisible by 4 because clearly is, and by our inductive hypothesis, so is