handout #25

CSE311—Foundations of Computing I
Key to Sample Final Questions

  1. The table below contains English descriptions in terms of x and y of relations on the set Z+ (x being related to y iff the described condition holds). Fill in the table indicating whether each relation is reflexive, symmetric, antisymmetric or transitive.

    Relation reflexive? symmetric? antisymmetric? transitive?
    x - y = 10 no no yes no
    x - y < 10 yes no no no
    xy = yx yes yes no yes

  2. Consider the relation R on Z+ composed of all ordered pairs (x, y) for which:
    |x - 2| ≤ |y - 2|
    Is R a partial ordering? Why or why not?

    Solution: It is not a partial ordering because the relation contains the pairs (1, 3) and (3, 1), which means that it is not antisymmetric. If the pair (3, 1) is removed, the relation is reflexive, antisymmetric, and transitive, which would make it a partial ordering.

  3. Prove that the difference of the cubes of two integers is always 2 more than a multiple of 6 when the difference of the integers is 2. Be sure to indicate the proof technique you are using to solve this problem.

    Solution: We can prove this directly. Assume that the difference of two integers is 2. Let the two integers be x and x + 2. Then computing the difference of their cubes:

    (x + 2)3 - x3 = x3 + 6x2 + 12x + 8 - x3 = 6x2 + 12x + 8 = 6(x2 + 2x + 1) + 2
    Thus, the difference of the cubes of the integers is 2 more than a multiple of 6. This completes the proof.

  4. Prove or disprove that the product of two consecutive integers is never 4 more than a multiple of 7. Be sure to indicate the proof technique you are using to solve this problem.

    Solution: The proposition is true. Proving that the product is never 4 more than a multiple of 7 reduces to proving that the product is never congruent to 4 in modulo 7. We can prove this by cases. There are 7 cases for consecutive integers in modulo 7:

    0 ⋅ 1 ≡ 0
    1 ⋅ 2 ≡ 2
    2 ⋅ 3 ≡ 6
    3 ⋅ 4 ≡ 5
    4 ⋅ 5 ≡ 6
    5 ⋅ 6 ≡ 2
    6 ⋅ 0 ≡ 0
    In no case do we obtain 4. This completes the proof that the product of two consecutive integers is never 4 more than a multiple of 7.

  5. Prove or disprove that the difference of the squares of two positive integers is prime only if the two integers have a difference of 1 (e.g., 62 - 52 = 11 and 72 - 62 = 13). Be sure to indicate the proof technique you are using to solve this problem

    Solution: The proposition is true and we can prove it directly. Let x and y be two positive integers. Then x2 - y2 = (x - y)(x + y). By the Fundamental Theorem of Arithmetic, this is prime only if (x - y) is 1 or if (x + y) is 1 (otherwise there would be two factors of the number). If x and y are both positive, (x + y) cannot be 1. Therefore, (x - y) must be 1 if (x2 - y2) is prime. This completes the proof.

  6. Prove using induction that in a rooted binary tree of height h, the number of vertices is at most 2h + 1 - 1. Recall that using the definitions of Rosen section 10.1, the height of a rooted binary tree is the length of the longest path from the root to a leaf. As a result, the tree of one vertex has a height of 0. Be sure to indicate what you are doing induction on (edges, vertices, height, etc).

    Solution: We will prove this by strong induction on the height of the tree. For the base case, there is only one tree of height 0 and it is composed of one vertex:

    1 ≤ 2 - 1 ≤ 20 + 1 - 1
    Now assume that the property holds of all binary trees of height 0 through k for some k in N. We show that it holds for all binary trees of height k + 1. Let T be a binary tree of height k + 1 with overall root R. T has more than one vertex, so R must have at least one child. There are two cases to consider.

    Suppose T has one child. In this case the child is a tree with height k. Applying the inductive hypothesis, we know it has at most 2k + 1 - 1 vertices. T has just one other vertex (R), so it has at most 2k + 1 vertices. This is smaller than 2k + 2 - 1, which completes the proof for this case.

    Suppose T has two children T1 and T2. Let h1 and h2 be the heights of T1 and T2 respectively. Then by the inductive hypothesis, we know that T1 has at most 2h1 + 1 - 1 vertices and T2 has at most 2h2 + 1 - 1 vertices. The vertices of T include R and the vertices of T1 and T2. Thus T has at most 2h1 + 1 - 1 + 2h2 + 1 - 1 + 1 vertices. Because T has a height of k + 1, one of h1 and h2 is k. Without loss of generality, assume h1 is k. The value of h2 is less than or equal to k, which means that 2h2 + 1 is less than or equal to 2k + 1. Thus, the number of vertices in T is less than or equal to 2k + 1 - 1 + 2k + 1 - 1 + 1, which equals 2k + 2 - 1. This completes the proof for this case and completes the overall proof that the number of nodes in a rooted binary tree of height h is at most 2h + 1 - 1.

  7. The table below contains English descriptions in terms of x and y of relations on the set Z+ (x being related to y iff the described condition holds). Fill in the table indicating whether each relation is reflexive, symmetric, antisymmetric or transitive.

    Relation reflexive? symmetric? antisymmetric? transitive?
    x + y = 2 no yes yes yes
    (x - 5)2 = (y - 5)2 yes yes no yes
    xy = 9 no yes no no
    2x = 3y no no yes no
    2 | xy no yes no no
    2 | x(y + 1) yes no no yes
    x mod y = 0 yes no yes yes

  8. Prove that there are no three consecutive positive integers such that the cube of the third is the sum of the cubes of the first two. Be sure to indicate the proof technique you are using to solve this problem

    Solution: We prove this by contradiction. Assume that such integers exist. Let the three consecutive integers be x, x + 1 and x + 2. Then we know that:

    (x+2)3 = x3 + (x+1)3
    x3 + 6x2 + 12x + 8 = x3 + x3 + 3x2 + 3x + 1
    x3 + 6x2 + 12x + 8 = 2x3 + 3x2 + 3x + 1
    7 = x3 - 3x2 - 9x
    7 = x(x2 - 3x - 9)
    By the Fundamental Theorem of Arithmetic, x would have to be either 1 or 7. Neither case works (33 ≠ 13 + 23 and 93 ≠ 73 + 83). Therefore there are no three consecutive positive integers for which this is true.

  9. Prove that a number is irrational if its square is irrational. Be sure to indicate the proof technique you are using to solve this problem

    Solution: We can use an indirect proof (proof by contrapositive) by showing that if a number is rational, then its square is rational. Let n be a rational number. Then n can be expressed as a/b where a and b are integers and b ≠ 0, which means n2 is a2/b2. But if a and b are integers then so are a2 and b2 and if b ≠ 0 then b2 ≠ 0. Thus, n2 is also rational, which completes the proof.

  10. Assuming that the sum of two real-valued variables x and y is a constant c:

    x + y = c
    Prove that the product xy is maximal when x = y. You are not allowed to use calculus. Be sure to indicate the proof technique you are using to solve this problem

    Solution: We prove this by contradiction. Suppose that there is a number c such that x + y = c and the product xy is not maximal when x = y. If x and y were equal, they would each be c/2. If that is not maximal, then there is a number delta such that one of x and y is (c/2 + delta) and the other is (c/2 - delta). The product of x and y has to be greater than the product when they are equal, so we have that:

    (c/2 + delta)(c/2 - delta) > (c/2)(c/2)
    c2/4 - delta2 > c2/4
    -delta2 > 0
    delta2 < 0
    There is no number whose square is negative, so this is a contradiction. Therefore, for every number c, if x + y = c then the product xy is maximal when x and y are equal.

  11. The table below contains English descriptions in terms of x and y of relations on the set Z+ (x being related to y iff the described condition holds). Fill in the table indicating whether each relation is reflexive, symmetric, antisymmetric or transitive. For this problem we define a function power2(n) to be the maximum value m in N such that 2m | n (the highest power of 2 that divides n).

    Relation reflexive? symmetric? antisymmetric? transitive?
    power2(x) = power2(y) yes yes no yes
    power2(x) <= power2(y) yes no no yes
    x mod 10 = y mod 10 yes yes no yes
    x ⋅ y = 48 no yes no no
    x ⋅ y = 1 no yes yes yes
    2 | (x - y) yes yes no yes
    xy < 100 no no no no

  12. Show that for an any positive integer n, 4n + 3 and 5n + 4 are relatively prime. (Hint: Use Euclid's algorithm. Do not use induction.)

    Solution: Recall that you can compute the gcd of two integers using Euclid's algorithm:

    5n + 4 = 1 ⋅ (4n + 3) + (n + 1)
    4n + 3 = 3 ⋅ (n + 1) + n
    n + 1 = 1 ⋅ n + 1
    Thus, 1 is the greatest common divisor of 4n + 3 and 5n + 4, which is the definition of relatively prime.

    1. Consider the following relation over the set of sets.

      R = {(A, B) | A ∩ B ≠ ∅}
      Is R an equivalence relation? Why or why not?

      Solution: No. An equivalence relation is reflexive, symmetric, and transitive. Of the three, R is not transitive.

      Let A = {1}, B = {1, 2}, and C = {2}. Note that A is related to B, and B is related to C, but A is not related to C.

    2. If so, let A = {1, 2, 3}. What is another set in the equivalence class of A? If not, leave this space blank.

  14. Prove the statement: "For any integers a, b, and c, if there exists an integer m such that b is not congruent to c in modulo m, then either a ≠ b or a ≠ c." Be sure to indicate the proof technique you are using to solve this problem

    Solution: We can prove this indirectly (proof by contrapositive). Assume that a = b and a = c. Then b = c. Since b = c, there cannot exist any m such that b is not congruent to c in modulo m. Every candidate m will divide b - c, which is 0, because every positive integer divides 0.

  15. Prove using mathematical induction that:
    1/(1 ⋅ 3) + 1/(3 ⋅ 5) + 1/(5 ⋅ 7) + 1/(7 ⋅ 9) + ... + 1/((2n - 1)(2n + 1)) = n/(2n + 1)
    Provide a formal definition for the overall proposition being proved (P(n)) using summation notation and indicate the domain for n. Then provide an inductive proof, clearly indicating where you are applying the inductive hypothesis.
    Let P(n) be the statement that:
    n
    ∑
    i = 1    		 1/((2i - 1)(2i + 1)) = n/(2n + 1)
    for n ∈ Z+.

    We first prove P(1):

    1/(1 ⋅ 3) = 1 / 3 = 1 / (2 + 1) = 1 / (2 ⋅ 1 + 1)
    Then we assume P(k) for some k ∈ Z+:
    k
    ∑
    i = 1    		 1/((2i - 1)(2i + 1)) = k/(2k + 1)
    And we prove P(k + 1):
    k + 1
    ∑
    i = 1    		 1/((2i - 1)(2i + 1)) = (k + 1)/(2(k + 1) + 1) = (k + 1)/(2k +3)
    k + 1
    ∑
    i = 1    		 1/((2i - 1)(2i + 1)) =
    k
    ∑
    i = 1    		 1/((2i - 1)(2i + 1)) + 1/((2k + 1)(2k + 3)) =
    (by inductive hypothesis)
    k/(2k + 1) + 1/((2k + 1)(2k + 3)) =
    k(2k + 3)/((2k + 1)(2k + 3)) + 1/((2k + 1)(2k + 3)) =
    (2k2 + 3k + 1)/((2k + 1)(2k + 3)) =
    (2k + 1)(k + 1)/((2k + 1)(2k + 3)) =
    (k + 1)/(2k + 3)
    Therefore P(n) holds for all n ∈ Z+.

  16. Prove that in a rooted binary tree, the number of leaves is one more than the number of vertices with two children. Recall that using the definitions of section 10.1, trees are not allowed to be empty (they have at least one vertex). Be sure to indicate what you are doing induction on (edges, vertices, height, etc).

    Solution: We prove this by induction on vertices. The simplest binary tree is a single vertex. That vertex is a leaf and it has zero children, so for that tree, the number of leaves (1) is one greater than the number of vertices with two children (0). For the inductive step, suppose that the property holds for all binary trees of k vertices for some k in Z+. We want to show that the property also holds for all binary trees of k + 1 vertices. Let T be a binary tree of k + 1 vertices. It must have a leaf L. Let T' be the tree obtained by removing L from T and the edge that connects it to its parent. T' has k vertices, so by the inductive hypothesis, we know that if it has n vertices with two children, then it has n + 1 leaves. Let P be the parent of L. The vertices of T' other than P all have the same status in both trees. Therefore, each leaf of T' other than P is also a leaf of T and each vertex with 2 children in T' also has two children in T (P has at most one child in T' because one of its children from T has been removed). There are two cases. P might have two children in T, in which case T has n + 1 vertices with 2 children (the vertices of 2 children from T' plus P) and n + 2 leaves (the leaves of T' plus L). Or P might have one child in T, in which case it is a leaf in T'. In that case T also has n vertices with 2 children (the same vertices as in T') and n + 1 leaves (all the leaves of T' other than P plus L). This completes the proof.

Stuart Reges
Last modified: Wed Dec 8 17:39:26 PST 2010