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
vote
1answer
24 views

Am I right in this discrete mathematics question?

$A = \{0, 1, 2\}$ $B = \{x \in R\mid−1 \le x \lt 3\}$ $C = \{x \in R\mid−1 \lt x \lt 3\}$ $D = \{x \in Z\mid−1 \lt x \lt 3\}$ $E = \{x \in Z+ \mid−1 \lt x \lt 3\}$ I put that $A=D$, $A=C$, and ...
0
votes
1answer
15 views

How does simplification work when solving linear combinations?

So I'm currently trying to wrap my head around finding gcd through the Euclidean Algorithm in order to write the integers as a linear combination. For example, a problem is to express the ...
0
votes
0answers
25 views

Translating English to symbolic logic

(Question prompt) The domain of discourse in this problem is the set of students and teachers at a school. Define the following predicates: • E(x, y): x has sent a letter to y. • P(x): x is a ...
0
votes
0answers
14 views

Baby-step Giant-Step algorithm to calculate value in new base

Using the Baby step–giant step algorithm I am trying to determine $log_{2}(7)$ in base $1$3. Let $p = 7$. Set $n$ to the least integer greater than $\sqrt p$: $n = 3$. So for baby step, I started off ...
2
votes
3answers
34 views

Determining if a relation is reflexive, symmetric, or transitive [on hold]

Let $A = \{0,1,2,3\}$ Define a relation $T$ on $A$ as follows: $T = \{(0,1),(2,3)\}$ Is $T$ reflexive? symmetric? transitive?
1
vote
1answer
12 views

Discrete Structures: Trying Correcting my Predicate Logic with the appropriate quantifiers

I am trying to correctly use predicate symbols and using the appropriate quantifiers were I have to write each English language statement in predicate logic and the domain is the whole word. $P(x)$ ...
1
vote
1answer
18 views

Solving recurrence relations with two variables

whenever I've had to solve recurrence relations, I've kind of just messed around with it until it works. I have a more complicated case, and I was wondering if there are general strategies someone ...
0
votes
3answers
18 views

Finding the equivalence classes of a relation R

Let A = {0,1,2,3,4} and define a relation R on A as follows: R = {{0,0},{0,4},{1,1},{1,3},{2,2},{3,1},{3,3},{4,0},{4,4}}. Find the distinct equivalence classes of R. How do I solve this problem? ...
2
votes
3answers
40 views

Show the closed form of the sum $\sum_{i=0}^{n-1} i x^i$ [duplicate]

Can anybody help me to show that when $x\neq 1$ $$\large \sum_{i=0}^{n-1} i\, x^i = \frac{1-n\, x^{n-1}+(n-1)\,x^n}{(1-x)^2}$$
-1
votes
0answers
15 views

What will be the negation of the following proposition number (iii)? [on hold]

I want to know the method for solving part iii of this question.. Someone please help me !
1
vote
0answers
22 views

Interesting Graph Theory “WOMVIES” problem

Here is an interesting problem: A graph is a set of vertices (points), some pairs of which are joined by an edge. For this problem, we will not allow an edge to join a vertex to itself (i.e., no ...
0
votes
1answer
19 views

Proving Equivalence Relations On A Set

Let X be the set of all nonempty subsets of {1,2,3}. Then X = {{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}} Define a relation R on X as follows: for all S and T in X, SRT if, and only if, the least ...
2
votes
2answers
20 views

Counting and solving bijection

Given the problem: Please count how many functions $f : D → \{0, 1 \}$ can be defined if the domain D is a finite set with the cardinality $|D| = n$. Is there a bijection between the set of all such ...
0
votes
0answers
15 views
0
votes
2answers
26 views

binary relations

I am having a hard time understanding some things dealing with these relations. The five relations we are dealing with are reflexive, symmetric, transitive, irreflexive, and antisymmetric. $R$ is ...
-1
votes
1answer
12 views

Determine which of these are strongly connected. Explain why or why not. [on hold]

I'm not sure how to determine this.. Is there a certain formula?
1
vote
2answers
8 views

Given a complete graph of n vertices Kn (has all possible edges – one edge between pair of vertices).

Given a complete graph of n vertices $K_n$ (has all possible edges – one edge between pair of vertices). Use counting to find a formula in $n$ for the number of edges in the graph. I know that the ...
2
votes
1answer
33 views

Find closed form formula

I need help to find closed form formula for this summation $$\sum_{i=0}^{\infty}(x-y)^i$$
0
votes
0answers
11 views

(a) Given the graph below, for each pair of vertices given in (i) and (ii) gi

so I think I've figured out part a) but I'm not sure.. my solution is: a) part i) $v_1 \rightarrow v_3 \rightarrow v_7 \rightarrow v_5 \rightarrow v_8 \rightarrow v_4 \rightarrow v_2 \rightarrow ...
1
vote
1answer
12 views

One hypothesis concerning Hamming distance matrix

Suppose $a_1, a_2, \ldots, a_m$ are different strings of the same length n. And let $V = [v_1, v_2, \ldots, v_n]$ be a matrix such that $V_{i, j}$ is a Hamming distance between $a_i$ and $a_j$. ...
1
vote
2answers
46 views

Discrete Math: Implication

If $\neg(P) \to \neg(Q) = Q \to P$ works as a Rule, then why doesn't $\neg(P) \to \neg(Q) = P \to Q$ work as a rule.
1
vote
1answer
14 views

Graphing digraphs with the following vertex set

Just want to make sure I did this correctly.. I think I did part a) correctly? Here is my solution for part a) Not sure how to do b) and c) though. Any advice would be great. Thanks in advance
1
vote
1answer
17 views

Proof of cardinalities sets

Prove that the cardinality of set $A^{B+C}$ is equal to the cardinality of $A^{B}\times A^{C}$. I think I need to make functions from $B+C$ to $A$ and one from $B$ to $A$ and one from $A$ to $C$. I ...
0
votes
1answer
19 views

Converting a regular language to a deterministic machine.

How does on go about converting a regular language to a deterministic machine? What are the steps involved. The language I'm working with is as follows: $$(00000 + 0111 + 100)^* (0 + 1)$$ I'd rather ...
0
votes
0answers
39 views

Does the graph exist with these degrees?

$(11,2,2,2,2,2,2,2,1)$ Is it possible that a degree of a vertex can be 11 ? However, there are only 9 vertices. Does the graph exist?
0
votes
2answers
18 views

Prove the inclusion-exclusion formula

We just touched upon the inclusion-exclusion formula and I am confused on how to prove this: $|A ∪ B ∪ C| =|A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|$ We are given this hint: To do ...
0
votes
1answer
23 views

context-free languages operation closure

The following operation is defined on formal languages. $ operation1(L) = \lbrace w \ | \ wxy \in L, \ \forall x \forall y \ (|x|=|w|) \ \wedge (|y| = |w| ) \rbrace $ Prove that context-free ...
1
vote
0answers
53 views

Deduction method with a quantified statement

In this expression I am trying to prove is a valid argument using the deduction method that is using equivalences and rules of inference in a proof sequence. ...
0
votes
1answer
44 views

Closed form for the summation [on hold]

Can anyone help me to find what is closed form formula for this summation formula $$\sum\limits_{n=0}^mx^n\sum\limits_{i=0}^ny^i$$
0
votes
0answers
27 views

How to solve this discrete question? [on hold]

Newbie to discrete math. Ask for how to start up. Thanks a lot.
-2
votes
1answer
22 views

Discrete Math Lattice Points [on hold]

I'm not sure how to start this problem but I think this has to do with the Inclusion-Exclusion Principle. Please help. Thank you
-3
votes
1answer
20 views

Discrete Mathematics linear recurrence [on hold]

Prove the summation formula using induction: $$\sum_{k=1}^{n} \frac{1}{k(k+1)}=1-\frac{1}{n+1}$$
0
votes
1answer
36 views

Discrete Mathematics Fibonacci Sequence

I am studying for the final exam in my Discrete Mathematics class and came upon the following problem on the study guide we were given. Given the following algorithm: If $n = 0$, then $f(n) = 0$ ...
0
votes
1answer
14 views

General solution to discrete dynamical system.

I am trying to find the general solution to the following discrete dynamical system: $$H(n+1) = 0.89H(n) + 30$$ $$E(n+1) = 0.64E(n) + 0.11H(n)$$ $$o(n+1) = 0.88o(n) + 0.36E(n) + 30$$ $H(0) = 3500$ ...
0
votes
1answer
30 views

What is the walk of this graph?

A walk that is not a trail from vertex 1 to vertex 3; A trail that is not a path from vertex 1 to vertex 3; A path from vertex 1 to vertex 3. How can I describe these walks?
0
votes
3answers
49 views

Proof By Induction $2^n \ge n^2$ for $n\ge4$

I am trying to prove the following, and here is what I have done: Can somebody help to complete this? $2^n \ge n^2$ for $n\ge 4$ $n=4$, LHS: $2^4 = 16$, RHS: $4^2=16$, $16=16$ Therefore TRUE Assume ...
0
votes
1answer
12 views

Solving Through The Use Of Handshakes.

Let $G$ be a graph. Use the Handshake Theorem to prove that $\delta(G)\nu(G) \le 2\varepsilon(G) \le \Delta(G)\nu(G)$. So the first step to solve this I know is that you need to know what ...
1
vote
2answers
17 views

Proof DES is injective - is this a valid argument

Without going too much into detail into the crpytography of the matter since not every mathematician is interested or knowledgable in the field, there is an encryption process called DES (data ...
0
votes
1answer
15 views

Prove multivariable function is surjective?

I am a little confused on how to prove a multivariable function is surjective(onto). The function is $f: \mathbb N^2 \to \mathbb N$ such that $f(a,b) = a^b$ I tried thinking of a counter example but ...
1
vote
0answers
35 views

about complement of a graph

Let $G$ be a $k-$regular graph on $n$ vertices. we know that if $k\geq n/2$, then $G$ is a connected graph. Now, if we take complement of graph $G$ and denote it as $\bar G$ then $\bar G$ will be ...
-3
votes
2answers
33 views

List the elements of a set [on hold]

Consider the universal set $N$, $$A = \{m: m\ |\ 16\}$$ and $$B = \{n: n \le 16 \text{ and } n \equiv 17 \mod 3\}.$$ List the elements of A, list the elements of B.
2
votes
2answers
31 views

Proof By Induction $n^2 > 3n$ where $n\ge 4$

I am trying to prove the following example, however I seem to be getting a little stuck: For $n\in\mathbb N$, $n\ge 4, n^2>3n$ What I have Done: Base Case:$ n=4$, LHS: $4^2 = 16$, RHS: $3\cdot 4 ...
0
votes
0answers
11 views

Fast Fourier Transform Splitting Algorithm

I'm trying to figure out how the FFT splitting algorithm works. I've pretty much understood the general idea, but when I try to compute it, I get something completely different than what I expect $ ...
1
vote
1answer
40 views

Proving a property about modulus

I seem to be having a lot of trouble finding a place to start in proving that $$(a \cdot b) \mod m = ((a \mod m) \cdot (b \mod m)) \mod m$$ Any ideas on how I should go about doing this? I've been ...
0
votes
1answer
39 views

I am trying to use proof of sequence correctly to make valid

Here I am trying to use a proof sequence so that the argument is valid (hint: the last A’ has to be inferred). (A → C) ∧ (C → B') ∧ B → A' Here are my steps I tried but not sure if this is correct ...
0
votes
0answers
42 views

Trying to justify each step correctly in proof sequence

I am trying Justify each step in the proof sequence below for correctly with [A → (B ∨ C)] ∧ B' ∧ C' → A' So I justified my steps here but I am not sure at 1 to 3 if I did it correctly. A → (B ∨ ...
0
votes
1answer
48 views

Gauss Method to show [on hold]

Could you please give me the way to solve this problem Using Gauss method to show if $x ≠ y + 1$ then $$ \sum_{i=0}^n (x-y)^i = \frac{(x-y)^{n+1}-1}{x-y-1}. $$
1
vote
1answer
25 views

Symbol clarification

Okay, so I've read a few different meanings for the exclamation point in a statement. For example: $$!\exists x \in O \ni 2x < 5$$ The only question I have is about the Exclamation point in front ...
1
vote
1answer
15 views

What would the expected number of swaps in a merge sort be?

If I were given a list of random numbers say x1, x2, .........., xn and these numbers are sorted according to the merge sort algorithm. What would be the number of expected swaps/exchanges which would ...
0
votes
1answer
48 views

solving a recurrence without initial conditions

I have been working on this problem for two days... I can only get as the characteristic part of the recurrence, I just can't figure out a proper guess for the particular solution. ...