# Thread: Couple of Discrete Math problems

1. ## Couple of Discrete Math problems

1. Prove: is a solution to the recurrence relation for when and

2. Show that if A and B are sets then

3. Let be a symetric and transitive relation on a set A. Assume for every there exists a with . Prove that R is an equivalence relation.

4. Let G be a graph with vertices and let be distinct vertices on G. Prove that if there is a walk from to , then it has length less than or equal to

Would really appreciate some help with these. Thanks

2. Originally Posted by DemonEyesBob
1. Prove: is a solution to the recurrence relation for when and

2. Show that if A and B are sets then
show that [/COLOR] $A - B \subseteq A \cap B^c$ and $A \cap B^c \subseteq A - B$ and you will have the desired result

do so by showing that if $x \in (A - B)$, then $x \in (A \cap B^c)$ and if $x \in (A \cap B^c)$, then $x \in (A - B)$

3. Let be a symetric and transitive relation on a set A. Assume for every there exists a with . Prove that R is an equivalence relation.
it remains only to show that R is reflexive.

so let
$a \in A$, then there is $b \in A$ so that $aRb$. but $R$ is symmetric, so that means we have $bRa$, so ...
4. Let G be a graph with vertices and let be distinct vertices on G. Prove that if there is a walk from to , then it has length less than or equal to

3. show that [/color][/color] $A - B \subseteq A \cap B^c$ and $A \cap B^c \subseteq A - B$ and you will have the desired result

do so by showing that if $x \in (A - B)$, then $x \in (A \cap B^c)$ and if $x \in (A \cap B^c)$, then $x \in (A - B)$

Thanks for your help on these two. Still a little confused though.

Where did the 'c' come from in $B^c$?

4. Originally Posted by DemonEyesBob
Thanks for your help on these two. Still a little confused though.

Where did the 'c' come from in $B^c$?
it is just alternate notation for that bar you had. it just means B-compliment

5. Originally Posted by DemonEyesBob
Thanks for your help on these two. Still a little confused though.

Where did the 'c' come from in $B^c$?
The 'c' means its complement. That is, $B^c$ means the complement of B.

6. For your question 2, i suggest drawing venn diagrams.

at least that way you can visually see the relation.

7. Originally Posted by Storm20
For your question 2, i suggest drawing venn diagrams.

at least that way you can visually see the relation.
show that and and you will have the desired result

do so by showing that if , then and if , then

First: just in case I misinterpreted it - I'm using $\ni$ as 'not in'.

I'm actually (lol) having a bit of trouble with this than I expected (big surprise). Even without a venn diagram I can see that they are the same, and if you just look at their definitions they're the same (ie. $A-B =$ { $x | x \in A \wedge x \ni B$}
which is the same as $A\cap B^c$ since $\cap$ is just ANOTHER bleeping way of saying AND). Sorry about the crassness, I've just been staring at these problems for a while now and I've realized that discrete and theory have simply killed my love of math.

OK. Back to the problem. I understood what Jhevon was saying, but I don't know how to 'show' something is a subset of something else. I'm simply stuck (my prof. has not been very helpful). I'm also still stuck on the equivalence relation... I'm just not sure how to 'prove' this.

edit: If anyone has any advice on the other two I'd still like to hear it please!

8. Originally Posted by DemonEyesBob

First: just in case I misinterpreted it - I'm using $\ni$ as 'not in'.

I'm actually (lol) having a bit of trouble with this than I expected (big surprise). Even without a venn diagram I can see that they are the same, and if you just look at their definitions they're the same (ie. $A-B =$ { $x | x \in A \wedge x \ni B$}
which is the same as $A\cap B^c$ since $\cap$ is just ANOTHER bleeping way of saying AND). Sorry about the crassness, I've just been staring at these problems for a while now and I've realized that discrete and theory have simply killed my love of math.

OK. Back to the problem. I understood what Jhevon was saying, but I don't know how to 'show' something is a subset of something else.
i told you how to prove it. and in fact, you were off you a good start by stating the definition of the set difference. just write out what it means and observe that the meaning is the same for the other definition.

I'm simply stuck (my prof. has not been very helpful). I'm also still stuck on the equivalence relation... I'm just not sure how to 'prove' this.
i started you off, using one of the properties given. use the last one to finish it off.

do you know what "reflexive", "symmetric" and "transitive" mean?

9. Originally Posted by Jhevon
i told you how to prove it. and in fact, you were off you a good start by stating the definition of the set difference. just write out what it means and observe that the meaning is the same for the other definition.
Do you think this is a sufficient way of proving it? It was giving me issues because the examples for proving set identities were usually more complicated then $A-B=A \cap B^c$ (such as proving De Morgan's Laws), and all the "by definition of"'s were applying to both A and B in the equation (if that makes sense). I think my teacher wants me to use 'set builder' notation, so that's what I've used here o.o

$A-B=A \cap B^c$
= {x| $x \in A \wedge x \ni B$ } -> by definition of Difference
= {x| $x \in A \wedge x \in B^c$ } -> by definition of Compliment
= {x| $x \in A \cap B^c$ } -> by definition of Intersection
= $A \cap B^c$ -> by meaning of set builder notation

10. edit: sorry for the dp, accident >_>

Think I solved the relation one. Still really need help on recurrence relation please!!!!