4. Use induction to prove that 1 + 5 + 9 + 13... + 4×n-3 = n×(2×n-1)
      Show all of the steps for an induction proof. Omit nothing. The
algebraic manipulation at the end only counts for part of the points
for this question.






---------------------------------------------------------------------------------------

      Mathala is a small mountain village of 500 people; ages vary
from newborns to people in their 90s. No parents in Mathala have more
than 5 children. Let the set S1 = {villagers of Mathala}
      Let the relation R1 = {(a, b) where a is a direct descendent of b or a=b}
      I.e. (a, b) ? R1 if a is b's child or grandchild or great
grandchild, etc. or if a and b are the same person.

   5. Determine if R1 is a poset. You must prove your answer.







   6. Describe the minimal and maximal elements of S1 using R1.


      Let S2 = {i | i ? Z+}
      Let the relation R2 = {(a, b) where (a, b) ? R2 if a and b have
the same number of prime factors and a, b are positive integers >=2}
      For example (8, 18) ? R2 since 8 = 2×2×2 and 18 = 2×3×3. They
both have 3 prime factors counting duplicates.

   7. A) Prove that R2 is reflexive.




      B) Prove that R2 is symmetric.




   8. Prove that R2 is transitive.




   9. Give the partitions of S2 generated by R2.



  10. Draw the digraph of the subset of S2 that contains the integers
from 2 to 12 using the relation R2.







  11. Let S3 = {x | x ? Z+ and x <= 12}
      Let the relation R2 = {(a, b) where (a, b) ? R3 if b/a is an odd integer}
      A) Prove that S3, R3 is a poset.





      B) Draw the Hasse diagram for S3, R3.