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
0answers
7 views

How many cases can draw diagonals that Applicable 2 above condition?

Imagine A $n$_regular polygon that vertex is named by $1$ to $n$. We know can draw $\frac{(n)(n+3)}{2}$ diagonals in $n$_regular polygon and also know if we want draw Maximum diagonals are not ...
0
votes
0answers
3 views

Scaling for Matlab fft operation?

I have a $N$ complex signal samples (QPSK) and I am creating an OFDM signal. When I am doing a IFFT operation in matlab, I use following command: $$Y=(dft/sqrt(N))*ifft(X),$$ where $X$ is the input ...
0
votes
2answers
18 views

discrete math use an element argument

Q)Let U be a universe.Use an element arguement to prove the following statement. For all sets A,B and B in P(U),(C-A) u (B-A)⊆ ( B U C) -A. Def : Z ⊆ W ={(z,w):x∈ X and y ∈ Y}. Proof: W=(C-A) U ...
2
votes
1answer
39 views

Upper limit for Big O notation isn't established?

We say that a function $f(x)=O(g(x))$ if $\exists x_0\in \mathbb{R}_+$ and $\exists C\in \mathbb{R}_+$ such that $\forall x\geq x_0$, $|f(x)|\leq C g(x)$. So with this definition, the function ...
1
vote
1answer
27 views

Easiest way of finding a root of permutation?

I've been searching extensively for the simplest way of finding a root of a permutation, but I can't understand half of the things that I've found. Let's say we have 2 permutations: $\alpha^2 = ...
-3
votes
1answer
20 views

Exclusive or (XOR) proof [duplicate]

The question is to prove: X'⊕ Y = X⊕Y' = (X⊕Y)' State laws used (' meaning negation) Thank You
2
votes
1answer
18 views

Difference between necessary and necessary but not sufficient?

This is from Discrete Mathematics and its applications I read up on necessary and sufficient from here What is the difference between necessary and sufficient conditions? If p->q (p implies ...
0
votes
1answer
16 views

Is these Trees isomorphic or not?

Is these Trees isomorphic or not? They have same structure but they have different code. Because one of them is minimum code. Thank you for your answers in advance.
0
votes
1answer
15 views

Expressing the converse, contra-positive, and inverse of conditional statements

This problem is from Discrete Mathematics and its Applications Here is my book's definition on converse, contrapositive, and inverse And the common ways to express an implication For this ...
0
votes
1answer
46 views

Generating function $D(x) = (1 + x)(1+x^2)(1+x^3)\cdots$ [on hold]

Let $$D(x) = (1 + x)(1+x^2)(1+x^3)\cdots $$ 1) What is the inverse function of $D(x)$? 2) What sequence is generated by $D(x) $ Please don't vote down, the subject is complicated for me. Sorry ...
0
votes
1answer
20 views

Draw a 2-3 tree, insert and delete a key

Assume that at the nodes of a 2-3 tree, the following keys are saved (in an increasing order): $3,6,9,15,18,21,24, 27, 30, 33, 36$. It is also given that the root is a 2-node that contains the number ...
1
vote
1answer
39 views

Discrete math - Prove that a tree with n nodes must have exactly n - 1 edges? [duplicate]

I'm new in discrete math. Can someone prove simply that a tree with $n$ nodes must have exactly $n - 1$ edges. I have researched the solution but I haven't founded yet. I know of course, a tree with n ...
0
votes
1answer
39 views

prove by mathematical induction

I've been trying to solve this but I'm having trouble in simplifying it, in order to match the right hand side. Could you solve this? $$\sum_{i=1}^{n+1} i\cdot 2^i = n\cdot 2^{n+2} +2 ,$$ for all ...
1
vote
4answers
68 views

Solve $3x \equiv 17 \pmod{2014}$

Solve $$3x \equiv 17 \pmod{2014}$$ So first I suppose $3^{-1} \pmod{2014}$ $2014 = 671(3) + 1 \implies 1 = 2014 - 671(3)$ But this gives $3^{-1} = 1 \pmod{2014}$ which is incorrect?
0
votes
2answers
35 views

Show that $R=\lbrace (a,b): 5\mid(a^2-b^2) \rbrace$ is an equivalence relation

How can I show that this is an equivalence relation ? $$R=\lbrace (a,b): 5\mid(a^2-b^2) \rbrace$$
0
votes
1answer
11 views

how many reflexive relations but not equivalence, are in a set with 4 elements?

I know that for reflexive relations on a set with n elements the formula is: $2^{(n^2-n)}$ So for a set with $4$ elements: $2^{(4^2-4)}$ = $2^{12}$ But I don't know how to find the relations that ...
0
votes
1answer
21 views

Which are the equivalence classes for the following relation?

Here I have such an exercises related to equivalence relations. Given R defined on $Z \times Z$, $$(a,b)R(c,d)$$ and $$a+d=b+c$$ Let set $A$ be: $$A=\lbrace{0,1,2} \rbrace$$ Which are the ...
0
votes
2answers
51 views

Can someone verify my assertion from this english sentence? [duplicate]

This is from Discrete Mathematics and its Applications This is the book means when mentions a list of common ways to express conditional statements After going through the list, I immediately ...
0
votes
1answer
29 views

how to prove $pr_i(\alpha \setminus \beta) \supseteq pr_i\alpha \setminus pr_i\beta$

For those who are not familiar with the syntax $pr_i \alpha = \{ pr_i(a,b) / a \alpha b \} \text{ for }\alpha \subseteq A \times B$ which is same as $\begin{cases} (x= pr_1 \alpha) \Leftrightarrow ...
0
votes
1answer
25 views

Need to prove that a conditional statement is a tautology

The conditional statement is $[(p \rightarrow q) \land (q \rightarrow r)] \rightarrow (p \rightarrow r)$ Here are the steps I took in an attempt to prove the above statement a tautology, but I ...
2
votes
4answers
53 views

Clarifying on how if p,q is logically equivalent to p only if q [duplicate]

Here is what my book says about the different ways implications are worded I am struggling with how "if p, then q" is logically equivalent to "p only if q" The example I came up with With "if ...
0
votes
1answer
28 views

How to tell the difference between interval and coordinate notation from context?

I am working on a practice problem with sets. (the answer key) At first I was confused by the notation Ai = (0,i), i is a natural number. I looked up the use of paranthesis and saw that they could ...
0
votes
2answers
33 views

discrete math simplify

Given P and Q are statements, and (P->Q) =(~P v Q) , write the following logical expression in its simplest form. Justify each of the steps by citing the logical rule used. (P ->Q ) -> Q This ...
1
vote
3answers
29 views

Finding sequence for generating function

I have the generating function $$F(x) = \frac{x^3}{1 - x^2}$$ and I need to determine the sequence generated by it. I know that the first non-zero term will be $x^3$, since that's the numerator. ...
2
votes
3answers
56 views

prove or disprove (discrete math)

This the question: Q: Prove or disprove the following statement. The difference of the square of any two consecutive integers is odd This is working step: let $m,m+1$ be 2 consective ...
5
votes
2answers
104 views

What is the general term of $a_{n+1}=\frac{2a_n-1}{5a_n-1} \ , \ \ a_1=1$?

I've struggled to solve this exercise $$a_{n+1}=\frac{2a_n-1}{5a_n-1}\ , \ \ a_1=1$$ $$b_{n+1}=(5a_n-1)b_n \ , \ \ b_1=1$$ Find $b_{\ 40}$ . $$$$ I thought 'taking inverse' will be ...
-1
votes
1answer
20 views

Find all the substrings of the string $aabaabb$

Find all the substrings of the string $aabaabb$ Can anyone give me tips to this question and the methods used to determine the substring? Thanks
1
vote
1answer
12 views

Why can a set of edges of a bipartite graph with maximum degree d be partitioned in d matchings ?

In Wikipedia I read this: 'If there is a perfect matching, then both the matching number and the edge cover number are |V| / 2.' http://en.wikipedia.org/wiki/Matching_%28graph_theory%29 Is this the ...
2
votes
1answer
37 views

How to adapt proof by contradiction showing that a sqrt(2) is irrational for sqrt(20)?

This example is from Discrete Math and its Applications I understand the steps the author is taking. First he assumes sqrt(2) is rational meaning that there exists integers a, and b such that ...
0
votes
3answers
12 views

Proving if $G$ has no cycles but by adding one edge between any two vertices will create a cycle then $G$ is a tree

Prove: if $G$ has no cycles but by adding one edge between any two vertices it will create a cycle then $G$ is a tree. Below is the definition we use for a tree. I don't see any way to connect ...
0
votes
1answer
26 views

Converting from Octal to Decimal.

I have the value $(3738)_8$ and I want to convert it to decimal. The answer i believe is $$(3 \times 8^3) + (7 \times 8^2)+ (3 \times 8^1) + (8 \times 8^0) = 2016$$. My question is that on some ...
5
votes
2answers
351 views

Prove that any set of 2015 numbers has a subset who's sum is divisible by 2015

I assume this is correct to any size set, not 2015 in particular... it's obviously true for 2. I know from pen and paper it's true for 3, and 4.... I understand that I should look at the reminders, ...
1
vote
0answers
15 views

Should this be rephrased into saying no common factors but 1?

This is from Discrete Mathematics and its Applications For the phrase "a and b have no common factors" , does that actually mean a and b have no common factors other than 1? I feel like this would ...
0
votes
0answers
16 views

Is it necessary to write out the whole truth table to show system specification is consistent?

This is an example from Discrete Mathematics and its Applications Basically the way I see this problem is "is there a combination of propositions that will make all of these specifications true". ...
2
votes
1answer
25 views

Proving lattice distributive property - discrete math [on hold]

I'm studying discrete math. I'm stuck on this question. Thank you for solution. I don't have any idea to solve it. ...
0
votes
3answers
30 views

Binomial coefficient problem

I still haven't quite realized how to solve binomial coefficient problems like this, can someone show me an elaborated way of solving this? I need to write this expression in a more simplified way: ...
0
votes
2answers
19 views

How many relations can be defined the this power set

Let $A=\{1,2,3\}$ What is the number of reflexive relations the can be defined on $P(A)$? I first thought the number is 3, but it seems I'm wrong. How can someone solve this problem? Thanks
0
votes
1answer
27 views

Let $G$ be a connected graph, then $G$ is a tree iff $G$ has no cycles

Prove the following: Let $G$ be a connected graph, then $G$ is a tree $\iff$ $G$ has no cycles. $\Rightarrow$ If $G$ is connected and a tree then by the definition of tree it has no cycles. ...
0
votes
0answers
32 views

Use rules of inferential logic for the following problem..

Here I have such a question related to laws of inference. The question asks to prove using the laws of inference (these rules) that the following facts give a certain conclusion. So the question is: ...
0
votes
1answer
43 views

polynomial equation solve in full numbers

$x^2+x+41=y^2$ <--solve that in full numbers. I get to that point $(y-sq(x))(y+sq(x)))=x+41$ which imo must be false because this implies that $sq(x)^2$ is equal to $-x$ did I make a mistake ...
0
votes
1answer
22 views

Combinatorial Challenge, alternative solution process.

Problem: "During an election campaign $n$ different kinds of promises are made by the various political parties, $n>0$. No two parties have exactly the same set of promises. While several ...
3
votes
2answers
52 views

Prove that $7n^2 + 2n + 3 = O(n^2)$ using the definition of O notation.

Prove that $7n^2 + 2n + 3 = O(n^2)$ using the definition of O notation. I need to use two constants and prove that they satisfy the O definition. I'm new to big O and want to know whether I am ...
1
vote
2answers
39 views

Propositional Logic : Absorption - Why is it so?

Why is the Absorption Law of Propositional Logic so ? p $\lor (p \land q) \equiv$ p Would appreciate an intuitive explanation and not one using a Truth Table
0
votes
2answers
20 views

Prove that if $s \to r$ , $(p \lor q) \to \lnot r $,…, then the conclusion is $q$

How do I prove the following statement. If: $s \to r$ $(p \lor q) \to \neg r$ $\neg s \to (\neg q \to r)$ $p$ Then the conclusion is $q$ After several transformations I've obtained $\neg q \to ...
0
votes
1answer
21 views

The sequence T is defined by $T_n = n! + 2, n \geq 1$

For the sequence $T$ defined by $T_n = n! + 2, n \geq 1$ Question: Is $T$ increasing? Please provide your comments on if this is correct. Thanks. Let n = 1 $$T_1 = 1 \cdot 1 + 2 = 3$$ $$T_2 = 2 ...
-2
votes
1answer
23 views

Recurrence relations and initial conditions [on hold]

I couldn't figure out how to do the super/subscript, hence the photo.
1
vote
2answers
28 views

Changing the state of coins and finding the minimum number of steps to do it

I have $N$ coins all showing heads. At each turn, I change the state (i.e., a head is changed to a tail, vice versa) of $N-1$ coins. Prove that all the coins can end up showing tails if and only if ...
1
vote
2answers
27 views

Discrete math functions proof

Let $\mathbb N_{\text{even}}$ be the set of all natural even numbers, and $\mathbb N_{\text{odd}}$ be the set of all natural odd numbers, the function $f:\mathcal P(\mathbb N)\to \mathcal P(\mathbb ...
0
votes
1answer
31 views

Simplification of Boolean Algebra

$$F = (w,x,y,z)= (xy'z) + (wxy'z') + (wxy) + (w'x'y'z') + (w'x'yz')$$ I need to simplify this equation as much as possible, using Boolean identities. The prime($'$) represents the negation of the ...
0
votes
1answer
20 views

Next step to show that these matrice expressions are equal?

This is a problem from Discrete Mathematics and its Applications I know invertible means it is possible to take the inverse of this matrix. This is definition of a power of a square matrix from my ...