The study of discrete mathematical structures. Consider using a more specific tag instead, such as: (combinatorics), (graph-theory), (computer-science), (probability), (elementary-set-theory), (induction), (recurrence-relations), etc.

learn more… | top users | synonyms

0
votes
1answer
19 views

If $m | (8n +7)$, $m | (6n + 5)$, prove that $m = ± 1$

If $m | (8n + 7)$, $m | (6n + 5)$,prove that $m = ± 1$ -We have just starting going over the "divides" notation, and I am aware of a few properties and theorems from my notes. I am; although, a bit ...
2
votes
2answers
23 views

If $\gcd(a, c) = 1$ and $b | c$, prove that $(a, b) = 1$

If $\gcd(a, c) = 1$ and $b \mid c$, prove that $(a, b) = 1$ -Not sure how to approach this problem. -We have just started the greatest common divisor section, and looking at my notes I see that ...
3
votes
3answers
27 views

If a is an integer, prove that $gcd(14a + 3, 21a + 4) = 1$

If a is an integer, prove that $gcd(14a + 3, 21a + 4) = 1$ -We have just started the section on greatest common divisor, one thing I know is that $gcd(a,b) = ax + by$ -My initial thought is that we ...
2
votes
2answers
27 views

Probability of island having 8 people born with disease, estimate?

The chances of being born with a certain disease are estimated as $1$ in $1200$. What is a good estimate of the chance that an island with $10000$ inhabitants has precisely $8$ people born with that ...
3
votes
1answer
18 views

What is the probability that these two objects are of the same color?

We have $11$ bins with $10$ objects each. Every object is either black or white, and the $i$th bin ($1 \le i \le 11$) has precisely $(i -1)$ black objects in it. Someone selects, uniformly at random, ...
0
votes
1answer
7 views

How can i show a pair forms a semigroup?

An operation . is defined on the set $Z×Z$, ie. the set containing all pairs of integers by: $(u,v).(x,y)=(u+v,v.y)$ How can i show that the pair ($Z×Z$, . ) forms a semigroup?
2
votes
1answer
26 views

Are these two events $A$ and $B$ independent?

Abe and Bernard are dealt five cards each from the same $52$ card deck. Let $A$ be the event that Abe gets a flush (five cards of the same suit) and $B$ be the event that Bernard’s five cards are of ...
4
votes
1answer
18 views

$p(X)$, $P(Y)$, $p(Z) > 0$ and every pair of these events is independent, then $p(X \wedge Y \wedge Z) > 0$?

Is the following statement true or not? Let $X$, $Y$, $Z$ be $3$ events in the same sample space such that $p(X)$, $P(Y)$, $p(Z) > 0$ and every pair of these events is independent. Then $p(X ...
-1
votes
0answers
15 views

How can i find a semigroup?

An operation * is defined on the set $\mathbb{Z} \times \mathbb{Z}$, ie. the set containing all pairs of integers by: (u,v)*(x,y)=(u+v,v*y) How can i show that ...
0
votes
2answers
26 views

Find a solution $x\in\mathbb{Z_{\mathrm{784}}}$ for $x\cdot\overline{602}=\overline{308}$

I know that I have to find a positive integer $x$ that I can multiply with $602$ and then divide the result by $784$ so that the remainder of that integer division is $308$. I am sure that this is ...
2
votes
1answer
31 views

In how many ways can we pick a group of 3 different numbers from the group $1, 2, 3, …, 500$ such that one number is the average of the other two?

Here's the question which I'm struggling with - In how many ways can we pick a group of 3 different numbers from the group $1, 2, 3, ..., 500$ such that one number is the average of the ...
1
vote
1answer
12 views

Translate quantification into English and give the truth value

The problem is: $\exists x \in \mathbb{R} (x^3 = -1)$ I understand the following: $\exists x$ = There exists an $x$ $\in$ = shows the element before it is a member of a set after it $\mathbb{R}$ = ...
1
vote
1answer
19 views

equivalence relation and quotient set, Given $A = \{0,1,2,3,4,5\}$

Given $A = \{0,1,2,3,4,5\}$, Write the appropriate equivalence relation of this quotient set: $$A/_R = \{\{1,2\},\{3\},\{4,0,5\}\}$$ Well, if it was to compute $$A/_R = ...
4
votes
2answers
30 views

Pair of friends and a pair of “enemies” in each group of three students

The problem: There is a class. In each group of three students in the class there is a pair of friends and a pair of "enemies". Find the maximum number of students in the class. I tried to play with ...
0
votes
1answer
20 views

If P(i) is true for all integers i with 2≤i≤k as inductive hypothesis, then why also p(t) is true by the inductive hypothesis?

"Let P(n) be the property n is divisible by a prime number. We prove that P(n) is true for all integers n with n> 1. Basis step. If n=2, then P(n) is true because 2 is a prime and every ...
0
votes
2answers
25 views

Discrete Math: Determining if Argument is Valid

I understand there are two ways to determine validity of an argument. The first way is to construct a truth table and if the statement consisting of the premises combined together implying the ...
0
votes
0answers
15 views

Small graphs containing all trees on $n$ vertices

What do those graphs look like which contain a copy of every tree on $n$ vertices and such that no proper subgraph has this property?
0
votes
1answer
16 views

Determining if Argument is Valid via Short-Cut Method

I understand there are two ways to determine validity of an argument. The first way is to construct a truth table and if the statement consisting of the premises combined together implying the ...
4
votes
2answers
106 views

What am I counting wrong?

EDIT: I made a mistake in the beginning, the second condition has changed. Sorry for this. I'm asked to count the number of sets of 4 elements that satisfy the two following conditions: 1) Each ...
3
votes
3answers
40 views

Simplify $(k +1)! > (k + 1)^2$ to prove true for $k ≥ 4$

I am trying to prove this statement is true for $k ≥ 4$. I don't know how to work with $k + 1$ factorial, so I'm a little lost on proving this.
1
vote
2answers
12 views

Prove equivalence ratio and find class of $B\subseteq A$ , $X \sim Y \Leftrightarrow X \cap B = Y \cap B$

Prove equivalence ratio and find class of $B\subseteq A$ , $X \sim Y \Leftrightarrow X \cap B = Y \cap B$. Well, I've proved really easily that it is reflexsive, symmetrical and transitive. But I'm ...
-1
votes
0answers
26 views

Number of solutions of equation with natural numbers [on hold]

Given natural numbers $s, n, k$. How to find number of solutions to equation $a_1 + a_2 + \ldots + a_s = n-s$ where $0 \leq a_i \leq k-1$ and $a_i \in \mathbb{N}$?
2
votes
3answers
52 views

Can I further simplify $5^k \cdot 5 + 9 < 6^k \cdot 6$ to prove this is true

I am trying to prove this statement, but I'm not sure where to go from here. Is don't think this is sufficiently reduced to conclude the statement is true, but I'm not positive. $k ≥ 2$ Can I ...
0
votes
3answers
47 views

Prove $n^3 + 7n + 3$ is divisible by 3 for all integers n ≥ 0

The statement I'm trying to prove is: $n^3 + 7n + 3$ is divisible by 3 for all integers n ≥ 0 I eventually need to prove $(k + 1)^3 + 7(k + 1) + 3$ is divisible by 3. I don't really understand ...
2
votes
1answer
43 views

Proving that a function grows faster than another

I'm told to prove or disprove that $4^{\sqrt{n}}$ grows faster than $\sqrt{4^n}$ As n tends to infinity. From my Previous years Calculus I know that if I take the derivative of two functions, and one ...
0
votes
1answer
37 views

Mathematical induction condition “p(k)$\Rightarrow$p(k+1)” for the divisibility by a prime number

" Mathematical induction If p(n) is a statement involving the natural number n such that: p(1) is true, and p(k)$\Rightarrow$p(k+1) for any arbitrary natural number k, then p(n) is true ...
1
vote
0answers
26 views

What is the probaility that two random permutations have same order?

I am interested in the orders of random permutations. Since the law of the log of the order of a permutation converges to a normal law (for instance Erdös-Turan Statistical group theory III), one ...
4
votes
1answer
314 views

Is there a way to find expected value of equation?

If the random variable $X$ is binomially distributed with parameters $n=6$ and $p=0.3$, what is $$E(4+3X^2)$$ I know $E(X) = np = 1.8$. I solved this problem by finding $P(X)$ of all $X$ using ...
0
votes
1answer
27 views

Is the relation $xRy$ iff $|x - y| \leq 2$ transitive?

Question: $xRy$ iff $|x-y| \leq 2$ I think I've found this to be reflexive and symmetric, but I'm stuck on transitivity. Can someone assist me with testing transitivity?
1
vote
2answers
36 views

Proof with Combinatorial Argument $\sum_{i = 1}^{n} (i-1) = nC2$

I am trying to prove below equation with combinatorial argument but I have no idea how this works. $$\sum_{i = 1}^{n} (i-1) = nC2$$ Can anyone give me a clue?
-2
votes
0answers
16 views

probablitly using bayes theroem

Three numbered urns contain colored balls as described in the table below. One of the urns is picked at random and a ball is drawn from the urn; the ball is red. What is the probability the ball can ...
0
votes
1answer
13 views

Prove that: $n^2+3n^3 + 6^{lgn} is $ $\theta(n^3)$

I'm asked to prove that: $n^2+3n^3 + 6^{lgn} is $ $\theta(n^3)$ I know that for Big O, I need to show: $f(n) <= c*g(n)$ But I'm not sure how to show this, since it involves theta. Any help would ...
-1
votes
0answers
42 views

Closed form for $\left(\sum_{k=0}^n\frac{x^k}{k!}\right)^p$

The expression for the p-th power of the sum of the first $n+1$ powers of x is given analytically by ...
0
votes
2answers
49 views

Prove for all integers n such that n ≥ 3, $ 4^3 + 4^4 + 4^5 … 4^n = \frac{4(4^n - 16)}{3}$

I am trying to prove this using mathematical induction, but I'm lost once I get to comparing the two sides of the equation. Proposition: For all integers n such that n ≥ 3, $ 4^3 + 4^4 + 4^5 … ...
2
votes
1answer
47 views

Converting programming logic to mathematical notation

How do I go about converting programming logic to mathematic notation? For example, I read a question that asks: ...
2
votes
2answers
33 views

Counting permutations with given condition

I need to find number of permutations $p$ of set $\lbrace 1,2,3, \ldots, n \rbrace$ such for all $i$ $p_{i+1} \neq p_i + 1$. I think that inclusion-exclusion principle would be useful. Let $A_k$ be ...
0
votes
2answers
27 views

How to make this inclusion-exclusion argument

I'm asked to count the number of functions $f:\{1,2,3,4\} \rightarrow\{1,2,3,4,5\}$ such that $f(1)∉\{f(2),f(3),f(4)\}, f(2)\neq f(3), f(3) \neq f(4)$. How do I make the inclusion-exclusion argument ...
0
votes
1answer
12 views

Simplifying DNF conversion?

Context: I have a huge circuit with lots of input bits (around 300). Among these, only about 40 are free, the others are fixed by the current state. I have to find all satisfying assignments knowing ...
0
votes
1answer
51 views

Null Bilinear Forms $x^T A y = 0$, where $A$ is square and full rank.

Let A be a full rank square matrix (A has no null space). When does $y^T A x = 0$ occur ? It could be that this problem is case-specific, so please find attached a document where x,y, and A take ...
0
votes
3answers
46 views

How did $-(2^{k-1})-(2^{k-2}) -\dotsb-(2^0)$ become $-2^k+1$?

I have a question, how was the geometric series collapsed to be in the form of $2^{k+1}$?
0
votes
2answers
21 views

Can I do universal instantiation on this predicate?

Can I do universal instantiation on the following predicate : $ \forall x\;S(x)\; \lor\; \forall x\;L(x)$ become $S(c)\lor L(c)$ or is it has to be $\forall x\; ((S(x) \lor L(x))$ to be able to do ...
1
vote
1answer
29 views

Sum of Reciprocals

I wonder if someone help me with this: I have $\pi_1+\pi_2+ \pi_3 +\pi_4=A$ and $\pi_1\pi_2\pi_3\pi_4=B$ where $\pi_i \;\forall i=1,2,3,4$ are unknown but $A,B$ are known numbers. Can I find for ...
0
votes
1answer
23 views

Am I showing relations correctly using subsets?

The question is: Let $S = \left\{a,b,c\right\}$. Recall that a relation on $S$ is a subset of $S\times S$. Give an example of a relation $R$ on $S$ that is reflexive and: a. Symmetric but not ...
0
votes
1answer
21 views

finding a DNF with an expression that contains quantifiers

I am supposed to use equivalencies to find the prenex DNF for the wff: $\exists xp(x) \land \exists xq(x) \rightarrow \exists x(p(x) \land q(x))$ It's been awhile since I've done something like this ...
-1
votes
3answers
53 views

Showing $k^2 + m^2$ is odd when $k$ is odd and $m$ is even [on hold]

Prove that if $k$ is any odd integer and $m$ is any even integer, then, $k^2 + m^2$ is odd.
0
votes
1answer
16 views

How do I express these relations using subsets? [on hold]

Let S = {a,b,c}. Recall that a relation on S is a subset of S×S. Give an example of a relation R on S that is reflexive and: a. Symmetric but not anti-symmetric. b. Anti-symmetric but not symmetric. ...
0
votes
1answer
33 views

Am I doing this relations question correctly?

Let S = {a,b,c}. Recall that a relation on S is a subset of S×S. Give an example of a relation R on S that is reflexive and: a. Symmetric but not anti-symmetric. b. Anti-symmetric but not ...
0
votes
2answers
22 views

(P and(not(not P or Q))) or( P and Q) equals P

I've been trying to verify the condition above but I get stuck on the passage : $$(P \land (P \land \lnot Q)) \lor (P \land Q)$$ I don't know how to simplify it since there are two ands and a not Q. ...
0
votes
1answer
22 views

Prove a relation is transitive

I've stumbled upon this question in my discrete math book: Prove $$ R = \{(x,y) \in N \times N \ | \ 2x \mid y^2 \} $$ is transitive. I tried thinking about it having to do something with division ...
0
votes
2answers
41 views

threshold for random 2-sat

I'm looking at notes on the threshold for random 2-sat which is given as $r_{2}^{*}=1$. In the first part of proving the threshold they claim that a 2-sat formula is satisfiable if and only if the ...