Book of Proof

Home > Other > Book of Proof > Page 41
Book of Proof Page 41

by Richard Hammack


  i=1

  2i−1 = F2n+1+F2n = F2n+2 = F2(n+1)

  as desired.

  ■

  283

  29.

  ¡n¢

  ¢

  ¢

  ¢

  ¢

  ¢

  Prove that 0 + ¡n−1

  1

  + ¡n−2

  2

  + ¡n−3

  3

  + · · · + ¡ 1

  n

  + ¡0 = F

  −1

  n

  n+1.

  Proof.

  ¡1¢

  ¢

  (Strong Induction) For n = 1 this is 0 + ¡01 = 1 + 0 = 1 = F2 = F1+1. Thus

  the assertion is true when n = 1.

  ¡k¢

  ¢

  ¢

  ¢

  ¢

  ¢

  Now fix n and assume that 0 +¡k−1

  1

  +¡k−2

  2

  +¡k−3

  3

  +· · · + ¡ 1

  k

  +¡0 = F

  −1

  k

  k+1 whenever

  k < n

  ¡n¢

  ¢

  ¢

  . In what follows we use the identity k = ¡n−1

  k

  + ¡n−1

  −1

  k

  . We also often use

  ¡a¢

  b = 0 whenever it is untrue that 0 ≤ b ≤ a.

  Ã

  !

  Ã

  !

  Ã

  !

  Ã

  !

  Ã

  !

  n

  n − 1

  n − 2

  1

  0

  +

  +

  + · · · +

  +

  0

  1

  2

  n − 1

  n

  Ã

  !

  Ã

  !

  Ã

  !

  Ã

  !

  n

  n − 1

  n − 2

  1

  =

  +

  +

  + · · · +

  0

  1

  2

  n − 1

  Ã

  !

  Ã

  !

  Ã

  !

  Ã

  !

  Ã

  !

  Ã

  !

  Ã

  !

  Ã

  !

  n − 1

  n − 1

  n − 2

  n − 2

  n − 3

  n − 3

  0

  0

  =

  +

  +

  +

  +

  +

  + · · · +

  +

  −1

  0

  0

  1

  1

  2

  n − 1

  n

  Ã

  !

  Ã

  !

  Ã

  !

  Ã

  !

  Ã

  !

  Ã

  !

  Ã

  !

  n − 1

  n − 2

  n − 2

  n − 3

  n − 3

  0

  0

  =

  +

  +

  +

  +

  + · · · +

  +

  0

  0

  1

  1

  2

  n − 1

  n

  "Ã

  !

  Ã

  !

  Ã

  !#

  "Ã

  !

  Ã

  !

  Ã

  !#

  n − 1

  n − 2

  0

  n − 2

  n − 3

  0

  =

  +

  + · · · +

  +

  +

  + · · · +

  0

  1

  n − 1

  0

  1

  n − 2

  =

  Fn + Fn−1 = Fn

  This completes the proof.

  ■

  31.

  Pn

  ¡k¢

  ¢

  Prove that

  = ¡n+1 ,

  k=0 r

  r+1

  where r ∈ N.

  Hint: Use induction on the integer n. After doing the basis step, break up the

  ¡k¢

  ¡k¢

  ¢

  ¢

  expression r as r = ¡k−1

  r

  + ¡k−1

  −1

  r

  . Then regroup, use the induction hypothesis,

  and recombine using the above identity.

  33. Suppose that n infinitely long straight lines lie on the plane in such a way that

  no two are parallel, and no three intersect at a single point. Show that this

  n2+n+2

  arrangement divides the plane into

  2

  regions.

  Proof. The proof is by induction. For the basis step, suppose n = 1. Then there

  is one line, and it clearly divides the plane into 2 regions, one on either side of

  the line. As 2 = 12+1+2

  2

  = n2+n+2

  2

  , the formula is correct when n = 1.

  Now suppose there are n + 1 lines on the plane, and that the formula is correct

  for when there are n lines on the plane. Single out one of the n + 1 lines on the

  plane, and call it `. Remove line `, so that there are now n lines on the plane.

  By the induction hypothesis, these n lines

  `

  n2+n+2

  divide the plane into

  5

  2

  regions. Now add

  line ` back. Doing this adds an additional

  4

  n + 1 regions. (The diagram illustrates the

  3

  case where n + 1 = 5. Without `, there are

  2

  n = 4 lines. Adding ` back produces n + 1 = 5

  new regions.)

  1

  284

  Solutions

  Thus, with n + 1 lines there are all together (n + 1) + n2+n+2

  2

  regions. Observe

  n2 + n + 2

  2n + 2 + n2 + n + 2

  (n + 1)2 + (n + 1) + 2

  (n + 1) +

  =

  =

  .

  2

  2

  2

  (n+1)2+(n+1)+2

  Thus, with n + 1 lines, we have

  2

  regions, which means that the

  formula is true for when there are n + 1 lines. We have shown that if the

  formula is true for n lines, it is also true for n + 1 lines. This completes the

  proof by induction.

  ■

  35.

  ¡n¢

  If n, k ∈ N, and n is even and k is odd, then k is even.

  Proof.

  ¡n¢

  Notice that if k is not a value between 0 and n, then k = 0 is even; thus

  from here on we can assume that 0 < k < n. We will use strong induction.

  For the basis case, notice that the assertion is true for the even values n = 2

  ¡2¢

  ¡4¢

  ¡4¢

  and n = 4: 1 = 2; 1 = 4; 3 = 4 (even in each case).

&
nbsp; ¡m¢

  Now fix and even n assume that k is even whenever m is even, k is odd, and

  m < n

  ¡n¢

  ¢

  ¢

  . Using the identity k = ¡n−1

  k

  + ¡n−1

  −1

  k

  three times, we get

  Ã

  !

  Ã

  !

  Ã

  !

  n

  n − 1

  n − 1

  =

  +

  k

  k − 1

  k

  Ã

  !

  Ã

  !

  Ã

  !

  Ã

  !

  n − 2

  n − 2

  n − 2

  n − 2

  =

  +

  +

  +

  k − 2

  k − 1

  k − 1

  k

  Ã

  !

  Ã

  !

  Ã

  !

  n − 2

  n − 2

  n − 2

  =

  + 2

  +

  .

  k − 2

  k − 1

  k

  Now, n − 2 is even, and k and k − 2 are odd. By the inductive hypothesis, the

  outer terms of the above expression are even, and the middle is clearly even;

  ¡n¢

  thus we have expressed k as the sum of three even integers, so it is even.

  ■

  Chapter 11 Exercises

  Section 11.0 Exercises

  1. Let A = {0,1,2,3,4,5}. Write out the relation R that expresses > on A. Then

  illustrate it with a diagram.

  2

  1

  R = ©(5,4),(5,3),(5,3),(5,3),(5,1),(5,0),(4,3),(4,2),(4,1),

  (4, 0), (3, 2), (3, 1), (3, 0), (2, 1), (2, 0), (1, 0)ª

  3

  0

  4

  5

  3. Let A = {0,1,2,3,4,5}. Write out the relation R that expresses ≥ on A. Then

  illustrate it with a diagram.

  285

  2

  1

  R

  =

  ©(5,5),(5,4),(5,3),(5,2),(5,1),(5,0),

  (4, 4), (4, 3), (4, 2), (4, 1), (4, 0),

  3

  0

  (3, 3), (3, 2), (3, 1), (3, 0),

  (2, 2), (2, 1), (2, 0), (1, 1), (1, 0), (0, 0)ª

  4

  5

  5. The following diagram represents a relation R on a set A. Write the sets A

  and R. Answer: A = {0, 1, 2, 3, 4, 5}; R = {(3, 3), (4, 3), (4, 2), (1, 2), (2, 5), (5, 0)}

  7. Write the relation < on the set A = Z as a subset R of Z × Z. This is an infinite

  set, so you will have to use set-builder notation.

  Answer: R = {(x, y) ∈ Z × Z : y − x ∈ N}

  9. How many different relations are there on the set A = ©1,2,3,4,5,6ª?

  Consider forming a relation R ⊆ A × A on A. For each ordered pair (x, y) ∈ A × A,

  we have two choices: we can either include (x, y) in R or not include it. There

  are 6 · 6 = 36 ordered pairs in A × A. By the multiplication principle, there are

  thus 236 different subsets R and hence also this many relations on A.

  11. Answer: 2(|A|2)

  13. Answer: 6=

  15. Answer: ≡ (mod 3)

  Section 11.1 Exercises

  1. Consider the relation R = {(a, a),(b, b),(c, c),(d, d),(a, b),(b, a)} on the set A = {a, b, c, d}.

  Which of the properties reflexive, symmetric and transitive does R possess and

  why? If a property does not hold, say why.

  This is reflexive because (x, x) ∈ R (i.e., xR x )for every x ∈ A.

  It is symmetric because it is impossible to find an (x, y) ∈ R for which ( y, x) ∉ R.

  It is transitive because (xR y ∧ yR z) ⇒ xR z always holds.

  3. Consider the relation R = {(a, b),(a, c),(c, b),(b, c)} on the set A = {a, b, c}. Which

  of the properties reflexive, symmetric and transitive does R possess and why?

  If a property does not hold, say why.

  This is not reflexive because (a, a) ∉ R (for example).

  It is not symmetric because (a, b) ∈ R but (b, a) ∉ R.

  It is not transitive because cRb and bR c are true, but cR c is false.

  p

  p

  p p

  5. Consider the relation R = ©(0,0),( 2,0),(0, 2),( 2, 2)ª on R. Say whether this

  relation is reflexive, symmetric and transitive. If a property does not hold, say

  why.

  This is not reflexive because (1, 1) ∉ R (for example).

  It is symmetric because it is impossible to find an (x, y) ∈ R for which ( y, x) ∉ R.

  It is transitive because (xR y ∧ yR z) ⇒ xR z always holds.

  7. There are 16 possible different relations R on the set A = {a, b}. Describe all of

  them. (A picture for each one will suffice, but don’t forget to label the nodes.)

  Which ones are reflexive? Symmetric? Transitive?

  286

  Solutions

  a

  b

  a

  b

  a

  b

  a

  b

  a

  b

  a

  b

  a

  b

  a

  b

  a

  b

  a

  b

  a

  b

  a

  b

  a

  b

  a

  b

  a

  b

  a

  b

  Only the four in the right column are reflexive. Only the eight in the first and

  fourth rows are symmetric. All of them are transitive except the first three

  on the fourth row.

  9. Define a relation on Z by declaring xR y if and only if x and y have the same

  parity. Say whether this relation is reflexive, symmetric and transitive. If a

  property does not hold, say why. What familiar relation is this?

  This is reflexive because xR x since x always has the same parity as x.

  It is symmetric because if x and y have the same parity, then y and x must

  have the same parity (that is, xR y ⇒ yR x).

  It is transitive because if x and y have the same parity and y and z have the

  same parity, then x and z must have the same parity. (That is (xR y∧ yR z) ⇒ xR z

  always holds.)

  The relation is congruence modulo 2.

  11. Suppose A = {a, b, c, d} and R = {(a, a),(b, b),(c, c),(d, d)}. Say whether this relation

  is reflexive, symmetric and transitive. If a property does not hold, say why.

  This is reflexive because (x, x) ∈ R for every x ∈ A.

  It is symmetric because it is impossible to find an (x, y) ∈ R for which ( y, x) ∉ R.

  It is transitive because (xR y ∧ yR z) ⇒ xR z always holds.

  (For example (aRa ∧ aRa) ⇒ aRa is true, etc.)

  13. Consider the relation R = {(x, y) ∈ R × R : x − y ∈ Z} on R. Prove that this relation

  is reflexive and symmetric, and transitive.

  Proof. In this relation, xR y means x − y ∈ Z.

  To see that R is reflexive, take any x ∈ R and observe that x − x = 0 ∈ Z, so xR x.

  Therefore R is reflexive.

  To see that R is symmetric, we need to prove xR y ⇒ yR x for all x, y ∈ R. We

  use direct proof. Suppose xR y. This means x − y ∈ Z. Then it follows that

  −(x − y) = y − x is also in Z. But y − x ∈ Z means yRx. We’ve
shown xR y implies

  yR x, so R is symmetric.

  To see that R is transitive, we need to prove (xR y ∧ yR z) ⇒ xR z is always

  true. We prove this conditional statement with direct proof. Suppose xR y and

  yR z. Since xR y, we know x − y ∈ Z. Since yRz, we know y − z ∈ Z. Thus x − y

  and y − z are both integers; by adding these integers we get another integer

  (x − y) +(y − z) = x − z. Thus x − z ∈ Z, and this means xRz. We’ve now shown that

  if xR y and yR z, then xR z. Therefore R is transitive.

  ■

  287

  15. Prove or disprove: If a relation is symmetric and transitive, then it is also

  reflexive.

  This is false. For a counterexample, consider the relation R = {(a, a), (a, b), (b, a), (b, b)}

  on the set A = {a, b, c}. This is symmetric and transitive but it is not reflexive.

  17. Define a relation ∼ on Z as x ∼ y if and only if |x − y| ≤ 1. Say whether ∼ is

  reflexive, symmetric and transitive.

  This is reflexive because |x − x| = 0 ≤ 1 for all integers x. It is symmetric because

  x ∼ y if and only if |x− y| ≤ 1, if and only if |y− x| ≤ 1, if and only if y ∼ x. It is not

  transitive because, for example, 0 ∼ 1 and 1 ∼ 2, but is not the case that 0 ∼ 2.

  Section 11.2 Exercises

  1. Let A = {1,2,3,4,5,6}, and consider the following equivalence relation on A: R =

  {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (2, 3), (3, 2), (4, 5), (5, 4), (4, 6), (6, 4), (5, 6), (6, 5)}. List the equivalence classes of R.

  The equivalence classes are: [1] = {1};

  [2] = [3] = {2,3};

  [4] = [5] = [6] = {4,5,6}.

  3. Let A = {a, b, c, d, e}. Suppose R is an equivalence relation on A. Suppose R has

  three equivalence classes. Also aRd and bR c. Write out R as a set.

  Answer: R = {(a, a), (b, b), (c, c), (d, d), (e, e), (a, d), (d, a), (b, c), (c, b)}.

  5. There are two different equivalence relations on the set A = {a, b}. Describe

  them all. Diagrams will suffice.

  Answer: R = {(a, a), (b, b)} and R = {(a, a), (b, b), (a, b), (b, a)}

  7. Define a relation R on Z as xR y if and only if 3x − 5y is even. Prove R is an

  equivalence relation. Describe its equivalence classes.

  To prove that R is an equivalence relation, we must show it’s reflexive, sym-

  metric and transitive.

  The relation R is reflexive for the following reason. If x ∈ Z, then 3x − 5x = −2x

  is even. But then since 3x − 5x is even, we have xR x. Thus R is reflexive.

  To see that R is symmetric, suppose xR y. We must show yR x. Since xR y, we

  know 3x − 5 y is even, so 3x − 5 y = 2a for some integer a. Now reason as follows:

  3x − 5y = 2a

  3x − 5y + 8y − 8x = 2a + 8y − 8x

  3 y − 5x = 2(a + 4y − 4x).

  From this it follows that 3 y − 5x is even, so yR x. We’ve now shown xR y implies

  yR x, so R is symmetric.

  To prove that R is transitive, assume that xR y and yR z. (We will show that this

  implies xR z.) Since xR y and yR z, it follows that 3x−5 y and 3 y−5z are both even,

  so 3x−5 y = 2a and 3 y−5z = 2b for some integers a and b. Adding these equations,

  we get (3x − 5 y) + (3 y − 5z) = 2a + 2b, and this simplifies to 3x − 5z = 2(a + b + y).

  288

  Solutions

  Therefore 3x − 5z is even, so xR z. We’ve now shown that if xR y and yR z, then

 

‹ Prev