Discrete math Definition and 214 Threads

The book works out the case with x and y irrational and xy rational. They used the nonconstructive existence proof method with x = sqrt(2) and y = sqrt(2). If that's rational, then you're finished. If it's irrational, then you can simply raise it to the power of sqrt(2) to get 2. I'm not sure...

"For the router to support the new address space it is necessary that the latest software release be installed." I said Q: The latest software released be installed R: The router to support the new address space. I interpreted this as Q is necessary for R, therefore R => Q. The professor has...

Homework Statement Use the equivalence p\rightarrow(r \rightarrow s) \equiv p\wedge r\rightarrow s to rewrite the following problem before the proof. Homework Equations [p\rightarrow (q\rightarrow r)]\wedge (p\rightarrow q) \tautologicallyimplies (p\rightarrow r) The Attempt at a...

Here's the problem. Theorem: If n^2+1 is odd, then n is even. Give indirect proof.

I am currently a CS undergrad. my university offers no courses in Abstract algebra or Number theory or Topology or Analysis. recently I have got interested in Number theory in Discrete math course. moreover I was and still am interested in algebra too. but the problem is, can I apply to CS grad...

Hi guys, Long time lurker of this forum, but first time poster. Discrete Math is going to be the end of me; I'm just not understanding how to solve problems and write the proofs. Any help would be greatly appreciated. Thanks in advance. The Problem: Let nεZ≥1. Show that...

Did this as a homework problem, got it wrong obviously. Not too sure how to solve it otherwise Homework Statement Let f be a function from A to A. Prove that for all m,n ε N, f^m*f^n = f^(m+N) Homework Equations The Attempt at a Solution f^(m+1) f^(n+1) = f(f^m) * f(f^n) =...

Homework Statement Figure out a self-referential formula for the number of handshakes required for a group of n aliens to introduce themselves by hand-calculating a few small values and coming up with a solution. Homework Equations We are given: Let H(n) be the number of handshakes...

Homework Statement Using contradiction, prove that for every four positive real numbers c, d, e and f, at least one of c, d, e, f is greater than or equal to the average of c, d, e, f. Homework Equations I don't believe that there are any relevant equations for this problem. I do know that...

From a pdf textbook: Example (infinite sets having the same cardinality). Let f : (0, 1) → (1,∞) be defined by f(x) = 1/x. Then f is a 1-1 correspondence. (Exercise: prove it.) Therefore, |(0, 1)| = |(1,∞)|. Exercise. Show that |(0,∞)| = |(1,∞)| = |(0, 1)|. Use this result and the fact that (0,∞)...

Homework Statement Determine if the statement is true or false. Prove those that are true and give a counterexample for those that are false. If r is any rational number and if s is any irrational number, then r/s is irrational. Homework Equations A rational number is equal to the...

Homework Statement Prove by contradiction. Your proof should be based only on properties of the integers, simple algebra, and the definition of rational and irrational. If a and b are rational numbers, b does not equal 0, and r is an irrational number, then a+br is irrational. Homework...

Homework Statement Let A be the set of all integers x such that x is = k2 for some integer k Let B be the set of all integers x such that the square root of x, SQRT(x), is an integer Give a formal proof that A = B. Remember you must prove two things: (1) if x is in A, then x is in B, AND...

Homework Statement How many positive divisors does each of the following have? 2^n where n is a positive integer. and 30 The Attempt at a Solution for 30 i get 2 , 5 , 3 , 10 but my book says 2 ,3 ,5 I don't understand why 10 isn't a divisor. and for 2^n I am trying...

1. For any integer n, prove that 3 divides n^3 -n The Attempt at a Solution I'm stuck. I understand that means that n^3 -n mod 3 =0. or I can n^3 -n can be expressed as 3x. But I don't know how to prove it. Where do i go from here. Thanks

Homework Statement Homework Equations I need to prove this by using induction. I need help with the induction step. The Attempt at a Solution. Basis step: let n=0; 2^0 = 2^(0+1) - 1 -----> 1=1

Homework Statement Define the relation a I b ( a divides b) between integers a and b and then define the greatest common divisor, gcd ( a,b), and the lowest common multiple, lcm ( a,b) Is there any number for m for which you have n I m ( n divides by m) for every n. I just found this...

1. Show by example that it is possible for g°f(x) to be surjective while f(x) is not I am confused by the general pattern of injectivity (one-to-one) and surjectivity (onto). I know the following by looking through my book: If f and g are surjective, then g°f is surjective. If f is...

Homework Statement Solve the congruence 2x≡7 (mod 17) Homework Equations None. The Attempt at a Solution I think my main problem with this is I am still confused on what modulo actually means. But I'll save that for some other time. So here is what I have done so far. I...

Homework Statement Is the following a statement: "Next year interest rates will rise" Homework Equations Sort of obvious, but a statement is defined as something which is true or false. The Attempt at a Solution I'm guessing that it is a statement, even if it isn't known whether it...

Homework Statement A = {0, 1, 2, 3, 4 ,5} Let R be a binary relation on set A such that: R = {(0,1), (1,0), (1,3), (2,2), 2,1), 2,5), (4,4)} a. Make a Directed Graph for the relation R on A b. What must be added to R to make it reflexive/symmetric?

Homework Statement Homework Equations base case: n=1 The Attempt at a Solution im not sure where to start because the examples that my professor showed us did not have a n(n-1) (n+1) but rather (p+1)P=1+1)(2(p+1)+1) im just very lost in this example

Discrete Math -- Proof methods Homework Statement Prove |x-y| ≤ |x| + |y| for all real numbers x and y (where |x| represents the absolute value of x, which equals x if x≥0 and equals -x if x<0). prove by cases Homework Equations The Attempt at a Solution

Homework Statement Suppose n > 1 people are positioned in a feld, so that each has a unique nearest neighbour. Suppose further that each person has a ball that is thrown at the nearest neighbour. A survivor is a person that is not hit by a ball. Prove that if n is odd, then there is at least...

Homework Statement Let their be a set A, and let B be the set: {A, {A}} (the set containing the elements A and the set that contains element A) As you know, A is an element of B and {A} is also an element of B. Also, {A} is a subset of B and {{A}} is also a subset of B. However...

Which one is a better course to take? I feel like MATLab is simple enough I can learn on my own if I ever need it. How useful is discrete math in physics? Should I take that now or stick to MATLab?

I think I've screwed up my future. I am in my third year, double major in physics and math (math major more to supplement my understanding of physics), and this semester was just horrid. I made the mistake of moving off campus, working two jobs, and in the time I had to study, could not focus...

Homework Statement The statement that S is a number segment means that there are numbers a and b and S is the set to which x belongs only in case x is a number between a and b.Problem 1) If each S1 and S2 is a number segment and there is a number common to S1 and S2 then is the common part a...

Discrete math -- links to biology? Hey, I'm in a math and biology program in college and I've recently become more and more into the discrete side of math. I was wondering if anybody knew of any areas of research that integrate discrete mathematics and biology, as there doesn't seem to be...

Homework Statement Prove that H1 +H2 +...+Hn = (n +1)(Hn-n)? Homework Equations Hn denotes the nth harmonic number. The nth harmonic number is the sum of 1+1/2+...1/n, which is n / n +1. I'm not really sure if Hn = (1/ n) . Prove by Mathematical Induction Hn denotes the...

Homework Statement Prove that 3 divides n3 + 2n whenever n is a positive integer. Homework Equations The Attempt at a Solution Basis Step : P(1) : [13 + 2(1) ] /3 [1+2] /3 [3]/3 1 Since 3/3 =1, P(1) is true Inductive Step: [ k3 + 2k...

Another one of my homework asks is this true or false and prove it: For all sets A, B, and C if A U C is a subset of B U C then A is a subset of B Please help!

One of my homework problems says is this true or false and prove your answer: For all sets A, B, C if A n C is a subset of B n C then A is a subset of B. I believe the answer is true but i have no idea please help!

I'm completely stumped on how to begin a discrete math proof, and I'm looking for a little advice on what might be a good way to approach this. In a previous problem I did a proof by contradiction to show that at least one of the real numbers a1, a2, ... an is greater than or equal to the...

I need to show that P<->Q is logically equivalent to ( P ^ Q ) v ( ~P ^ ~Q) So far I have P <-> Q is equivalent to ( ~P v Q ) ^ ( ~Q v P ) by a example I have no idea where to go from here

Discrete Math "Proper Subsets" Hey everyone, I am confused on part of this. Any input would be much appreciated! X has ten members. How many members does ~P(X) have? (~P is the set of all subsets) How many proper subsets does X have? Well the number of members of ~P is 2^10 or 1024...

Homework Statement Okay so I'm trying to teach myself the first three chapters if Grimaldi before I take a discrete math course in January. I'll probably be posting a few problems. The question is as follows: In how many ways can we select n objects from a collection of size 2n that...

1. Homework Statement Use set builder notation to give a description of each of these sets. a) { 0,3,6,9,12 } b) { -3, -2, -1,0, 1, 2, 3 } c) { m,n,o,p } 3. The Attempt at a Solution X={x l x is an odd possitive multiplier of 3 less than 12 } X is supposed...

"Pure" Mathematics vs. Applied Math vs. Discrete Math I'm approaching the point where I'm going to have to decide which four-year university I'm going to finish my Bachelor's degree at. I'm pretty much restricted to colleges in Georgia, and I am primarily looking at Georgia State and Georgia...

Anybody know of any uses of discrete math in physics? I learned proof by induction in discrete math. Is that used to prove anything in physics? Any other examples that you can think of?

Hi, I have some troubles with this question. Define an operator * on R by x*y = 2xy -x -y +1 a) is * commutative? b) is * associative? I can easily see that * is commutative, but how do i test for associativity? The rule states that (x*y)*z = x*(y*z) But what is z ?

Homework Statement If I want to know how many ways there are to distribute 11 chocolate chip cookies to 50 children, is there any way to do this without brute force? Homework Equations The Attempt at a Solution

Homework Statement Find all pairs of integers a, b such that their GCD and LCM are 14 and 168 respectively. Homework Equations a x b = gcd(a,b) x lcm(a,b) (useful?) The Attempt at a Solution confused...

Homework Statement Find the remainder of dividing 2(562009)-3. Homework Equations Let m be a positive integer. If a\equivb (mod m) and c\equivd (mod m), then a + c \equiv b + d (mod m) and ac\equivbd (mod m). The Attempt at a Solution Using ac\equivbd (mod m): (2 mod...

In statistics I learned how to do this problem one way, & in discrete mathematics I learned how to do it another way, but the answers don't jive. So I'm wondering if I'm doing something wrong. Below is the question. A bakery produces six different kinds of pastry. If the different kinds of...

Homework Statement Suppose that we play the following game. You are given a pile of N matches. You break the pile into two smaller piles of m and n matches. Then you form the product 2mn and remember it. Next, you take one of the piles and break it into two smaller piles (if possible), say of...

If m and n are positive integers, (mn)!=m!n! Prove or disprove. its so obviously true i can't prove it. anyone help? -also- Prove: The square root of a prime integer is an irrational number. any help?

Suppose a,b,c,d are integers and a DOES NOT equal c. Suppose that x is a real number that satisfies the equation: (ax+b)/(cx+d)=1 Must x be rational? If so, express x as a ratio of two integers. I have no idea how to begin this problem.

Homework Statement prove or disprove that E[X^2] = E(X)^2 Homework Equations E[X] = \sumxi*pr(xi) The Attempt at a Solution I really don't know where to start, I believe that it is not true, so I should try to disprove it, and the easiest way to do that would be by...

Homework Statement In the following you are given a 5-card hand from a 52 card deck. a) given that you have at least one ace, what is the probability you have at least 2 aces? b) given that you have the ace of diamonds, what is the probability that you have another ace? c) given that you...