CMSC 250 Homework #9 Fall 2005

0201 & 0202

Due Wed Nov 2 at the beginning of your discussion section.

You must write the solutions to the problems single-sided on your own lined paper, with all sheets stapled together, and with all answers written in sequential order or you will lose points.

1. For each of the following statements, either use induction to prove that the statement is true, or give a counterexample with justification to show that it is false.
   1. Suppose that the following recurrence relation holds
      
      $$a_1 = 1, a_2 = 0, \forall i \in Z^{\geq 2}, a_i = 4a_{i-1} - 4a_{i-2}$$
      
      
      Prove that $\forall n \in Z^+, a_n = 2^n(1 - \frac{n}{2})$
      Base Case (n = 1, n = 2)
      n = 1: $a_n = a_1 = 1\hspace{0.6in}2 ^ 1 (1 - \frac{1}{2}) = 2(\frac{1}{2}) = 1$
      n = 2: $a_n = a_2 = 0\hspace{0.6in}2 ^ 2 (1 - \frac{2}{2}) = 2(0) = 0$
      IH $(n = i, \forall i \in Z, 1 \leq i \leq k - 1)$
      $a_i = 2 ^ i (1 - \frac{i}{2})$
      IS$(i = k)$
      show: $a_k = 2 ^ k (1 - \frac{k}{2})$
      proof:
      $a_k = 4a_{k - 1}- 4a_{k - 2}\\ = 4(2^{k - 1}(1 - \frac{k - 1}{2})) - 4(2^{k -... ...\ =4(2^{k - 3}(2 - k))\\ =2^{k - 1}(2 - k)\\ = 2 ^ {k} (1 - \frac{k}{2})$
   2. Suppose that the following recurrence relation holds
      
      $$b_1 = 4, b_2 = 12, \forall i \in Z^{\geq 2}, b_i = b_{i-2} + b_{i-1}$$
      
      
      Prove that $\forall n \in Z^{\geq 1}, 4\vert b_n$ Base Case (n = 1, n = 2)
      $n = 1\hspace{0.6in}b_n = b_1 = 4\hspace{0.6in} 4\vert 4\\ n = 2 \hspace{0.6in}b_n = b_2 = 12\hspace{0.6in} 4\vert 12\\$ IH $(n = m, \forall m \in Z, 1 \leq m < k)\\ 4 \vert b_m$
      IS$(n = k)$
      show: $\hspace{0.1in}4\vert b_k$
      proof:
      $b_k = b_{k - 2} + b_{k - 1}\\ 4\vert b_{k - 2}$ therefore $\exists r \in Z, b_{k - 2} = 4r\\ 4 \vert b_{k - 1}$ therefore $\exists s \in Zm b_(k - 2) = 4s$ by def. of divides
      $b_k = 4r+4s$ by substitution
      $b_k = 4(r+s), r+s \in Z$ by closure of $Z$
      $4\vert b_k$ by def. of divides
      
   3. Suppose that the following recurrence relation holds
      
      $$d_1 = \frac{9}{10}, d_2 = \frac{10}{11}, \forall k \in Z^{\geq 3}, d_k = d_{k-1} \cdot d_{k-2}$$
      
      
      Prove that $\forall n \in Z^{\geq 1}, d_n \leq 1$ Base Case (n = 1, n = 2)
      $n = 1\hspace{0.6in}d_n = d_1 = \frac{9}{10}\hspace{0.6in} 0 < \frac{9}{10} \le ... ...hspace{0.6in}d_n = d_2 = \frac{10}{11}\hspace{0.6in} 0 <\frac{10}{11} \le 1\\$ IH $(n = i, \forall i \in Z, 1 \leq i < k)\\ d_i \le 1$
      IS$(n = k)$
      show: $\hspace{0.6in} d_k \le 1$
      proof:
      $d_k = d_{k - 1}d_{k - 2}\\ \hspace{3in} d_{k - 1} \le 1 / d_{k - 2}$ by IH
      $\hspace{3in} d_{k - 1} \le 1$ from above
      $\hspace{3in} d_{k - 1}d_{k - 2} \le d_{k - 2}$ by multiplying both sides by $d_{k - 2}$
      $\hspace{3in} d_{k - 2} \le 1$ from above
      $\hspace{3in} d_{k - 1}d_{k - 2} \le d_{k - 2} \le 1\\ \hspace{3in} d_{k} \le 1$ by substitution
      
2. Use set notation to answer each of the following questions:
   1. Suppose A and B are sets defined as
      
      $$A = \{x \in Z\vert \forall k \in Z^{\geq 1}, x =4k+1 \}$$
      
      
      
      
      $$B = \{x \in Z\vert \forall k \in Z^{\geq 1}, x = 3k+5\}$$
      
      
      1. List 10 elements of $A \cup B$
      2. List 10 elements of $A \cap B$
      Note:
      A = { 5, 9, 13, 17, 21, 25, 29, 33, 37, 41... }
      B = {8, 11, 14, 17, 20, 23, 26, 29, 32, 35... }
      $A \cap B = \{ x\in Z \vert \forall k \in Z^{\geq 1}, x = 12k + 17\}$
   2. For each of the following expressions, use a Venn diagram representing the universe U and the two subsets of that universe A and B. Shade the part of the diagram that corresponds to the set specified by the expression. Note: $A^c$ means the complement of A.
      1. $A^c$
         
      2. $B^c$
         
      3. $(A \cup B)^c$
         
      4. $A^c \cap B^c$
         
      5. $A^c \cup B^c$
         
      6. $(A \cap B)^c$
         

Web Accessibility