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) = n² 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 K_4,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 2ⁿ > n.  (HINT: use multiplication in the inductive step.)

Q12. Use Mathematical Induction to prove that 2ⁿ⁺¹ < 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 2²ⁿ - 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 2ⁿ < 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! < nⁿ 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).