Reference no: EM132363853
SGTA Exercises - Sets, cycles in graphs, mathematical induction
Q1. What is the cardinality of each of these sets?
(a) A = ∅
(b) B = {∅}
(c) C = {∅,{∅}}
(d) D = {∅,{∅},{∅,{∅}}}
For which of the above is ∅ an element of the set? For which of the above is {∅} an element of the set?
Q2. Suppose A, B, and C are sets.
What, if anything, can you determine about the set (A - C) ∩ (C -B)?
Q3. For this question, let the universal set U be the set of all books ever published; let M be the set of maths books; let D be the set of all Discrete Maths books, and let W be the set of all books written by women.
Express each of the following as sets:
(a) all maths books written by women;
(b) all maths books written by men;
(c) all maths books not about Discrete Maths;
(d) all Discrete Maths books written by men and non-math books written by women.
Q4. If A = {∗, {a, b}} write down the elements of the power set P (A).
Q5. Use Mathematical Induction to prove that the equation 1+3+5+... +(2n-1) = n2 is true for any positive integer n . (HINT: use addition in the inductive step.)
Q6. Let A = {1, 2, 3, 4} and B = {a, b}. Find A × B and B × A.
Q7. Write A -B in terms of the set operations ∩, ∪ and the complement. A Venn diagram may help.
Q8. Find the simplest expression for the set represented as follows: [A ∩ (B- ∪ (A ∪ (A ∩ B)))] ∩ B.
Q9. What is the length of the longest possible path in the bipartite graph K4,3 without repeating any edge?
How do you know you are correct?
[Hint: If a path doesn't start or end at a vertex, what can you say about the number of edges in the path that have that vertex as one of it's end points?]
Q10. The graph H has 13 vertices and the path a b c d e f g h i j k l m is a Hamiltonian path. Vertex a has degree 6 and is adjacent to vertices b, e, g, h, i, and j, while vertex m has degree 7 and is adjacent to vertices b, c, e, f, j, k and l.
Using the idea behind the proof of Ore's theorem, or otherwise, find a Hamiltonian circuit in H.
Q11. Use Mathematical Induction to prove that for any positive integer n, it is true that 2n > n. (HINT: use multiplication in the inductive step.)
Q12. Use Mathematical Induction to prove that 2n+1 < 3n for all natural numbers n > 1. (HINT: use multiplication in the inductive step.)
Q13. Use Mathematical Induction to prove that for any positive integer n, the number 22n - 1 is divisible by 3. (HINT: use multiplication by a fixed number, and addition in the inductive step.)
Q14. Prove that any amount of postage greater than or equal to 8 cents can be obtained using only 3-cent and 5-cent stamps. (HINT: consider different cases in the inductive step.)
Q15. What more can you say about the sets A and B in each of the following circumstances?
(a) A ∪ B = A
(b) A - B = A
(c) A ∩ B = B ∩ A
(d) A - B = B - A
Q16. Show each of the following to be true,
(a) A - B = A ∩ B
(b) A- (B ∩ C) = (A - B) ∪ (A - C)
(c) (A - B) - C = (A - C) - (B - C)
using one of these methods:
(i) Venn diagrams;
(ii) a subset argument;
(iii) a membership table.
Use a different method for each of the three set equalities.
The factorial function, defined for natural numbers n ∈N, is calculated by a product as follows.
n! = n (n -1) (n -2) . . . 3 × 2 × 1
This function is used in the following Induction exercises.
Q17. Prove that 2n < n! for n ≥ 4, where n! is the product of all the positive integers from1 to n. (HINT: use multiplication in the inductive step.)
Q18. Prove that n! < nn for n ≥ 2. (HINT: use multiplication in the inductive step.)
Q19. Use Mathematical Induction to show that for all natural numbers n the sum of the squares of the natural numbers which are less than n is given by the formula 1/6 n (n -1)(2n -1).