MATH 160 Spring 2026
Introduction to Discrete Mathematics		Charles Cusack
Math & Stats
Hope College
Main
Schedule
Grading
Gradebook
Homework
Policies
Advice
College
    Policies
Notes
Programs
Tutorials
Handin
CSCI 235
MATH 160
Others
Admin

All Homework

Homework 1

  1. (8) AIDM Problem 1.8 (page 31)
    Hint: Use a truth table and a few words for one of the proofs. The other proof might start with something like "The proposition is only false when..."
  2. (16) AIDM Problem 1.12 (page 32)
    Hint: Make sure for parts (c) and (d) you only use ↓. You are not allowed to use ¬ (the most common mistake students seem to make). You might want to start by figuring out how to implement ¬ using ↓.

Homework 2

  1. (5) AIDM Problem 1.15e. Show every step!
  2. (5) AIDM Problem 1.16f.
  3. (5) AIDM Problem 1.17e. Justify your answer by making it clear that you understand what it is saying and then why it is true or false.
  4. (5) AIDM Problem 1.18f.

Homework 3

  1. (6) Convert \((p\oplus q)\wedge(q\vee r)\) to disjunctive normal form using procedure 1.93 from the textbook. Make sure you show all of the steps!
  2. (6) Use the definition of odd and even to prove that if \(n\) is odd, then \(n^2+n\) is even.

Homework 4

  1. (6) AIDM Problem 2.4 (page 71). To be clear, you are not being asked to prove anything in this problem. You are asked to rephrase the given statement and justify the rephrasing.
  2. (6) AIDM Problem 2.19 (page 72)

Homework 5

  1. (6) AIDM Problem 2.10 (page 71). Make sure your proof is based on the definition of even.
  2. (4) AIDM Problem 2.22. (Easy! Don't overthink it.)
  3. (6) AIDM Problem 2.23. (Also pretty easy if you realize that \(1=1^2\).)

Homework 6

  1. (4) AIDM Problem 3.1 on page 129.
  2. (8) Let \(U=\{A,B,C,...,Z\}\) (the capital letters of the English alphabet) be the universal set and \(S=\{A, B, C, D\}\).
    1. What is \(|S|\)?
    2. What is \(|P(S)|\)?
    3. How many subsets does \(S\) have?
    4. What is \(|\overline{S}|\)
  3. (2) Is \(\mathbb{Z}^+\cup\mathbb{Z}^-=\mathbb{Z}\)? Clearly explain.
  4. (8) Let \(A=\{2x | x\in\mathbb{Z}\}\) and \(B=\{3x | x\in\mathbb{Z}\}\). Express each of the following using set notation.
    1. \(A\cup B\)
    2. \(A\cap B\)
    3. \(A\setminus B\)
    4. \(A\times B\)

Homework 7

  1. (8) AIDMA Problem 3.3b. (Just part b!)
    Hint: Since you are proving equality, this will involve two proofs—one for set containment in each direction.
  2. (4) AIDM Problem 3.6
  3. (4) AIDM Problem 3.8ef
  4. (4) AIDM Problem 3.9ef
  5. Bonus! (4) AIDM Problem 3.11. (FYI, I am fairly strict on grading bonus problems.)

Homework 8

  1. (6) Let \(f:\mathbb{Z}\rightarrow\mathbb{Z}\) be defined by \(f(x)=x^3-x\). Answer each of the following, with a brief justification.
    1. Is \(f\) one-to-one?
    2. Is \(f\) onto?
    3. Is \(f\) invertible?
  2. (8) Let \(f\) be a function that maps a person on earth to the number of pets that they have owned.
    1. What is the domain of \(f\)?
    2. What is the codomain of \(f\)?
    3. The exact range of \(f\) is difficult to know for sure. But is it the same as the codomain? Explain.
    4. Is the range of \(f\) a subset of the codomain? Explain.
  3. (6) Let \(f(x)=e^x\) and \(g(x)=3x^2-4x+7\)
    1. Compute \((f\circ g)(x)\)
    2. Compute \((g\circ f)(x)\)

Homework 9

  1. (8) Let \(f:\mathbb{R}\rightarrow\mathbb{R}\) be defined by \(f(x)=x^3-1\).
    1. Prove that \(f\) is one-to-one.
    2. Prove that \(f\) is onto.
    3. Prove that \(f\) is invertible.
    4. Find \(f^{-1}(x)\).
  2. (8) AIDM Problem 3.24 (Page 131).
    You have to prove 3 things! One of them is so easy it can seem confusing. The other two are not that difficult. Look at the examples in the book for inspiration.

Homework 10

  1. (4) AIDM Problem 4.2 (page 179)
  2. (6) AIDM Problem 4.5 (page 179).
    Make sure you show the work that helped you figure out the formula!

Homework 11

  1. (5) AIDM Problem 4.25 (Page 181). Make sure you show all of the steps! This problem is pretty straightforward—Just plug \(A\) in and evaluate the lefthand side until it simplifies to \(\textbf{0}_2\).
  2. (5) Let \(M = \begin{bmatrix} 0 & 1 \cr 1 & 1 \cr\end{bmatrix}\). Compute \(M^{12}\). Show all of your work.
    (Hint: If you are clever, you can do this with 4 matrix multiplications instead of 11.)

Homework 12

  1. (10) AIDM Problem 5.10 (Page 262). Make sure to clearly label the appropriate parts of the proof.

Homework 13

  1. (10) AIDM Problem 5.13 (Page 262)
    DeMorgan's Law from page 83 provides the base case. For the inductive case, recall that \(A\cup B\cup C=(A\cup B)\cup C\), and similar for intersections.

Homework 14

  1. (10) Use induction to prove for all \(n\geq 1\), a set of size \(n\) has \(2^n\) subsets.
  2. (10) Prove that if you have coins with values 3 and 5, any amount of change of at least 8 can be made with those coins. That is, prove (using strong induction) that every \(n\geq 8\) can be written as \(n=3a+5b\) for some integers \(a\) and \(b\). Don't forget to word the proof very carefully and prove enough base cases!

Homework 15

  1. Consider the following recursively defined function

    \(\displaystyle T(n) = \begin{cases} 2, & \text{if } n \le 0, \\ T(n-1) + 3, & \text{if } n > 0. \end{cases} \)

    1. (5) Compute \(T(0)\), \(T(1)\), \(T(2)\), \(T(3)\), and \(T(4)\).
    2. (2) What are the base case(s) of the recursion?
    3. (2) What are the inductive/recursive cases?
    4. (3) Explain why the recursion always terminates.
  2. A student is climbing a staircase with \(n\) steps. At each move, the student may climb either \(1\) step or \(2\) steps. Let \(S(n)\) be the number of different ways to climb the staircase.
    1. (3) Explain why \(S(0)=1\) and \(S(1)=1\).
    2. (3) Explain why, for \(n\ge 2\),
      \[ S(n)=S(n-1)+S(n-2). \]
    3. (4) Compute \(S(2)\), \(S(3)\), \(S(4)\), and \(S(5)\).
    4. (6) Prove by induction that the recurrence correctly counts the number of ways to climb the staircase. (Hint: If you did parts (a) and (b) correctly, you have most of the details already.)

Homework 16

  1. (10) Recall that the Fibonacci sequence is given by \(f_0=0\), \(f_1=1\), and for \(n>1\), \(f_n=f_{n-1}+f_{n-2}\). Use substitution (induction) to prove that for all \(n\geq 0\), the closed form is given by \[f_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n - \sqrt{5}\left(\frac{1-\sqrt{5}}{2}\right)^n.\] The following identities will help you in the algebraic steps: \[\left(\frac{1+\sqrt{5}}{2}\right)^2=\left(\frac{1+\sqrt{5}}{2}\right)+1 \mbox{ and } \left(\frac{1-\sqrt{5}}{2}\right)^2=\left(\frac{1-\sqrt{5}}{2}\right)+1 \]
  2. (10) Use iteration to find a closed formula for \(T(n)=T(n-1)+n^2\), \(T(1)=1\). Show all of your work and simplify your answer.

Homework 17

For both of the following, make sure you show all of your work. Do not forget to plug in values to determine the constants!

  1. (6) Solve the following first-order linear recurrence relation using the technique from the book: \(a_n=-2a_{n-1}+3\), \(a_0=0\).
  2. (6) Solve the following second-order homogeneous linear recurrence relation using the technique from the book: \(t_n=3t_{n-1}-2t_{n-2}\), \(t_0=1\), \(t_1=2\).

Homework 18

  1. A department assigns identification codes to students. Each code is created in one of the following ways:
    • Type 1: Three uppercase letters followed by two digits.
    • Type 2: Five digits.

    There are 26 letters, 10 digits, and both letters and digits may be repeated. Briefly justify your answer to each of the following questions.

    1. (3) How many codes of Type 1 are possible?
    2. (3) How many codes of Type 2 are possible?
    3. (3) How many distinct codes are possible in total?
    4. (3) What is the minimum number of students that guarantees that at least two students must receive the same identification code? Prove your answer.

Homework 19

  1. (5) AIDM Problem 6.10 (Page 300)
  2. (5) AIDM Problem 6.13a (Page 300). You will need to do a proof by cases and use the pigeonhole principle.
  3. (5) AIDM Problem 6.19 (Page 301)

Homework 20

  1. (5) AIDM Problem 6.14 (Page 300). The final answer will be very simple!
  2. (5) AIDM Problem 6.22 (Page 301). If you use the proper result from the book, this one is very easy. It does require using a few words, though!
  3. (5) AIDM Problem 6.26(g) (Page 302). This one requires inclusion-exclusion. You do not need to determine the final number—an answer like \(12^5*\binom{12}{5}+ 12*11*10-\binom{7}{5}\) is acceptable (although the real answer is a lot longer than this!). Make sure to explain/show your logic.

Homework 21

  1. (4) AIDM Problem 7.2 (page 351).

  2. (8) Consider the following graph.
    0 1 2 3 4 5
    1. Give the adjacency matrix representation for this graph.
    2. Give the adjacency list representation for this graph.

  3. (4) Give a proof by induction of the Handshake Lemma (Theorem 7.49) on simple graphs (no loops). Use induction on the number of edges.

Homework 22

Consider the following graph

  1. (8) Use Prim's algorithm to find a minimum spanning tree for the graph.
    • Assume the adjacency lists are stored in numerical order and start from vertex 0.
    • Give the value in the priority queue at every step of the algorithm (Look at Example 9.101).
    • Draw the graph and darken the edges of the minimum spanning tree. (you may scan/photocopy that page from the book if you wish).
    • Finally, give the weight of the minimum spanning tree.
  2. (8) Use Kruskal's algorithm to find a minimum spanning tree for the graph.
    • Clearly label the vertices with the order they are visited.
    • Clearly darken the edges of the minimum spanning tree. (you may scan/photocopy that page from the book if you wish).
    • Finally, give the weight of the minimum spanning tree.