 All HomeworkComments for all assignments
 Exercises taken from Discrete Mathematics and its Applications,
Seventh Edition unless otherwise noted.
 You must show all of your work for each problem!
 Points will be deducted if you do not show all of your work.
 Each problem is generally worth 10 points.
Problems with multiple parts may be assigned more points if there are enough parts or
each part is significant enough.
 The Review Questions are always related to the section that will be discussed on the assignment due date.
Homework 1Section  Problem


1.1  10ceg
 1.1  14cef
 N/A  The questions below

This question is worth double.
Answer the following questions based on the course website.
For each one, give an answer and specify which link on the left you clicked to get
the information.
For instance, your answer for one might be:
45. Certainly (Gradebook)
Each question is worth 1 point, right or wrong.
 How many assignments can you turn in late?
 If you turn in an assignment 2 minutes into the class, is it late?
 What percentage of your grade are exams? What percent is each exam?
 If you want to see me in my office, what should you do?
 If you want to submit anonymous feedback, can you? How?
 Does neatness/organization of homework matter at all?
 Do I have to show all of my work on homework problems, whether or not the problem says so?
 Can you tell exactly what grade you got on any assignment in the
course at any time? Can you get an idea of how your grade compares with the grade of others?
 If you have a disability of any kind, what should you do?
 Will I give extra credit assignments to students who are not performing
well in the course?
 What is the reading assignment for Monday?
 At exactly what time are homework assignments due (be precise)?
 How many problems are on Homework 4?
 Is there class on Friday? Is it required?
 What dates are the exams? Do you plan on being in class on those days?
 Is reading the textbook optional?
 Is attending department colloquiums required? How many? What day/time are they usually?
 Are there any solutions available for the exercises in the book? If so, where?
 What should you do after every homework assignment is handed back?
 What is the earliest possible date and time you can leave Hope College at the end of the semester?
Homework 2Section  Problems  Notes


1.1  18
 1.1  32ae
 1.2  8
 1.2  10
 Review Questions  4ab  On page 111 
Homework 3Section  Problem  notes


1.1  20
  28  Phrases these using the same language that is in the original.
  36f  Show intermediate columns and list the variable columns and rows in the same order as the examples in the textbook.
 1.3  10d  See previous comment. Also, explain why the truth table justifies your answer.
  14  Clearly justify your answer.
  16  Read the paragraph before the problem.
 Review Questions  6  On page 111 
Homework 4Section  Problem  Comments


1.1  42  Remember to say something to justify your answers. It doesn't have to be much.
 1.2  18  Clearly justify your answer(s).
 1.4  4  Briefly explain each.
  8  One of these is tricky. Think carefully.
  50  Define a universe of discourse and choose statements P and Q on that universe such that the given statements have different truth values. Notice that 49 is similar... 
Homework 5Section  Problem  Notes


1.3  22  Read the paragraph before the problem and do the problem according to the directions given there.
 1.4  14  Justify your answers by providing an example, counter example, and/or brief explanation.
 1.6  8  Express the statements using predicates, quantifiers, and logical connectives (e.g. negation, and, or). Then identify the rules used.
  16  Clearly state whether or not the argument is correct and give the specific rule(s) of inference or fallacy used.
 Review Question  10a  On page 111. 
Homework 6Section  Problems  Notes


1.2  40  Look at #41 to see what sort of answer it is looking for.
 1.3  58  Briefly describe how you arrived at your answer.
 1.4  32  See the solution to #33 for an example of what it is asking for. In particular, for each one you need to: Specify the domain and define appropriate predicate(s).
 Express the statement using your predicate(s) and the appropriate quantifier(s).
 Negate the expression and then move the negation as far to the right as you can.
 Express the negation in English, phrasing it "nicely".
(This one is worth 20 points)
 1.7  2  Be very precise, using the definition of even (In particular, you cannot not say, for instance, that 10x+14y6z+12 is even. You must use algebra to make it look like 2k for some integer k. Similarly for future problems with either odd or even.). A common mistake on this kind of proof is to write it in such a way that you are essentially assuming the two numbers are the same number without realizing it.
  16  As with the previous problem, make sure you don't construct a proof that only ends up proving it for m=n.
 Review Question  12  On page 111 
Homework 7Section  Problem  Notes


1.1  22
 1.3  30  Begin by realizing that it can only be false if the premise is true but the conclusion is false. Then argue that if the conclusion is false, the premise is, too.
 1.4  56
 1.7  18  Take the assumption that n is an integer as a given, and read the problem as "If 3n+2 is even, then n is even."
 1.8  6  Make sure to use the official definitions of odd and even throughout the proof. Also, the phrase about opposite parity simply means that one is odd and the other is even. 
Homework 8Section  Problem  Notes


1.3  28  Read the paragraph before the problem.
 1.4  44
 1.6adf  10
 1.7  32  Three keys to this problem: First, you need each to be equivalent to the others. This will require 3 or 4 miniproofs, depending on how you go about it. Second, you do not start all of the miniproofs by assuming x is rational. Finally, you must use the formal definition of rational throughout your proof.
 1.8  30  Make sure you consider every possibility.
  36  There is in some sense an obvious number to try. That is, given two distinct numbers, there is one number that you can be certain is between them. The trick is then to prove that this number is irrational. If it isn't clear how to do that, what sort of proof comes to mind?
 Review Question  1  On page 186
  3  On page 186 
Homework 9Section  Problem  Notes


1.2  42
 1.3  44  Read the paragraph before problem 43. Use the result of Problem 43. In other words, you just need to show that you can implement ∨ using ¬ and ∧.
 1.7  24
 2.1  16  In case it isn't clear, give a single diagram showing the relationship between A, B, and C.
  28
  36
 2.2  4  If the answer to any of these is A or B, say so. 
Homework 10Section  Problem  Notes


1.1  44  Show intermediate results
 1.6  20  Explain why or why not, specifying rules of inference/fallacies.
 1.8  8+addition  Read carefully. It says "not exceeding it", so the number itself should be included. The addition is to answer the same problem, but with the phrase "not exceeding it" replaced with "less than it".
 2.2  12  Use a "set containment proof". See Examples 10 and 12. Your proof should contain phrases like "Let x∈FOO", "by the definition of union", "thus FOO⊆FERZLE", etc.
  16a  See note for the previous problem.
 2.3  8abcd
  12+addition  Also specify whether each is onto. For both onetoone and onto, justify. 
Homework 11Section  Problem  Notes


1.4  36
 1.7  38  Clearly show why your counterexample works. Also, read the problem carefully so you do not come up with a false counterexample.
 2.1  30  Prove your conclusion.
 2.2  16e  Use a "set containment proof". Your proof should contain phrases like "Let x∈FOO", "by the definition of union", "thus FOO⊆FERZLE", etc.
 2.3  20  N is the set of natural numbers ({0, 1, 2, ...}). Also, when part c says "different than the identity", it means it cannot always map a number to itself, regardless of what the function looks like. So functions like f(x)=⌊x⌋ or f(x)=2*(x/2) don't count.
  36  Make sure you clearly indicate which answer is which.
 2.4  4ad
  16b
  26bh  Do not give a recursive formula. I should be able to determine a_{100} by just plugging in 100, for instance. Assume the first term is a_{1.
}   32c  Make sure to show your work.
  34b  Make sure to show your work.
  40  Make sure to show your work. 
Homework 12Section  Problem  Notes


2.2  26c
 2.3  56
  58
 2.4  26a
 Review Question  1ab  On page 378 
Homework 13Section  Problem  Notes


2.2  24  You may use any of the valid techniques from the book.
 2.4  26e  Do not give a recursive formula. I should be able to determine a_{100} by just plugging in 100, for instance. Assume the first term is a_{1}. If you are having a hard time with this, try adding or subtracting 1 from the term and seeing if the numbers look more familiar. Then you should be able to determine a formula.
  32d
  34d
 5.1  4  This problem is much easier if you assume P(k1) and show P(k).
  50 
Homework 14Section  Problem  Notes


1.6  24
 2.4  16e
 5.1  6  Look at the solutions to similar problems (e.g. #5, #7)
  18  Look at the solution to problem #19
 5.2  4  Look at problem #3 and the solution in the back of the book. 
Homework 15Section  Problem  Notes


1.4  10
 2.3  38  Your answer should be one or more equations that relate the constants (e.g. ab=c+d). An answer that gives an example of specific values of constants that work is not enough.
 5.1  10  It should be a very simple formula.
 5.2  8  Your answer should be something of the form "For $5n, where n≥a" for some integer a (which you need to find). Then you will need strong induction to prove it. This is probably one of the more confusing problems, but look for the solutions of the similar ones in the book for some help.
  10  I will give you the answer to the first part: It is always n1 breaks. For the inductive step, don't over think it. When you break the chocolate the first time, just make up sizes it breaks into (e.g. one piece will be size i (where i is at least 1), and the other then has to be what?). Strong induction makes this pretty straightforward.
  30
  32 
Homework 16Section  Problem  Notes


1.3  62b  Clearly justify your answer.
 5.1  20  Don't make this one harder than it is. It is fairly straightforward.
 5.3  8ab  For b: recursive definitions do not always have to be based on the immediately preceding term.
  12  Recall that f_{0}=0 and f_{1}=1. This one should not be too difficult if you use the correct proof technique.
  24a  The empty string (λ) is a palindrome.
  38
 Review Question  1  On page 439 
Homework 17Section  Problem  Notes


1.1  36e  For old time's sake.
 5.1  12  This one involves some tricky algebra.
 5.3  8cd
  24b
 6.1  10
  12
  40  You do not have to write out the equivalent decimal expression for this one (Josh).
 Review Question  6  On page 440 
Homework 18Section  Problem  Notes


1.4  52  Briefly justify/explain your answer for each.
 5.3  18  A^{n} is A multiplied by itself n times. If you need a refresher on how to multiply matrices, ask me or look at section 2.6.
 6.1  32  Do not make these ones harder than they are. Also, do not simplify your answers. For examples, 26^{3} or 26*25*24 are acceptable.
  56  You do not need to simplify your answer.
 8.5  8
  20
 6.2  16  Justify/Explain your answer.
 Review Question  10  On page 440 
Homework 19Section  Problem  Comments


1.3  18  Read the paragraph before this group of problems.
 6.1  14
  60
 6.2  12  x mod 5 is the remainder when x is divided by 5. So, for instance, 13 mod 5 = 8 mod 5.
  26  The easiest way to show this is to give a graph where the vertices are people and edges indicates friendship. Then you need to argue why your example suffices.
  34
 6.3  8
  22 
Homework 20Section  Problem  Comments


1.7  10
 5.3  40  This one can be tricky. Make sure you don't miss any possibilities.
 6.3  24
  30
 6.4  4 
Homework 21Section  Problem  Notes


1.8  14  This one is really easy if you try some examples. You will quickly discover whether or not it is true.
 2.4  16f  Recall that sometimes you are better off not multiplying everything out as you go. Also, this one might be more clear if you work downward.
 6.3  38
 Review Question  2  On page 634 
Homework 22Section  Problem


2.2  14
 6.1  46
 8.5  14
 6.4  8
 9.1  4
  12
  28
  34aceg 
Homework 23Section  Problem


1.8  16
 5.1  56
 6.3  16
 9.3  4c
  8c
  14ab 
Homework 24Section  Problem  Notes


2.2  16c
 6.1  74  Read the problem very carefully. Also, if you are able to write the decimal representation of the answer to d on less than 100 sheets of paper, you don't have the correct answer.
 6.2  36
 9.3  18c
  32
 9.5  12
  36c
 Review Question  1  On page 844 
Homework 25Section  Problem  Notes


2.3  20
 5.3  14
 6.4  6
 9.3  22
 9.5  16  You need to prove that the relation has the three required properties. The complicated thing about this problem is the notationthe relation is ordered pairs of ordered pairs. This might help you think about it correctly: One thing you need to show is that if ((a,b), (c,d)) is in R, then ((c,d), (a,b)) is in R.
  46
 12.1  4a
  6c
  12 
Homework 26Section  Problem  Notes


6.2  40  Don't use induction. There is a much easier way to think about it. (Hint: What section if this in?)
 6.4  28
 9.1  34b
  36b
 9.5  44
 12.1  2
 12.2  2b
  6 
