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

-1
votes
0answers
21 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
32 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
35 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
15 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
22 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
38 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
25 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
33 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
17 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
23 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
112 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
44 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
18 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
27 views

Number of solutions of equation with natural numbers [closed]

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
55 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
54 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
50 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
40 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
31 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
325 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
36 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
43 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
21 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
17 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
44 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
54 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
50 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
39 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
31 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
13 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
55 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
49 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
22 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
33 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
25 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
22 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
59 views

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

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

How do I express these relations using subsets? [closed]

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
34 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
23 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
24 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
45 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 ...
0
votes
1answer
36 views

Prove that $|A| \geq |B|$ implies $|B| \leq |A|$ [duplicate]

If $|A| \geq |B|$, then there exists an onto function $f: A \rightarrow B$. If $|B| \leq |A|$, then there exists a one-to-one function $f: B \rightarrow A$. My issue is that I don't think that $|A| ...
0
votes
0answers
14 views

The problem of finding a smallest spanning 2-edge-connected subgraph of a graph G is NP-hard

For a given graph G = (V, E) with weights c(e), e ∈ E, the problem of finding a smallest spanning 2-edge-connected subgraph means that one has to find a subset F ⊆ E of smallest weight c(F) ...
0
votes
1answer
24 views

Proof of equivalence theorem using equational calculus

I have to show the following theorem: $p\vee \neg p \equiv ((p \vee q)\wedge \neg (\neg p \wedge (\neg q \vee \neg r)))\vee (\neg p \wedge \neg q) \vee (\neg p \wedge\neg r)$ I have proved $((p ...
0
votes
0answers
16 views

Recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$,$\sum\limits_{i=1}^{k}c_i < 1$ is linear

Let $L: \mathbb N_0 \to \mathbb N_0$ satisfy the recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$ with $c_i \geq 0$ for $i=0,\ldots, k$ and $\sum\limits_{i=1}^{k}c_i < ...
0
votes
4answers
58 views

Prove that if $n$ is odd, then $-n$ is odd.

Here is my work so far, I am missing something quite obvious but I can't seem to link it together: Proof. Let $n$ be an integer. Suppose $n$ is odd. This means that there is an integer $k$ such that ...
0
votes
1answer
33 views

Consider a general arithmetic sequence,$\{x_n\}^{\infty}_ {n=1}$, defined by $x_n = a+nb$

Consider a general arithmetic sequence,$\{x_n\}^{\infty}_ {n=1}$, defined by $x_n = a+nb$, ($n ≥ 1$).Prove that if $c$ is any integer such that gcd$(b,c) = 1$ then there is some element of the ...
0
votes
0answers
33 views

Consider the sequence of positive integers An, for n ≥ 1, defined by $A_n = 10^{2^n} + 1$.

Consider the sequence of positive integers $A_n$, for $n \geq1$, defined by $A_n = 10^{2^n} + 1$. 1) Prove that the elements of this sequence are pairwise coprime, i.e. prove that if $m \neq n$ then ...
0
votes
0answers
23 views

Master Theorem for common recurrence

I have the following recurrence: $$T(n) = T\bigg(\frac{n}{2}\bigg) + O(n)$$ And I am trying to find the time complexity using the master theorem. So I have: $a = 1, b = 2$ $f(n) = O(n) = c(n)$ ...