Name (PRINTED):
Student ID #:
Section # (or TA's:
name and time)

CMSC 250

Exam #2

Friday, Oct. 29, 2004

Write all answers legibly in the space provided. The number of points possible for each question is indicated in square brackets - the total number of points on the exam is 100, and you will have exactly 50 minutes to complete this exam. You may not use calculators, textbooks or any other aids during this exam. If you need more space for any answer, ask for an extra paper - these extra papers must be turned in and you must mark so we can find the answer corresponding to a question. The ``cheatsheet'' (which is the last page of the exam) can be ripped off and used during the exam, and the back of the cheat sheet can be used for scratch paper.

Note: The short answer questions are at the end of the exam so that you have the two facing pages for each of the proof questions. If you need more than those two pages DO NOT continue on the page from another problem, raise you hand and we will bring you additional sheets of paper.

Note: The points for the individual non-short answer questions for this exam are not indicated. This would give too much indication as to which are true and which are false. Statements that are true will receive more points than ones that are false. Proving something true that is false or false that is true will result is a loss of all credit. Induction problems will be worth slightly more that deduction.

Leave the paper closed this side up on your desk until you are told to start.

Make sure you are in your assigned seat with all celphones and pagers turned off. Make sure you have writing instruments and your picture ID out on your desk.

**** This area is for grading purposes (points lost per problem)- Do not write below this line ****

1. [25 pnts] If you believe the following statement is True, you must use INDUCTION to prove that it is indeed true. If you believe the following statement is False, you must give and justify a specific counter example.:
   

   $\forall n \in Z^{\geq 0}, \,\,\,\, 9 \vert (12^n-3^n)$	This is:
   	TRUE X
   Hints - if you are using a formal proof	FALSE
   for this you may want to consider:
   definition of division and quotient remainder theorem

   Base Case: (n=0)
   $12^n-3^n = 12^0-3^0 = 1-1 = 0$ by substitution and algebra
   $9\vert$ by the definition of divides
   
   
   
   

   Inductive Hypothesis:(n=k)
   $9\vert (12^k - 3^k)$
   
   
   
   

   Inductive Step:(n=k+1)
   show: $9 \vert (12^{k+1}-3^{k+1})$
   
   
   
   

   proof:
   $12^{k+1} - 3^{k+1}$
   $= 12(12^k) - 3(3^k)$
   $= (9+3)(12^k) - 3(3^k)$
   $= 9(12^k) + 3(12^k) - 3(3^k)$
   $= 9(12^k) + 3(12^k-3^k)$
   
   Since by the IH we know that $9\vert (12^k - 3^k)$,
   by the definition of divides we get $\exists m \in Z, 12^k-3^k = 9m$
   
   $12^{k+1} -3^{k+1} = 9(12^k) + 3(9m)$ by substitution
   $= 9(12^k + 3m)$ by algebra
   
   Since $12^k + 3m \in Z$ when $k \geq 0$ by closure of Z in mult and add,
   we know that $9 \vert 9(12^k -3m)$ by the definition of divides.
   
   Therefore, $9 \vert 12^{k+1} -3^{k+1}$ by substitution.
   QED
   

2. [20 pnts] Prove True or False:
   

   $\exists n \in Z, n^2 \equiv_3 2$	This is:
   	TRUE
   Hints - if you are using a formal proof	FALSE X
   for this you may want to consider: definition of equivalence in a mod
   and definition of divides and division into cases
   and quotient remainder theorem
   the fact that something can only be equivalent to one value r where $0 \leq r < d$

   Since it is false, we will prove the negation of it is true.
   The negation of the original statement is:
   $\forall n \in Z, n^2 \not\equiv_3 2$
   
   Proof: Let n be arbitrary in Z.
   by the Quotient Remainder Theorem, we know that
   $\exists q \in Z, n = 3q + 0 \vee n = 3q+1 \vee n = 3q+2$
   We prove the statement by proving that it is true for each of these three individual cases for the value of n.
   
   Case 1 (n = 3q+0):
   Since $n = 3q + 0$,$n = 3q$ because 0 is the additive identity.
   $n^2 = 9q^2$ by squaring both sides.
   $n^2 = 3(3q^2)$ by factoring.
   $n^2-0 = 3(3q^2)$ because 0 is the additive identity.
   Since $3q^2 \in Z$ by closure of Z in multiplication,
   We know that $3\vert n^2-0$ by definition of divides.
   And $n^2 \equiv_3 0$ by definition of equivalence in a mod.
   Since $n^2 \equiv_3 0$, it is not equivalent to 2
   
   Case 2 (n = 3q+1):
   $n^2 = 9q^2+6q+1$ by sqaring both sides
   $n^2 - 1 = 9q^2 + 6q$ by subtracting one from both sides
   $n^2 -1 = 3(3q^2+2q)$ by factorring out the 3
   Since $3q^2+2q \in Z$ by closure of Z in addition and multiplication,
   we know that $3\vert n^2-1$ by the definition of divides.
   This means that $n^2 \equiv_3 1$ by defintion of equiv in a mod
   Since $n^2 \equiv_3 1$, it is not equivalent to 2
   
   Case 3 (n = 3q+2):
   $n^2 = 9q^2+12q+4$ by squaring both sides
   $n^2 - 1 = 9q^2+12q+3$ by subtracting one from both sides
   $n^2 -1 = 3(3q^2+4q+1)$ by factorring out the 3
   Since $3q^2+4q+1 \in Z$ by closure of Z in addition and multiplication,
   we know that $3\vert n^2-1$ by definition of divides
   This means that $n^2 \equiv_3 1$ by defintion of equivalence in a mod
   Since $n^2 \equiv_3 1$, it is not equivalent to 2
   
   Since by in all three cases it is true that $n^2 \not\equiv_3 2$, it is true by delemma and generalizing from the generic particular,
   that $\forall n \in Z, n^2 \not\equiv_3 2$.
   
   This means that $\sim \exists n \in Z, n^2 \equiv_3 2$ by negating the quantifier.
   Therefore the original statement given is false.

3. [10 pnts] Prove true or false:

   $\forall n,p,r \in Z, \,\,\, n \vert pr \rightarrow n\vert p \vee n\vert r$	This is:
   	TRUE
   Hints - if you are using a formal proof	FALSE X
   for this you may want to consider:
   conditional worlds
   and definition of divides
   and prime factorization

   Since this is a universal statement which is false,
   We give a counter-example and then justify that counter-example.
   
   Let $n = 4, p = 2$ and $r = 2$
   
   It is true that $n \vert pr$ since $4 \vert 2 \cdot 2$ because $4 \vert 4$ by the definition of divides.
   This means that the antecedent is true
   
   The statement $n \vert p$ is false since $4 \not\vert 2$
   The statement $n \vert r$ is false since $4 \not\vert 2$
   Therefore the disjunction $n \vert p \vee n\vert r$ is false
   This means that the consequent is false
   
   Since the antecedent is true and the consequent false with these values,
   This is a valid counter-example to the universal statement.
   

4. [25 pnts] Assuming you have the recurrence relation defined as
   
   $$a_0 = 1 \,\,\, a_1 = 2 \,\,\, \mbox{and} \,\, \forall n \in Z^{\geq 2}, a_n = a_{n-2} + 4$$
   
   

   Use Induction to prove the following fact about the elements of that series:
   

   $$\forall k \in Z^{\geq 0}, a_k \equiv_2 (k+1)$$
   
   

   Base Case: (k=0, k=1)
   k=0: $a_k = a_0 = 1$ and $k+1= 0+1 = 1$ Since $1 \equiv_2 1$, it is true when n=0
   k=1: $a_k = a_1 = 2$ and $k+1= 1+1 = 2$ Since $2 \equiv_2 2$, it is true when n=1
   
   
   
   

   Inductive Hypothesis:(k=i $\forall i \in Z, 0 \leq i < p$)
   $a_i \equiv_2 (i+1)$
   
   
   
   

   Inductive Step:(k=p)
   show: $a_p \equiv_2 p$
   
   
   
   

   proof:
   $a_p = a_{p-2} +4$ from the definition of the recurence relation
   
   $p-2 < p$ since we are subtracting a positive integer on the smaller side
   $0 \leq p-2$ whenever $p \geq 2$ which is the only values we are inducting for
   Therefore we know we can apply the IH.
   
   $a_{p-2} \equiv_2 (p-2)$ by the IH
   $2 \vert a_{p-2} - ((p-2)+1)$ by the definition of equivalence in a mod
   $\exists m \in Z, a_{p-2} - ((p-2)+1) = 2m$ by definition of divides
   $a_{p-2} = 2m + ((p-2)+1)$ by adding the same quantity to both sides
   
   $a_p = (2m+((p-2)+1)) +4$ by substitution
   $= (p +1) +(2m -2 + 4)$ by associativity and commutativity
   $a_p - (p+1) = 2m-2+4$ by subtracting the same quantity from both sides
   $a_p - (p+1) = 2(m+1)$ by algebra
   
   Since $m+1 \in Z$ by closure of Z in addition,
   $2 \vert 2(m+1)$ by definition of divides
   $2 \vert (a_p - (p+1))$ by substitution
   
   Therefore $a_p \equiv_2 (p+1)$ by definiiton of equiv in a mod
   QED
   

5. [20 pnts] Short Answer Questions:
   1. Based on the Unique Prime Factorization theorem circle the most appropriate answer based on the statement that $2\cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot m = 7 \cdot 8 \cdot 9 \cdot 10$

      $2 \vert m$		Definately
      		FALSE
      $7\vert m$	Definately
      	TRUE
      $21 \vert m$		Definately
      		FALSE
      $5 \vert m$		Definately
      		FALSE

   2. For each of the following fill in the limits on the $\sum$ or $\prod$ as requested to cover as many terms as possible. For any additional terms, not covered by the summation or product, give the value of X required by that one problem to maintain the equality - do not use any summation or product notation when giving the value of X, only individual operands.
      1. 
         
         $$\sum_{i=k}^n a_i + \sum_{i = k+2}^{n+3} b_i = \left ( \sum (a_i + b_i)\right) + X$$
         
         
         
         Lower Limit = k+2 Upper Limit = n
         
         X = $a_{k}+a_{k+1}+b_{n+1}+b_{n+2}+b_{n+3}$
      2. 
         
         $$\sum_{i=k-1}^{n+2} a_i= \left ( \sum_{i=k+1}^{n} a_i \right )+ X$$
         
         
         
         X = $a_{k-1}+a_k+a_{n+1}+a_{n+2}$

      3. 
         
         $$\prod_{i=k-1}^{n}a_i \cdot \prod_{i=k+2}^{n-1} b_i= \left ( \prod a_ib_i \right ) \cdot X$$
         
         
         
         Lower Limit = k+2 Upper Limit = n-1
         
         X = $a_{k-1} \cdot a_{k} \cdot a_{k+1} \cdot a_n$

      4. 
         
         $$\prod_{i=k}^n a_ib_i = \left (\prod_{i=k+2}^{n-1} a_i \cdot \prod_{j=k}^{n-2} b_j \right) \cdot X$$
         
         
         
         X = $a_{k} \cdot a_{k+1} \cdot a_n \cdot b_{n-1} \cdot b{n}$

   3. Answer TRUE or FALSE (complete word) for each of the following. (No justification is needed - just the correct whole word answer.):
      1. FALSE $\forall n \in Z, \exists q \in Q, \exists m \in Z, q = \frac{m}{n}$

      2. FALSE $\forall n, m \in Z, n < m \rightarrow \exists k \in Z, n < k< m$

      3. TRUE $\forall n, m \in Q, n < m \rightarrow \exists k \in Q, n < k< m$

Theorem 1.1.1 - Epp Textbook p. 14

Given any statement variables $p$, $q$, and $r$, a tautology $t$ and a contradiction $c$,
the following logical equivalences hold:
1. Commutative laws:	$p \wedge q \equiv q \wedge p$	$p \vee q \equiv q \vee p$
2. Associative laws:	$(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$	$(p \vee q) \vee r \equiv p \vee (q \vee r)$
3. Distributive laws:	$p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$	$p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$
4. Identity laws:	$p \wedge t \equiv p$	$p \vee c \equiv p$
5. Negation laws:	$p \vee \sim p \equiv t$	$p \wedge \sim p \equiv c$
6. Double Negative law:	$\sim (\sim p) \equiv p$
7. Idempotent laws:	$p \wedge p \equiv p$	$p \vee p \equiv p$
8. DeMorgan's laws:	$\sim (p \wedge q) \equiv \sim p \vee \sim q$	$\sim (p \vee q) \equiv \sim p \wedge \sim q$
9. Universal bounds laws:	$p \vee t \equiv t$	$p \wedge c \equiv c$
10. Absorption laws:	$p \vee (p \wedge q) \equiv p$	$p \wedge (p \vee q) \equiv p$
11. Negations of t and c:	$\sim t \equiv c$	$\sim c \equiv t$

Table 1.3.1 - Epp Textbook p. 40

Modus Ponens	Modus Tollens		Disjunctive	$p \vee q$	$p \vee q$
$p \rightarrow q$	$p \rightarrow q$		Syllogism	$\sim q$	$\sim p$
$p$	$\sim q$			Therefore $p$	Therefore $q$
Therefore $q$	Therefore $\sim p$
Conjunctive	$p$		Hypothetical	$p \rightarrow q$
Addition	$q$		Syllogism	$q \rightarrow r$
	Therefore $p \wedge q$			Therefore $p \rightarrow r$
Disjunctive	$p$	$q$	Dilemma:	$p \vee q$
Addition	Therefore $p \vee q$	Therefore $p \vee q$	Poof by	$p \rightarrow r$
			Division	$q \rightarrow r$
			into Cases	Therefore $r$
Conjunctive	$p \wedge q$	$p \wedge q$	Rule of	$\sim p \rightarrow c$
Simplification	Therefore $p$	Therefore $q$	Contradiction	Therefore $p$
Closing C.W.	$\vert p$ Assumed		Closing C.W.	$\vert p$ Assumed
without	$\vert q$ derived		with	$\vert x \wedge \sim x$ derived
contradiction	Therefore $p \rightarrow q$		contradiction	Therefore $\sim p$

Other Equivalences and Other Rules of Inference

Definition	$p \rightarrow q$	$\equiv$	$\sim p \vee q$
of Implication	$\sim (p \rightarrow q)$	$\equiv$	$p \wedge \sim q$
Definition of	$A \leftrightarrow B$	$\equiv$	$(A \rightarrow B) \wedge (B \rightarrow A)$
Biconditional	$\sim (A \leftrightarrow B)$	$\equiv$	$(A \wedge \sim B) \vee (B \wedge \sim A)$
Negation of	$\sim \forall x\,\, P(x)$	$\equiv$	$\exists x \,\, \sim P(x)$
Quantifiers	$\sim \exists x\,\, P(x)$	$\equiv$	$\forall x \,\, \sim P(x)$
Universal	$\forall x \in D, P(x) \rightarrow Q(x)$
Modus Ponens	$P(a)$	$\rightarrow$	$Q(a)$
Universal	$\forall x \in D, P(x) \rightarrow Q(x)$
Modus Tollens	$\sim Q(a)$	$\rightarrow$	$\sim P(a)$
Universal Instantiation	$\forall x \in D, P(x)$	$\rightarrow$	$P(a)$
Existential Generalization	$P(a)$ where $a \in D$	$\rightarrow$	$\exists x \in D, P(x)$
Universal Generalization**	$P(a)$ where $a \in D$	$\rightarrow$	$\forall x \in D, P(x)$
Existential Instantiation **	$\exists x \in D, P(x)$	$\rightarrow$	$P(a)$ where $a \in D$

** NOTE: Remember the special circumstances required for the rules marked by the stars.

Web Accessibility