Discrete math

Discrete Math Test #3 Study Guide Name: ___________________

Show all step. Explain your logic. Use the appropriate mathematical language.

1. A sequence is defined recursively as follows:

2 1,14

0

1

t� �

a kaa kk

Use mathematical induction to verify that this sequence satisfies the explicit formula.

0, 3

147 t

�� ns

n

n

2. A sequence .....,, 321 bbb satisfies the recurrence relation 21 82 �� � kkk bbb with initial conditions 0,1 21 bb . Find an explicit formula for the sequence.

3. Let X = {l ∈ Z | l = 5a + 2 for some integer a}, Y = {m ∈ Z | m = 4b + 3 for some integer b}, and Z = {n ∈ Z | n = 4c − 1 for some integer c}. (a) Is X ⊆ Y ?(b) Is Y ⊆ Z?

Justify your answers carefully. (In other words, provide a proof if the statement is true or a disproof if the statement is false.)

4. Use the element method for proving a set equals the empty set to prove that. For all sets A and C, (A − C) ∩ (C − A) = ∅.

5. Disprove the following statement by finding a counterexample. For all sets A, B, and C,

A ∩ (B - C) = (A ∩ B) – (A ∩ C).

6. Derive the following result “algebraically” using the properties listed in Theorem 6.2.2.

Give a reason for every step that exactly justifies what was done in the step.

For all sets B and C, (B − C) − B = ∅.

7. If U = {x, y, z}, what is the power set of U?

8,9. P413 #6., 10. p 414#15.

11. Let S be the set of all even integers, and define a function f: Z → S as follows: f(n) =

2n, for all real numbers n.

(a) Prove that f is one-to-one and onto

(b) Find a formula for the inverse function f 1� .