Chapter 2: Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

Question: Consider these functions from the set of students in a discrete mathematics class. Under what conditions is the function one-to-one if it assigns to a student his or her

1. Mobile phone number

2. Student identification number

3. Final grade in the class

4. Home town.

Find the solution to each of these recurrence relations with the given initial conditions. Use an iterative approach such as that used in Example 10.

a)\({{\bf{a}}_{\bf{n}}} = - {{\bf{a}}_{{\bf{n}} - {\bf{1}}}}\),\({{\bf{a}}_{\bf{0}}} = {\bf{5}}\)

b)\({{\bf{a}}_{\bf{n}}} = {{\bf{a}}_{{\bf{n}} - {\bf{1}}}} + {\bf{3}}\),\({{\bf{a}}_{\bf{0}}} = {\bf{1}}\)

c)\({{\bf{a}}_{\bf{n}}} = {{\bf{a}}_{{\bf{n}} - {\bf{1}}}} - {\bf{n}}\),\({{\bf{a}}_{\bf{0}}} = {\bf{4}}\)

d)\({{\bf{a}}_{\bf{n}}} = {\bf{2}}{{\bf{a}}_{{\bf{n}} - {\bf{1}}}} - {\bf{3}}\),\({{\bf{a}}_{\bf{0}}} = - {\bf{1}}\)

e)\({{\bf{a}}_{\bf{n}}} = \left( {{\bf{n}} + {\bf{1}}} \right){{\bf{a}}_{{\bf{n}} - {\bf{1}}}}\),\({{\bf{a}}_{\bf{0}}} = {\bf{2}}\)

f )\({{\bf{a}}_{\bf{n}}} = {\bf{2n}}{{\bf{a}}_{{\bf{n}} - {\bf{1}}}}\),\({{\bf{a}}_{\bf{0}}} = {\bf{3}}\)

g)\({{\bf{a}}_{\bf{n}}} = - {{\bf{a}}_{{\bf{n}} - {\bf{1}}}} + {\bf{n}} - {\bf{1}}\),\({{\bf{a}}_{\bf{0}}} = {\bf{7}}\)

Consider these functions from the set of students in a discrete mathematics class. Under what conditions is the function one-to-one if it assigns to a student his or her

1. Mobile phone number
2. Student identification number
3. Final grade in the class
4. Home town.

Use a venn diagram to illustrate the relationships \(A \subset B\) and \(A \subset C\).

Give an example of an uncountable set.

Describe an algorithm for generating all the permutations of the set of the nsmallest positive integers.

Suppose that f is a function from the set A to the set B. Prove that

a) If f is one-to-one, then$S_f$ is a one-to-one function from$P\left(A\right)$ to $P\left(B\right)$.

b) If f is onto function, then$S_f$ is a onto function from$P\left(A\right)$ to $P\left(B\right)$.

c) If f is onto function, then$S^{f^{-1}}$ is a one-to-one function from$P\left(B\right)$ to $P\left(A\right)$.

d) If f is one-to-one, then$S_{f^{-1}}$ is a onto function from $P\left(B\right)$to $P\left(A\right)$.

e) If f is a one-to-one correspondence, then$S_f$ is a one-to-one correspondence from$P\left(A\right)$ to$P\left(B\right)$ and$S_{f^{-1}}$ is a one-to-one correspondence from$P\left(A\right)$ to

Show that if \(A\), \(B\) and \(C\) are sets, then \(\overline {A \cap B \cap C} = \overline A \cup \overline B \cup \overline C \).

(a) by showing each side is a subset of the other side.

(b) using a membership table.

Find the solution to each of these recurrence relations and initial conditions. Use aniterative approach such as that used in Example 10.

a) \({{\bf{a}}_n} = 3{a_{n - 1}}\),\({{\bf{a}}_0} = 2\)

b) \({{\bf{a}}_n} = {a_{n - 1}} + 2\),\({{\bf{a}}_0} = 3\)

c) \({{\bf{a}}_n} = {a_{n - 1}} + n\),\({{\bf{a}}_0} = 1\)

d) \({{\bf{a}}_n} = {a_{n - 1}} + 2n + 3\),\({{\bf{a}}_0} = 4\)

e) \({{\bf{a}}_n} = 2{a_{n - 1}} - 1\),\({{\bf{a}}_0} = 1\)

f ) \({{\bf{a}}_n} = 3{a_{n - 1}} + 1\),\({{\bf{a}}_0} = 1\)

g) \({{\bf{a}}_n} = n{a_{n - 1}}\),\({{\bf{a}}_0} = 5\)

h) \({{\bf{a}}_n} = 2n{a_{n - 1}}\),\({{\bf{a}}_0} = 1\)

If A is an uncountable set andBis a countable set, must A -B be uncountable?.