1. (5 points) Show that these statements are inconsistent, using logical arguments:

   “If Miranda does not take the 1019 course, then she will not graduate.”

   “If Miranda does not graduate, then she is not qualified for the job.”

   “If Miranda reads the book by Rosen, then she is qualified for the job.”

   “Miranda reads the book by Rosen but she does not take the 1019 course.”

<aside> 💡 $P$: “Miranda take the 1019 course” $Q$: “Miranda graduate” $R$: “Miranda is qualified for the job” $S$: “Miranda reads the book by Rosen”

$$ \begin{cases}\neg P\rarr\neg Q\\ \neg Q\rarr\neg R\end{cases}\rArr\neg P \rarr \neg R\\ S\rarr R\\

$$

Since $\neg R$ and $R$ are inconsistent, $\neg P\wedge S$ is inconsistent .

</aside>

1. (4 points) Assume that $G = (V, E)$ is a directed graph. What does the following statement tell us about $G$?

$$ ∀x ∈ V ∃y ∈ V ∃e ∈ E (e = (x, y)). $$

<aside> 🔖 The statement $∀x ∈ V ∃y ∈ V ∃e ∈ E (e = (x, y))$ means that for every vertex $x$ in the graph, there exists a vertex $y$ and a directed edge e from $x$ to $y$ in the graph. In other words, every vertex in $G$ has at least one outgoing edge and $y=f(x):V\rarr V$ is a surjection.

</aside>

1. (8 points) Assume that $A ⊆ C$ and $B ⊆ D$.

   (a) $[4]$ Prove that their Cartesian products satisfy $A × B ⊆ C × D$.

   (b) $[4]$ Under what conditions is $A × B$ a proper subset of $C × D$? Describe the conditions as completely as possible.

   <aside> 💡 (a) Proof: $\forall a \in A, a\in C$ since $A\sube C$

   $\forall b\in B, b\in D$ since $B\sube D$

   $\therefore \forall \left(a,b\right)\in A\times B\rarr (a,b)\in C\times D$

   i.e $A\times B \sube C\times D\quad \square$

   (b)

   $A × B$ is a proper subset of $C × D$ if and only if there exists an element in $C × D$ that is not in $A × B$. In other words, we need to find an element $(c, d)$ such that either $c ∉ A$ or $d ∉ B$, or both.

   If either $A$ or $B$ is the empty set, then $A × B$ is also the empty set, and therefore is a proper subset of $C × D$ unless $C × D$ is also the empty set.

   If neither $A$ nor $B$ is empty, then $A × B$ can be equal to $C × D$ if and only if $A = C$ and $B = D.$

   In all other cases, $A × B$ is a proper subset of $C × D$.

   </aside>

2. (6 points) Consider the function $f : \Z → \Z$ defined by $f(n) = 2n + 1.$

   (a) $[3]$ Is $f$ one-to-one (that is, an injection)? Explain.

   (b) $[3]$ Is $f$ onto (that is, a surjection)? Explain.

   <aside> 💡 (a) Assume $x$ and $y$ $\in \Z$, $f(x)=f(y)\rArr 2x+1=2y+1\rArr x=y$ Therefore $f$ is an injection.

   (b) $\forall y = f(x)\in Z\rArr \exist x=\frac{y-1}{2}$, however $x\notin \Z$ when $y$ is even. Therefore $f$ is not a surjection.

   </aside>

3. (5 points) Show that the two intervals $(0, 1)$ and $(0, 2)$ have the same cardinality.

<aside> 💡 Proof: First define a $f:(0,1)\rarr(0,2)$ by $f(x)=2x$ Since $f(x_1)=f(x_2)\rArr 2x_1=2x_2\rArr x_1=x_2$ , $f$ is an injection; Since $\forall y\in (0,2)\exist x=\frac{y}{2} \in(0,1), f$ is a surjection. Therefore, $f$ is a bijection from $(0,1)$ to $(0,2$) $\rArr (0,1)$ and $(0,2)$ have the same cardinality. $\square$

</aside>

1. (7 points) Let $f$ and $g$ be functions from $\N$ to $\N$. Assume that $f(n$) is $\mathcal{O}(n^3)$, and that $g(n$) is $\mathcal{O}(f(n))$. Prove that the function $f(n) + g(n)$ is $\mathcal{O}(n^ 3 ).$

<aside> 🔖 Proof: $f(n)$ is $\mathcal{O}(n^3)\rArr\exist C_1>0\exist k_1\forall x(x>k_1\rarr|f(x)|\le C_1|x^3|)$ $g(n)$ is $\mathcal{O}(f(n))\rArr\exist C_2>0\exist k_2\forall y(y>k_2\rarr|g(y)|\le C_2|f(y)|)$ Therefore, $\exist C_3=C_1(1+C_2)>0\exist k_3>max(k_1,k_2)\\ \forall n(n>k_3 \rarr |f(n)+g(n)|\le|f(n)+C_2(f(n))|\\ \le (C_1+C_1C_2)|n^3|) =C_3|n^3|$ i.e $f(n)+g(n)$ is $\mathcal{O}(n^3) \quad \square$

</aside>

1. (6 points) Recall that the Fibonacci numbers $\{ f_ n \}$ are defined by $f_ 0 = 0, f_ 1 = 1,$ and $f _n = f {n−1} + f{n−2}$ for $n ≥ 2$. Prove that

$$ \sum_{i=0}^{n}f_i=f_{n+2}-1\text{ for every nonnegative integer } n $$

<aside> 🔖 Proof: Base case: when $n=0,P(0):\sum_{i=0}^{n}f_i=f_{n+2}-1=f_2-1=0$ is true.

Assume $\forall n\ge 0 P(n):\sum_{i=0}^{n}f_i=f_{n+2}-1$ is also true. Then $P(k+1)$ is also true:

$$ \sum_{i=0}^{k+1}f_i=f_{k+1}+\sum_{i=0}^{k}f_i=f_{k+2}-1+f_{k+1}=f_{k+3}-1 $$

Since $P(0)$is true and $P(n)\rarr P(n+1)$, $P(n): \sum_{i=0}^{n}f_i=f_{n+2}-1\text{ is true for every nonnegative integer } n\quad \square$

</aside>

1. (7 points) Let the sequence $\{ a_n\}$ be defined as follows:

$$ a_1 = 2, a_2 = 9,\text{ and }a_n = \frac{2}{n}a_{n−1} + 3 a_{n−2}\text{ for all }n ≥ 3. $$

Prove that $a_n ≤ 3^n$ for every positive integer $n$.

(Suggestion: You can use strong induction to prove this.)