Assignment 3

In addition to correct answers, please do the following:

  • Show how you derived your answer.
  • Proofs, and longer-answer questions, should be beautifully organized and easy to read, including perfect spelling and grammar.

Please see Canvas for instructions on how and when to submit this assignment.

Question 1

Prove that if \(n\) is an integer, then \(n\) and \(n+1\) can’t both be odd. Write this as an English paragraph-style proof.

Question 2

Prove that if \(n\) is an odd integer, then \(n^2 + 3\) is always even. Write this as an English paragraph-style proof.

Question 3

Suppose \(S=\{a, \{ b \}, \{ a \} \}\). For each of the following expressions, state if they are true or false.

  1. \(a \in S\)
  2. \(\{ a \} \in S\)
  3. \(\{ a \} \subseteq S\)
  4. \(\{\{ a \}\} \subseteq S\)
  5. \(b \in S\)
  6. \(\{ b \} \subseteq S\)
  7. \(\{\{ b \}\} \subseteq S\)
  8. \(\{\{ b \}\} \subset S\)

Question 4

For each of the following statements, state if they are true or false.

  1. \(\emptyset \in \emptyset\)
  2. \(\emptyset \subseteq \emptyset\)
  3. \(\emptyset \subset \emptyset\)
  4. \(\emptyset \in \{ \emptyset \}\)
  5. \(\emptyset \subseteq \{ \emptyset \}\)
  6. \(\emptyset \subset \{ \emptyset \}\)

Question 5

Suppose the sets \(A\), \(B\), and \(C\) are in the same universe. If \(A \subseteq B\), and \(B \nsubseteq C\), is \(A \nsubseteq C\) always true? If yes, then provide a proof; if no, then give a counter-example.

Question 6

Suppose \(A\), \(B\), \(C\), \(D\), and \(E\) are are defined as follows:

\[ \begin{align}\begin{aligned}A = \{3n | n \in \mathbb{Z} \}\\B = \{8n | n \in \mathbb{Z} \}\\C = \{2n | n \in \mathbb{Z} \}\\D = \{4n | n \in \mathbb{Z} \}\\E = \{6n | n \in \mathbb{Z} \}\end{aligned}\end{align} \]

Which of the following statements are true, and which are false?

  1. \(C \subseteq D \subseteq B\)
  2. \(E \subseteq C\)
  3. \(B \subseteq D \subseteq C\)
  4. \(A \subseteq E\)
  5. \(E \subseteq A\)
  6. \(\bar{E} \subseteq \bar{C}\)
  7. \(C \cap D \subseteq B\)
  8. \(\bar{C} \cap D \subseteq \bar{B}\)
  9. \(\bar{C} \cap \bar{D} \subseteq \bar{B}\)
  10. \(\bar{A} \cup C \subseteq \bar{E}\)

Question 7

Prove each of the following facts without using Venn diagrams (or membership tables); give a line-by-line proof, and justify each line. Assume all the sets have the same universe \(\mathscr{U}\).

  1. If \(A \subseteq B\) and \(C \subseteq D\), then \(A \cap C \subseteq B \cap D\).
  2. If \(A \subseteq B\) and \(C \subseteq D\), then \(A \cup C \subseteq B \cup D\).
  3. \(A\) is a subset of \(B\) if, and only if, \(\bar{B} \cap A = \emptyset\).
  4. \(\bar{A} \cup B = \mathscr{U}\) if, and only if, \(A\) is a subset of \(B\).

Question 8

Use mathematical induction to prove that this equation is true for all integers \(n > 0\).

\[\sum_{i=1}^{n} 2^{i} = 2^{n+1}-2\]

Question 9

Use mathematical induction to prove that this equation is true for all integers \(n > 0\).

\[\sum_{i=1}^{n} (i+1)\cdot 2^{i} = n \cdot 2^{n+1}\]