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
2answers
20 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
10 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
0answers
11 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
94 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
36 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
9 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
25 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
50 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
45 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
39 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
34 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
18 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
308 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
23 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
15 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
38 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 … ...
1
vote
1answer
43 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
50 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
20 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
52 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
32 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
32 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
33 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
12 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
13 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
54 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 ...
-3
votes
0answers
37 views

Find all cases in which $A \times A$ contains the same number of elements as a given finite set $A$. [on hold]

I am doing this for my discrete math class, could you guys explain to me how to to this? Find all cases in which $A \times A$ contains the same number of elements as a given finite set $A$.
0
votes
0answers
24 views

Decode the text using a 3×3 Hill Cipher [on hold]

Decode the text using a 3×3 Hill Cipher NKVCHDGPVZYKHYESCHUWOTRUNKUEXFQDHVJMGIVHNCUYGYKJNXNGWLOKVJRUDYYBGNYCZVHYRFZFDBCSCPFGOTBDLDKOM Given Plaintext - 'theintern' How do I decrypt ?
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
20 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)$ ...
1
vote
2answers
29 views

Show that ¬p ∨ (r →¬q) and ¬p ∨¬q ∨¬r are equivalent.

I am new in Discrete Math so that I am still not familiar with Logical Equivalent rules. 1) Show that ¬p ∨ (r →¬q) and ¬p ∨¬q ∨¬r are equivalent. My Try: ¬p ∨ (r →¬q) $\equiv$ ¬p ∨ (¬r∨ q) ...
1
vote
2answers
53 views

What is the remainder produced when the integer 2099^(2017^13164589) is divided by $99$? [on hold]

I'am looking for the remainder produced when the integer $2099^{2017^{13164589}}$ is divided by $99$ ? The goal reached is to avoid large integers.
2
votes
1answer
12 views

Nested Quantification of exactly one.

Suppose my domain is "All students in the class" and P(x, y):= x has emailed y. So, how do i define: Every student has emailed exactly one student. Exactly one student has emailed every one. A ...
2
votes
3answers
46 views

Given $3$ types of coins, how many ways can one select $20$ coins so that no coin is selected more than $8$ times.

So I was given this question. Given $3$ types of coins, how many ways can one select $20$ coins so that no coin is selected more than $8$ times. First I make $x_1 + x_2 + x_3 = 20$ Then $ 0 \leq x_i ...
0
votes
2answers
52 views

Big-Oh Analysis of For Loop

I have the following for loop: sum = 0 for i = 1 to n do for j = 1 to i^3 do for k = 1 to j do sum++ What is the strategy to determine ...