Explore BrainMass

Discrete Math

Big-Oh Proving Question

A. Use the definition of big-oh to prove that 3n - 8 - 4n^3 / 2n - 1 is O(n^2). B. Use the definition of big-oh to prove that 1 . 2 + 2 . 3 + 3 . 4 + ... + (n - 1) . n is O(n3).


A. Convert (11101)2 to base 16. b. Use the Euclidean algorithm to find gcd(34,21).

Recursive definition

I need to give a recursive definition with initial condition(s). a.) The sequence {an}, n = 1,2,3,... where an = 2n. b.) The Fibonacci numbers 1, 1, 2, 3, 5, 8, 13, ....


For each case, think of a set S and a binary relation p on S for - A. p is reflexive and symmetric but not transitive b. p is reflexive and transitive but not symmetric c. p is reflexive but neither symmetric nor transitive


Prove: any subgroup of the order of p^(n-1) in a group of order p^n, where p is a prime, is a normal subgroup

Discrete Math

The following is is meant to have some assumptions made (like "n"). I have been up all night trying to figure this out. It can't be Euler because the vertices can't be >1. It might be Hamilton if I assume that E of G(V,E) is infinte..but how would I get my answer? I would just have sets (e1, e2,...) Could this be a straight

Discrete Math : Set Relations

Let SIGMA = {a,b} be an alphabet. a. List between braces the elemnts of SIGMA4. the set of strings of length over SIGMA. b. Let A = SIGMA1 U SIGMA2 and B = SIGMA3 U SIGMA4. Describe A, B and AUB in plain English.

Venn Diagrams : Union, Intersection and Compliment

A. Write the first 6 elements of the following sets: E is the set of even numbers E={ } L is the set of numbers divisble by 11. L={ } S is the set of numbers divisible by 6. S={ } b. Draw a Venn Diagram to represent the relationship among E,L,S. c. Place the following five numbers on the V

Game Theory : Two-person, Constant-Sum Games

The attached file has a problem that I can't figure out how to set up. Can you take a look and explain how this problem should be set up? There are two people playing a two-person constant-sum game. Player 1 wants to travel from New York to Dallas using the shortest of the possible routes listed below. Player 2 has the ab


To prove that a statement of the form "If P then Q", you may assume that: A. P=Q B. P is true C. Q is true D. P is false E. nothing until it has been proved


To prove a statement "If P then Q", it is valid to prove which of the following statements instead? A. If not Q then not P B. If Q then P C. If not P then not Q D. Q only if P E. Both P and Q are true

The number of chain links required to pay for n days.

A traveler owing a gold chain with 7 links is accepted at an inn on condition that he pay one link of the chain for each day he stays. if the traveler is to pay daily and may be given links already used in payment as change, show that he only needs to take out one of the links of the chain in order to pay each day for 7 days. (n

Proof Set is Countable : Bolzano-Weierstrass Theorem

Given S is a subset of R Suppose S' (set of all accumulation points in S) = emptyset Prove S is countable. I think I am supposed to use the Bolzano-Weierstrass Theorem but I can't figure out how to apply it.

Venn Diagrams : Union and Intersection of Sets

Given the universal set of {x 0<x< 10}(this should read less than and equal too) and sets A,B,and C as defined below: A={factors of 6) B= {factors of 10} C= {odd numbers} a. List the elements in A U B U C. (they are suppossed to be upside down U"s ) b. State A U (B U C). (the U in between the b, c is the wrong way).

Probabilities and Set Theory

We say that an event A E A is nearly certain if A is nearly certainly equal to OMEGA. In other words, OMEGA = AUN , where N is a negligeable set.

Probabilities and Set Theory

Please see the attached file for the fully formatted problems. Let (Omega, A, P) be a probability space. We consider a series of mesurable sets (An)nEnCA . Prove that P(lim infnAn).... Prove that if the series is convergent, we have continuity, i.e. ...

Probabilities and Set Theory

Please see the attached file for the fully formatted problems. Let (Omega, A) be a measurable space, and P:A--> [0,infinity] an application such that P(AUB) = P(A) + P(B) when A,B E A and A intersection B = ø, and P(Omega) = 1 . Prove that the following statements are equivalent: (i) P is a probability (ii) P is continuou

Probabilities : Set Theory

Please see the attached file for full problem description with proper symbols. --- Let A and B be two events such that P(A) = 3/4 and P(B) = 1/3. Prove that 1/12=<P(A intersection B)=<1/3 and give two examples where these limits are reached. In the same way, find an interval for P(AUB) .

Set Theory : Solve

If A={1,3,4}, B={2,4,6,8), C=(1,4,5} and the universe is the counting numbers less than, then find the following: A. AUB(B has line over it) B. AU(BnC)

Binary Operations : Monoids

Let S be a set with an associative binary operation but with no identity. Choose an element 1 not belonging to S, write M = {1} or S, and define an operation on M by using the operation of S and 1s=s=s1 for all s belonging to S. Show that M is a monoid.

Revenue Function, Profit Function and Maximum Profit

Problem: A company makes cameras. The price per camera at which x million cameras can be sold is: p(x) = 94.8 - 5x. 0 -< x -< 15 (the symbol -< is the "greater or equal to sign", I couldn't get it to work on my computer) The cost of making x million cameras is: c(x) = 156 + 19.7x (x is in millions of

Binary Operations : Equivalence Classes

Note. I don't how to make a letter with a line overtop of it so the equivalent notation here is *. ex) a* = a bar (a with a line overtop of it) Let M be a commutative monoid. Define a relation ~ on M by a ~ b if a = bu for some unit u. (a) Show that ~ is an equivalence on M and if a* deontes the equivalence class of a, let