Author |
Topic: Discrete Math Help (Read 13382 times) |
|
Wardub
Junior Member
Gender: 
Posts: 130
|
 |
Re: Discrete Math Help
« Reply #25 on: Sep 22nd, 2007, 7:57pm » |
 Quote  Modify
|
In your example i understand why the answer is p or q
because p and not p cannot both be true at the same time. which means if both hypothesis are correct. and for example we say p is true then we know r is true. and if p is false we know that q is true. since we don't know p's truth value it is q or r but i have no idea how to go about proving it with steps and rules of inference and junk.
Bah i can do it in my mind, but i can't do it on paper because its more like a branch. If there was a Hypothesis "p" i could do it in a second. I think i have to do something with p p'
wait im coming to a conclusion how about
1. p r Hypothesis
2. p r
3.pq Hypothesis
4.rq if p then r, so can you substitute the p for an r?
5.qr
Chpt 7 questions:
Prove by contradiction that if 5n-1 is odd then n is even. Do i make it if 5n-1 is even then n is odd? and then solve?
how do i go about proving this without just saying it must be an odd number
if 5n-1 is even then n = 2k+1, = 10k -4 = even
2k +1 is odd. so is this enough?
Chapter 8 is making sense i did it on paper because it needed graphs. I have no questions thanks to Towr for explain Boolean Product i finally understand composition S o R i just need to make sure i get the order correct.
|
| « Last Edit: Sep 22nd, 2007, 10:50pm by Wardub » |
 IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Discrete Math Help
« Reply #26 on: Sep 22nd, 2007, 11:05pm » |
Quote Modify
|
I think you need to get help from a tutor. It is hard helping over a forum!!
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Discrete Math Help
« Reply #27 on: Sep 23rd, 2007, 7:16am » |
Quote Modify
|
on Sep 22nd, 2007, 6:27pm, Wardub wrote:| As far as chapter 5 is concerned i get it all except some properties of the empty set. why is the empty set a subset of every set? |
|
Because there are no elements in the empty set that aren't in the (super)set.
For any two sets, A is a subset of B, if and only if every element in A is also an element of B. When there are no elements in A, this is trivially true (Because "for-all .." claims over an empty domain are always true. This is related to everything being derivable from absurdity. Because there are no elements there are no elements for which it isn't true, hence it's true for all.)
Quote:What does { , { }} mean? |
|
That you have a set that contain and and it contains a set containing .
Look at each set as a box: you have one large box, containing two smaller boxes. One of these is empty, and the other contains a fourth, smaller, box which is empty.
Visualization and analogies can help a lot (although you should never mistake them for being real; intuition can in some cases lead you astray. But for the moment this works).
Quote:| one problem i don't get is, Determine the power set of {1, , {1}} but how can this have 1 and the empty set and what does {1} mean? |
|
{1} is a set containing the element 1. (Look at it as boxes again: you have a large box, with inside it a '1', an empty box, and a box with a '1')
To find the powerset you don't have to consider what the elements are (it doesn't matter that some of them are sets). Just treat every element as a single object.
There are three distinct elements in our set (1 and and {1}); so the powerset must consist of 23 subsets.
To avoid confusion, let's take a=1, b=, c={1}. So then our set is {a,b,c}
This looks easier, but is exactly the same problem; the powerset is (spread over several lines so you can clearly see the eight subsets of {a,b,c} which together form the powerset):
{
{},
{a},
{b},
{c},
{a,b},
{a,c},
{b,c},
{a,b,c}
}
Now we can replace the placeholders a,b,c with the originals again and get
{
{},
{1}},
{},
{{1}},
{1, },
{1, {1}},
{ , {1}},
{1, , {1}}
}
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Discrete Math Help
« Reply #28 on: Sep 23rd, 2007, 7:37am » |
Quote Modify
|
on Sep 22nd, 2007, 7:57pm, Wardub wrote:Chpt 7 questions:
Prove by contradiction that if 5n-1 is odd then n is even. Do i make it if 5n-1 is even then n is odd? and then solve?
how do i go about proving this without just saying it must be an odd number
if 5n-1 is even then n = 2k+1, = 10k -4 = even
2k +1 is odd. so is this enough? |
|
You have the claim: Odd(5n+1) Even(n)
To prove by contradiction, means that we assume this claim is false, and then show that this leads to an absurd conclusion. So what is the negation of Odd(5n+1) Even(n)?
It will be Odd(5n+1)  Even(n), that n is (or can be) not-even despite 5n+1 being odd.
If n is not even, then it is odd*); so we have an odd n. 5 is also an odd number, and an odd number times an odd number is odd *); so 5n is odd. 1 is an odd number as well, and adding two odd numbers gives an even number *), therefore 5n+1 is even.
But we started by assuming both that n was odd, and that 5n+1 was odd, clearly 5n+1 can't be both even and odd *). And so here we reach a contradiction: it cannot be true that 5n+1 and n are both odd, so if 5n+1 is odd, n must be even.
*) here I'm taking these claims for granted, but of course in some way they have to follow from the axioms of arithmetic and the definition of "odd" and "even" (if odd numbers are defined as those that are not even, then it follows immediately that a number can't be both; the other two claims follow from modular arithmetic)
|
| « Last Edit: Sep 23rd, 2007, 7:40am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: Discrete Math Help
« Reply #29 on: Sep 23rd, 2007, 2:35pm » |
Quote Modify
|
Thanks a lot guys, this is making sense now, I think my main problem is seeing the proofs but i assume that will come. And Sameer, i tried to get a tutor but they didn't have any for this class and it has no TA's im going to ask him after the test if there is anyone he knows that will help me. O and towr that box example really helped me thanks.
im doing the rest of my notes by hand, its easier to do matrices. Im having trouble with what a transitive Matrix would look like, could anyone help. It says a matrix M is transitive if M  M  M. Does that M M mean take the boolean product?
|
| « Last Edit: Sep 23rd, 2007, 2:54pm by Wardub » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Discrete Math Help
« Reply #30 on: Sep 23rd, 2007, 3:23pm » |
Quote Modify
|
on Sep 23rd, 2007, 2:35pm, Wardub wrote:| im doing the rest of my notes by hand, its easier to do matrices. Im having trouble with what a transitive Matrix would look like, could anyone help. It says a matrix M is transitive if M M M. Does that M M mean take the boolean product? |
|
I'm fairly sure it does.
Transitivity means that if aRb and bRc then aRc: so you can already get to c from a in one step (i.e. it's in the original matrix)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: Discrete Math Help
« Reply #31 on: Sep 30th, 2007, 9:57pm » |
Quote Modify
|
Hey guys im back again, this time we are proving by induction, and i understand how to prove a sequence is equal to a certain equation. But i had to miss last class and i don't understand how to solve by induction if the thing im solving is not suppose to be equal. Im not sure im making sense right now in writting let me know if you need clarifacation.
1. prove for every int N > 4 that 2^N > N^2
2. prove for every int n > 0 the number n^5-n is a multiple of 5.
I know i need to prove the first the first term is true, then i need to substitute (n+1) for n correct? but in these examples i don't know where i am suppose to go. like if i was proving something was equal, i could make the left side look like the right, but i don't know how i would go about proving something is greater, or a multiple of 5, im really stumped.
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Discrete Math Help
« Reply #32 on: Sep 30th, 2007, 10:11pm » |
Quote Modify
|
For induction three steps
1) Prove for smallest integer n
2) Assume it is true for some integer n = k
3) Prove that using assumption in 2) the equation is true for n = k + 1
Let' take for e.g. your first problem 2n > n2
Step 1:
For n = 5
25 = 32
52 = 25
So 32 > 25
Step 2:
Assume it is true for some n = k
then 2k > k2
Step 3:
L.H.S = 2k+1
= 2k . 2
> k2 . 2
= k2 + k2
> k2 + 2k + 1 (because k2 > 2k + 1 (why? - you should probably try to prove this)
= (k+1)2
Thus by induction ... 2n > n2 for n > 5
see how in step 3. how I need to prove 2k+1 > (k+1)2 so I adjusted terms to get the RHS... hope this helps.
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: Discrete Math Help
« Reply #33 on: Sep 30th, 2007, 10:29pm » |
Quote Modify
|
yes that helps quite a bit, one quick question so in step 3, to prove that k^2 > 2k+1 do i prove this inductivly also?
so
im skipping the first step cuz i no i can do that
L.H.S
(K+1)(K+1)
R.H.S
2(K+1)+1
(K+1) (2 + 1/(K+1))
hmm i dont think thats right and im really tired ill pick up on this in the morning.
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Discrete Math Help
« Reply #34 on: Sep 30th, 2007, 10:37pm » |
Quote Modify
|
You can prove without induction.. you can start this (k-1)2 - 2 > 0 for k > 5
giving k2 > 2k + 1
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: Discrete Math Help
« Reply #35 on: Oct 1st, 2007, 10:34am » |
Quote Modify
|
Hmm im so confused. after 2^k * 2 why do you have > k^2*2, and then K^2 + k^2, because 2^(k+1) != k^2 + k^2
That made no sense, anyway im getting closer
ok so we multiple both sides by 2 right
so we have 2^(k+1) > 2K^2 = k^2 + k^2
then where do i go from here? im not following your steps
|
| « Last Edit: Oct 1st, 2007, 10:42am by Wardub » |
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Discrete Math Help
« Reply #36 on: Oct 1st, 2007, 10:54am » |
Quote Modify
|
on Oct 1st, 2007, 10:34am, Wardub wrote:| Hmm im so confused. after 2^k * 2 why do you have > k^2*2, |
|
Because from step 2., we have 2k > k2 so 2k . 2 > k2 . 2
Quote:
and then K^2 + k^2, because 2^(k+1) != k^2 + k^2
That made no sense, anyway im getting closer
|
|
2k2 = k2 + k2
Mind you we haven't yet reached k+1 part yet.
Quote:
ok so we multiple both sides by 2 right
so we have 2^(k+1) > 2K^2 = k^2 + k^2
then where do i go from here? im not following your steps |
|
Maybe use my steps as a guide and try to do it yourself and see if you can relate!!
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Discrete Math Help
« Reply #37 on: Oct 1st, 2007, 10:56am » |
Quote Modify
|
on Oct 1st, 2007, 10:34am, Wardub wrote:Hmm im so confused. after 2^k * 2 why do you have > k^2*2, and then K^2 + k^2, because 2^(k+1) != k^2 + k^2
That made no sense, anyway im getting closer |
|
He used the induction hypothesis there.
We try to prove 2(k+1) > (k+1)2 using the hypothesis 2k > k2
We have 2(k+1) = 2*2k, so we can apply the hypothesis to 2k
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: Discrete Math Help
« Reply #38 on: Nov 18th, 2007, 9:00am » |
Quote Modify
|
OK I am back and in need of a lot of help. I have a test tomorrow and I've been studying all weekend but I still don't get these. Ill make a list and give sample problems.
combinatorial arguments - I don't understand how to get this, or how to show it. i know it has something to do with counting something in two ways, still makes no sense to me.
We also are suppose to validate this with a tree diagram, But I have no idea how this works.
Given a sequence find recurrence relation - I can do this if I see the pattern, but I have no idea how to get it into degree 2. Sample problem An(a sub n) = n^2 for n>=2. I can get it into a degree one but need to know to degree 2.
Given an closed form find the recurrence relation. I might be able to do this.
I'm also having big trouble with some of the order and repetition concepts.
Order n and Rep y = C(r+n-1,r)
Order y and rep some C(r,k1...kn)
Order n and Rep some C(r+n-1,r) with I.E Im not sure what these are or how to perform them
Anyway here are some samples.
8 types of donuts. have to choose 36 donuts. only can have max of 4 of a, 6 of b and 8 of c. how many ways total?
how many solutions to x1+x2+x3+x4+x5+x6+x7 = 54 where 3x1 4x2 5x3 6  x4,x5,x6,x7
If you can help please do, I need explanations mostly, correct answers would help too. I probably didn't clarify myself well enough, so if you have questions ask please Ill be studying all day pretty much. Thank You
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Discrete Math Help
« Reply #39 on: Nov 18th, 2007, 9:29am » |
Quote Modify
|
on Nov 18th, 2007, 9:00am, Wardub wrote:| combinatorial arguments - I don't understand how to get this, or how to show it. i know it has something to do with counting something in two ways, still makes no sense to me. |
|
I'm not sure what sort of problems you mean; could you give an example (even if you might not understand it)
In general, a specific example-problem would be helpfull
Quote:| Given a sequence find recurrence relation - I can do this if I see the pattern, but I have no idea how to get it into degree 2. Sample problem An(a sub n) = n^2 for n>=2. I can get it into a degree one but need to know to degree 2. |
|
Again, I'm not entirely sure what you mean. There's a number of things I could think of. For example An= An-1+2n+1 would be a recursion which yields the same sequence as An= n2.
Given the sequence
1 4 9 16 25 36
you can start by taking difference, and differences of differences
3 5 7 9 11
2 2 2 2
Since the last is constant, and having done two difference-sequences, we must have a degree two recurrence (afaik)
working up, a[n] =2
b[n] = b[n-1]+a[n-1] = b[n-1]+2 = 2n+1
c[n] = c[n-1] + b[n-1] = c[n-1] + b[n-1] = c[n-1] + 2n +1 (hey, that looks familiar)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Discrete Math Help
« Reply #40 on: Nov 18th, 2007, 9:40am » |
Quote Modify
|
on Nov 18th, 2007, 9:00am, Wardub wrote:| how many solutions to x1+x2+x3+x4+x5+x6+x7 = 54 where 3 x1 4 x2 5 x3 6 < x4,x5,x6,x7 |
|
subtracting 3,4,5, and 4*7 respectively brings all variables to  0, so solving the number of ways to get
x1'+x2'+x3'+x4'+x5'+x6'+x7' = 14
should do it. And this is a matter of dividing 14 'balls' over 7 'bins', or in yet again other words the number of distinct permutations of 14 identical elements with 6 (identical) separators, i.e. C(20,14) = 38760
|
| « Last Edit: Nov 18th, 2007, 9:41am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: Discrete Math Help
« Reply #41 on: Nov 18th, 2007, 2:38pm » |
Quote Modify
|
Thanks so far. As far as the other problem it should look somewhat like. ao = 1, a1 = 6 and an= an-1+6an-2 for n2 That is the form but not the actual answer.
Do you have any idea what I mean by tree diagram? We used it for like counting some binary strings with 00 or stuff.
Here is a small example but I don't know how he did it.
The problem was something like all binary strings of length n with no double 0's. so the tree branched out 0 or 1
x - 1 <---- then he put a y here and said  Sn-1
x-0 ----> 01 (or else theres 2 0s) and he called this w Sn-2
and then he concluded Sn = Sn-1 + Sn-2
O and here is an example for combinatorial problem. Prove C(2n,2) = 2C(n,2)+ n^2. and its not suppose to be algebraic proof either
|
| « Last Edit: Nov 18th, 2007, 2:43pm by Wardub » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Discrete Math Help
« Reply #42 on: Nov 18th, 2007, 3:05pm » |
Quote Modify
|
on Nov 18th, 2007, 2:38pm, Wardub wrote:| Do you have any idea what I mean by tree diagram? |
|
I didn't.
Quote:We used it for like counting some binary strings with 00 or stuff.
Here is a small example but I don't know how he did it.
The problem was something like all binary strings of length n with no double 0's. so the tree branched out 0 or 1
x - 1 <---- then he put a y here and said Sn-1
x-0 ----> 01 (or else theres 2 0s) and he called this w Sn-2
and then he concluded Sn = Sn-1 + Sn-2 |
|
That makes some sense.
if the string ends in 1 you can put anything behind it, if it ends in 0 you can only put 1 behind it. But also, if it ends in 0, then it must end in 10 so you go two steps back in length.
Every valid bitstring is made by taking a valid bitstring (starting with the empty string and 0) and adding either 1 or 10
Quote:| O and here is an example for combinatorial problem. Prove C(2n,2) = 2C(n,2)+ n^2. and its not suppose to be algebraic proof either |
|
What do you mean not algebraic?
Is C(2n,2)=(2n)(2n-1)/2 = n(n-1) + n2 = 2C(n,2) + n2 not allowed?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Discrete Math Help
« Reply #43 on: Nov 18th, 2007, 3:11pm » |
Quote Modify
|
Usually proving an identity combinatorially would mean to show that both sides of the equation "count" the same thing. For example, with C(2n,2)=2 C(n,2) + n2, the left hand side counts the number of two element subsets of a 2n element set. Now you can form such a subset in 3 different ways. Either you can choose 2 elements from the first n elements of the 2n element subset, you can choose 2 elements from the second n elements of the 2n element subset, or you can pick one element from the first n elements and one element from the second n elements. So there are C(n,2)+C(n,2)+n*n total 2 element subsets of a 2n element set, i.e. C(2n,2)=2 C(n,2) + n2.
|
|
IP Logged |
|
|
|
Wardub
Junior Member
Gender:
Posts: 130
|
|
Re: Discrete Math Help
« Reply #44 on: Nov 18th, 2007, 3:50pm » |
Quote Modify
|
Ya what Obob is talking about is correct. Am i suppose to just write that? Seems long. I have a few more questions. How many strings of length 12 have atleast 1 x and 1 y. So would this be C(8,1) * C(8,1) * 26^10?
string length 12 which contain atleast one vowel where letters cant be repeat? Would that be C(8,1)C(26,5) *25!/14!?
Also does anyone know what C(r, k1 + k2 +... kn) means?
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Discrete Math Help
« Reply #45 on: Nov 18th, 2007, 4:17pm » |
Quote Modify
|
Proofs require that you explain all your logic and all the steps involved, so you do need to write a fair amount. Whether you write your solution into sentences and/or paragraphs is up to you, but I would highly encourage it.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Discrete Math Help
« Reply #46 on: Nov 19th, 2007, 12:07am » |
Quote Modify
|
on Nov 18th, 2007, 3:50pm, Wardub wrote:| I have a few more questions. How many strings of length 12 have atleast 1 x and 1 y. So would this be C(8,1) * C(8,1) * 26^10? |
|
I'd go with the method of taking all strings of length 12 and excluding those without x's or y'; i.e. 2612 - 2 2512 + 2412
(subtract the strings without x's, subtract the strings without y's, but then we subtracted the strings with neither x's or y's twice, so add them back once).
Quote:| string length 12 which contain at least one vowel where letters can't be repeated? Would that be C(8,1)C(26,5) *25!/14!? |
|
There are C(26,12) ways to make a string, C(21,12) ways to make a string that doesn't contain a vowel. So subtract the latter from the former and you have all strings of length 12 with at least one vowel.
Basically it's the same trick as before. Rather than count in how many ways you can do a certain thing, you can also count in how many ways you can do the opposite and subtract this from the total number of ways to do anything (in the context).
Quote:| Also does anyone know what C(r, k1 + k2 +... kn) means? |
|
It might, possibly, denote the multinomial r!/(k1! * k2! * .. * kn!)
Doesn't your textbook have an overview of the notations and what they mean? (it's usually in an appendix or on the insides of the cover)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print