CMSC 250 Homework 5 ANSWERS Spring 2006

Due Wed March 1 at the beginning of your discussion section.

For each of the following, state either that the statement is true or that the statement is false. Then give a complete, convincing proof to justify your answer.

1. For all integers $x$, if $x$ is an even integer then $x^2 + x$ is an even integer.

   TRUE.
   This is the same as $\forall x \in Z, x \in Z^{even} \rightarrow x^2 + x \in Z^{even}$.

   Proof.
   

   Let x be arbitrary in the domain of integers.

   $\vert$Assmue $x$ is even.

   $\vert$Then $x = 2y$ for some integer $y$ by the definition of even.

   $\vert$Then $x^2 + x ~=~ (2y)^2 + (2y)$ by substitution.

   $\vert~=~ 4y^2 + 2y$ by multiplication.

   $\vert~=~ 2(2y^2 + y)$ by distribution.

   $\vert$Since $2y^2+y \in Z$ by the closure of the integers in addition and multiplication,

   $\vert$ $2(2y^2+y) \in Z^{even}$ by the definition of even

   $\vert$and $x^2 +x \in Z^{even}$ by substitution of equalities.

   $x \in Z^{even} \rightarrow x^2 + x \in Z^{even}$ by closing the conditional world without a contradiction.

   Since x was arbitrary in the domain of integers, we can use generalizing from the generic particular to get:

   $\forall x \in Z, x \in Z^{even} \rightarrow x^2 + x \in Z^{even}$

   QED

2. The sum of any two rational numbers is rational.

   TRUE.
   This is the same as $\forall x, y \in Q, x+y \in Q$.
   
   Proof.

   Let $x$ and $y$ be arbitrary rational numbers.

   Then $\exists a,b,c,d \in Z$ such that $x = \frac{a}{b}$ and $y = \frac{c}{d}$

   where $b \neq 0$ and $d \neq 0$.

   Then $x + y ~=~ \frac{a}{b} + \frac{c}{d}$ by substitution

   $~=~ \frac{ad}{bd} + \frac{bc}{bd}$ by multiplication of fractions

   $~=~ \frac{ad + bc}{bd}$ by addition of fractions.

   Since the integers are closed under addition and multiplication, $\exists j \in Z, j = ad + bc$.

   Since the integers are closed under multiplication, $\exists k \in Z, k= bd$.

   Since neither $b$ nor $d$ are 0, $bd \neq 0$ by multiplication rules of algebra.

   Since $x + y ~=~ \frac{j}{k}$ where $j$ and $k$ are both integers and $k \neq 0$,

   $x + y \in Q$ by definition of rational.

   Since x and y were both arbitrary in Q, we can generalize to:

   $\forall x, y \in Q, x+y \in Q$.

   QED

3. The product of any two irrational numbers is irrational.

   FALSE.

   Disproof by counter example.
   Select $\sqrt{2}$.
   $\sqrt{2}$ is irrational,
   but $\sqrt{2} * \sqrt{2} = 2$, which is rational.
   

4. $\forall x, y, z \in Z, ((x \vert y ) \wedge (x \vert z)) \rightarrow (x \vert y +z)$

   TRUE.

   Proof.

   Let x, y and z be arbitrary integers.

   $\vert$Assume $x \vert y$ and $x \vert z$

   $\vert \exists a,b \in Z$ such that $ax = y$ and $bx = z$ by definition of divides.

   $\vert y + z ~=~ ax + bx$ by substitution.

   $\vert ~=~ (a + b) x$ by distribution.

   $\vert$ Since $a + b \in Z$ by closure of Z in addition,

   $\vert x \vert y + z$, by definition of divides.

   $(x \vert y \wedge x \vert z) \rightarrow x \vert (y+z)$ by closing the conditional world without a contradiction.

   Since $x$, $y$ and $z$ were arbitrary integers, we can generalize from the generic particular and get:

   $\forall x,y,z \in Z, (x \vert y \wedge x \vert z ) \rightarrow x \vert (y+z)$.

5. The sum of any two consecutive integers is odd.

   TRUE.

   Proof.

   Let $n$ be an arbitrary integer.

   Then its successor is $n+1$.

   The sum of these two consecutive integers is $n + (n+1)$

   This equals $2n + 1$ by algebra.

   Since $n$ was defined above as an integer, $2n+1 \in Z^{odd}$by the definition of odd.

   Since $n$ was arbitrary in the set we can generalize to:

   For all pairs of two consecutive integers, their sum is odd.

6. For all integers $x$ greater than 3, $4 \vert x(6 * 2^x)$

   TRUE.

   Proof.

   Let $x$ be an arbitrary integer greater than 3.

   Then $x = y + 2$ for some integer $y > 1$.

   Therefore $x(6 * 2^x) ~=~ (y + 2)(6 * 2^{y+2})$ by substitution.

   $~=~ (y + 2)(6 * 2^2 * 2^y)$ by algebra.

   $~=~ 2^2 (y + 2)(6 * 2^y)$ by associativity and commutativity.

   $~=~ 4 (y + 2)(6 * 2^y)$ by squaring the 2.

   Since $(y + 2)(6 * 2^y) \in Z$ by closure of Z in addition and multiplication,

   we know that $4 \vert 4(y+2)(6*2^y)$ by definition of divides

   and $4 \vert x(6 * 2^x)$ by substitution.

   QED

7. $\forall n \in Z, n \in Z^{even} \rightarrow n+n^2 + n^3 \in Z^{even}$

   TRUE.

   Proof:

   Let n be arbitrary in Z.

   $\vert$Assume $n \in Z^{even}$. $\vert\exists k \in Z, n = 2k$ by definition of even.

   $\vert n + n^2 + n^3 ~=~ (2k) + (2k)^2 + (2k)^3$ by substitution.

   $\vert ~=~ 2k + 4k^2 + 8k^3$ by algebra

   $\vert ~=~ 2(k+2k^2+4k^3)$ by distribution

   $\vert$ Since $k + 2k^2 + 4k^3 \in Z$ by closure of Z in multiplication and addition,

   $\vert 2(k+2k^2+4k^3) \in Z^{even}$ by the definition of even.

   $\vert$ and $n + n^2 + n^3 \in Z^{even}$ by substitution.

   Therefore $n \in Z^{even} \rightarrow n+n^2+n^3 \in Z^{even}$ by closing the conditional world w/out contradiction.

   Since n was arbitrary in the integers, we can generalize to:

   $\forall n \in Z, n\in Z^{even} \rightarrow n+n^2+n^3 \in Z^even$

   QED

8. $\forall x, y \in Z^{odd}, x-y \in Z^{even}$

   TRUE.

   Proof.

   Assume $x$ and $y$ are arbitrary in $Z^{odd}$.

   Then $x = 2a + 1$, where $a \in Z$ by the definition of odd,

   and $y = 2b + 1$, where $b \in Z$ by the definition of odd.

   Then $x - y ~=~ (2a + 1) - (2b + 1)$ by substitution

   $~=~ 2a - 2b$ by algebra

   $~=~ 2(a-b)$ by distribution.

   Since $a - b \in Z$ by closure of Z in subtraction,

   $2(a-b) \in Z^{even}$ by the definition of even

   and $x-y \in Z^{even}$ by substitution.

   QED

9. $\forall n \in Z, n^2 - n >0 \rightarrow n \neq 1$

   TRUE.

   We construct the contrapositive. We must show that
   

   $$\forall n \in Z, \sim n \neq 1 \rightarrow \sim (n^2 - n >0)$$
   
   
   which is equivlaent to
   
   $$\forall n \in Z, n = 1 \rightarrow n^2 - n \le 0$$
   
   

   Proof.

   Let $n$ be arbitrary in Z.

   $\vert$ Assume $n = 1$. $\vert n^2 - n ~=~ 1^2 - 1 ~=~ 1 - 1 ~=~ 0$ by algebra.

   $\vert \le 0$ by definition of less than or equal to.

   $\vert n^2 - n \le 0$ by substitution.

   $n = 1 \rightarrow n^2 -n \le 0$ by closing the conditional world without contradiction.

   Since n was arbitrary in Z, we can generalize to:

   $\forall n \in Z, n = 1 \rightarrow n^2 -n \le 0$.

   QED

10. If $n$ is the sum of any four consecutive integers, $\exists k \in Z, n = 4k + 2$.

    TRUE.

    Proof.

    Let m be arbitrary in the domain of integers.

    Four consecutive integers can be written as $m$, $m+1$, $m+2$, and $m+3$.

    Then their sum is $m + (m+1) + (m+2) + (m+3)$

    $~=~ 4m + 6 ~=~ 4m + 4 + 2 ~=~ 4(m + 1) + 2$ by algebra.

    Select $k = m+1$. $k \in Z$ by closure of Z in addition.

    $m+(m+1)+(m+2)+(m+3) = 4k+2$ by substitution.

    Since m was arbitrary in Z, this can be generalized to:

    $\forall m \in Z, \exists k \in Z, m+(m+1)+(m+2)+(m+3) = 4k+2$.

    QED

11. For all integers $n$, $n$ is an even number if and only if $5n^2 + 12$ is even.

    TRUE.

    We must show that if $n$ is even then $5n^2 + 12$ is even, and if $5n^2 + 12$ is even then $n$ is even. For the second statement, we construct the contrapositive and show that if $n$ is odd then $5n^2 + 12$ is odd. So we need to prove the following two statements:
    $\forall n \in Z, n \in Z^{even} \rightarrow 5n^2 + 12 \in Z^{even}$
    $\forall n \in Z, n \in Z^{odd} \rightarrow 5n^2 + 12 \in Z^{odd}$
    

    Proof.

    Let $n$ be arbitrary in the domain of integers.

    $\vert$Assume $n$ is even.

    $\vert$Then $n = 2m$ for some integer $m$.

    $\vert$Then $5n^2 + 12 ~=~ 5(2m)^2 + 12$ by substitution

    $\vert~~~=~ 5*2^2m^2 + 12 ~=~ 20m^2 + 12 ~=~ 2(10m^2 + 6)$ by algebra

    $\vert 10m^2 + 6 \in Z$ by the closure of the integers in addition and multiplication.

    So $2(10m^2 + 6) \in Z^{even}$ by the definition of even

    and $5n^2 + 12 \in Z^{even}$ by substitution of equalities.

    $n \in Z^{even} \rightarrow 5n^2 + 12 \in Z^{even}$ by closing the conditional world without a contradiction.

    Since $n$ was arbitrary in the domain of integers, we can use generalizing

    from the generic particular to get:

    $\forall n \in Z, n \in Z^{even} \rightarrow 5n^2 + 12 \in Z^{even}$

    Let $n$ be arbitrary in the domain of integers.

    $\vert$Assume $n$ is odd.

    $\vert$Then $n = 2m+1$ for some integer $m$.

    $\vert$Then $5n^2 + 12 ~=~ 5(2m+1)^2 + 12$ by substitution

    $\vert~~~=~ 5*(4m^2 + 4m + 1) + 12 ~=~ 20m^2 + 20m + 16 + 1 ~=~ 2(10m^2 + 10m + 8) + 1$ by algebra

    $\vert 10m^2 +10m + 8 \in Z$ by the closure of the integers in addition and multiplication.

    So $2(10m^2 + 10m + 8) + 1 \in Z^{odd}$ by the definition of odd

    and $5n^2 + 12 \in Z^{odd}$ by substitution of equalities.

    $n \in Z^{odd} \rightarrow 5n^2 + 12 \in Z^{odd}$ by closing the conditional world without a contradiction.

    Since $n$ was arbitrary in the domain of integers, we can use generalizing

    from the generic particular to get:

    $\forall n \in Z, n \in Z^{odd} \rightarrow 5n^2 + 12 \in Z^{odd}$

    QED

12. $\forall m \in Z, \exists k \in Z, m^2 = 5k \vee m^2 = 5k+1 \vee m^2 = 5k + 4.$

    TRUE.

    Proof.

    Let $m$ be arbitrary in the domain of integers.

    $m = 5a ~\vee ~ m = 5a +1 ~\vee m = 5a+2 ~\vee ~ m = 5a +3 ~\vee ~ m = 5a+4$

    Case $m = 5a$:

    $m^2 ~=~ (5a)^2$ by substitution

    $~~~=~ 25a^2 ~=~ 5(5a^2)$ by algebra

    Let $k = 5a^2$

    $k \in Z$ by the closure of the integers in multiplication.

    $m^2 ~=~ 5k$ by substitution

    $m^2 = 5k \vee m^2 = 5k+1 \vee m^2 = 5k + 4$ by disjunctive addition.

    $\exists k \in Z, m^2 = 5k \vee m^2 = 5k+1 \vee m^2 = 5k + 4$ by existential generalization.

    Case $m = 5a+1$:

    $m^2 ~=~ (5a+1)^2$ by substitution

    $~~~=~ 25a^2 +10a + 1 ~=~ 5(5a^2 + 2a) + 1$ by algebra

    Let $k = 5a^2 + 2a$

    $k \in Z$ by the closure of the integers in addition and multiplication.

    $m^2 ~=~ 5k + 1$ by substitution

    $m^2 = 5k \vee m^2 = 5k+1 \vee m^2 = 5k + 4$ by disjunctive addition.

    $\exists k \in Z, m^2 = 5k \vee m^2 = 5k+1 \vee m^2 = 5k + 4$ by existential generalization.

    Case $m = 5a+2$:

    $m^2 ~=~ (5a+2)^2$ by substitution

    $~~~=~ 25a^2 +20a + 4 ~=~ 5(5a^2 + 4a) + 4$ by algebra

    Let $k = 5a^2 + 4a$

    $k \in Z$ by the closure of the integers in addition and multiplication.

    $m^2 ~=~ 5k + 4$ by substitution

    $m^2 = 5k \vee m^2 = 5k+1 \vee m^2 = 5k + 4$ by disjunctive addition.

    $\exists k \in Z, m^2 = 5k \vee m^2 = 5k+1 \vee m^2 = 5k + 4$ by existential generalization.

    Case $m = 5a+3$:

    $m^2 ~=~ (5a+3)^2$ by substitution

    $~~~=~ 25a^2 +30a + 9 ~=~ 5(5a^2 + 6a + 1) + 4$ by algebra

    Let $k = 5a^2 + 6a + 1$

    $k \in Z$ by the closure of the integers in addition and multiplication.

    $m^2 ~=~ 5k + 1$ by substitution

    $m^2 = 5k \vee m^2 = 5k+1 \vee m^2 = 5k + 4$ by disjunctive addition.

    $\exists k \in Z, m^2 = 5k \vee m^2 = 5k+1 \vee m^2 = 5k + 4$ by existential generalization.

    Case $m = 5a+4$:

    $m^2 ~=~ (5a+4)^2$ by substitution

    $~~~=~ 25a^2 +40a + 16 ~=~ 5(5a^2 + 8a + 3) + 1$ by algebra

    Let $k = 5a^2 + 8a + 3$

    $k \in Z$ by the closure of the integers in addition and multiplication.

    $m^2 ~=~ 5k + 1$ by substitution

    $m^2 = 5k \vee m^2 = 5k+1 \vee m^2 = 5k + 4$ by disjunctive addition.

    $\exists k \in Z, m^2 = 5k \vee m^2 = 5k+1 \vee m^2 = 5k + 4$ by existential generalization.

    Therefore, $\exists k \in Z, m^2 = 5k \vee m^2 = 5k+1 \vee m^2 = 5k + 4$ by proof by divistion into cases.

    Since $m$ was arbitrary in the domain of integers, we can use generalizing from the generic particular to get:

    $\forall m \in Z, \exists k \in Z, m^2 = 5k \vee m^2 = 5k+1 \vee m^2 = 5k + 4.$

    QED

Web Accessibility