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
2answers
22 views

Let $B = {n \in \mathbb{Z} : n = 3j + 2; j \in \mathbb{Z}}, D = {n \in Z : n = 3j − 1; j \in \mathbb{Z}}$. Is $B = D$?

Let $B = {n \in \mathbb{Z} : n = 3j + 2; j \in \mathbb{Z}}, D = {n \in Z : n = 3j − 1; j \in \mathbb{Z}}$. Is $B = D$? How do I prove this? To me it looks to be true. But I don't know how to put it ...
0
votes
0answers
32 views

Definition of fixed point free relation

If we have such relation that for $\forall x$ $f(x)\ne x$ , how is it called in one word? I can come up with only "graph of this function is not a straight line:)" Thank you
-5
votes
2answers
46 views

Given any 40 people, at least four of them were born in the same month of the year

Given any 40 people, at least four of them were born in the same month of the year. Why is this true?
-1
votes
1answer
18 views

binary relation prove

im studying for a test and theres are some questions that ive tried and i dont understand. A) $E$ is a binary relation on group $A$. binary realation $F$ is on group $P(A)$ \ $\{\phi\}$ as: ...
1
vote
1answer
20 views

Write expressions w/out quantifiers (convert to AND/OR expressions)

A universe contains the three individuals $a,b$, and $c$. For these individuals, a predicate $Q(x,y)$ is define, and its truth values are given by the following table \begin{array}{c|ccc} ...
0
votes
1answer
19 views

How to prove that $(A \cup B) - C = (A - C) \cap (B - C)$ [on hold]

If true, prove else provide a counter example. This is a homework question and I cant figure it out. Please help.
-1
votes
2answers
36 views

Discrete math, proving sets [on hold]

I am studying discrete math and i stumbled upon a proof i couldnt proove, can someone help me with this one? "Assume that A,B,C are three sets with no elements in all three sets. Assume further that ...
1
vote
0answers
25 views

Mean distance of random points on a rectangular grid

I have a $N\times N$ grid of side $L$. Each gridpoint can be black or white and a ratio $r$ of the points is black. I want to predict the mean distance between two black points. The most appropriate ...
0
votes
1answer
35 views

Can someone explain and help me with propositional logic in discrete math?

Can someone explain to me in detail how to complete these two problems without using truth tables? I'm having a hard time understanding what to do. I know that I'm supposed to use the laws, etc. But ...
4
votes
2answers
61 views

Finding limit via Sandwich Theorem: $\lim_{n\to\infty} n\sum_{n+1}^{2n} \frac{1}{i^2}$

Question: Use the Sandwich Theorem to find $$\lim_{n\to ∞} n\sum_{n+1}^{2n} \frac{1}{i^2}$$ Appreciate any guidance.
0
votes
5answers
62 views

Summation for $\sum\limits^5_{i=2}\:\left(3i\:-\:5\right)$

I know that the closed form of $\sum\limits^n_{k=1}\:k=\frac{n(n+1)}{2}$ But I'm not sure what the closed form for $\sum\limits^5_{i=2}\:\left(3i\:-\:5\right)$ would be. Any push in the right ...
1
vote
2answers
32 views

Simple expression for $\sum_{k=1}^{n-1}\:\frac{1}{k\left(k+1\right)}$

I know that $\:\:\frac{1}{k\left(k+1\right)}\:\:\:\:=\:\frac{1}{k}\:-\:\frac{1}{k+1}\:$ And that $\sum_{k=1}^{n-1}\:k$ $= \frac{n(n-1)}{2}$ But I'm not completely sure how to turn ...
-1
votes
2answers
22 views

How can I further simplify $(B^c ∩ (B ∩ A)^c)^c$

I'm pretty sure this is equal to B, but I'm not sure how to go about reducing this step by step. Could I use the double negative law to eliminate the complements? I'm not positive if that would work ...
0
votes
3answers
21 views

Finding the complement of a set

I have the sets A, B, and C: $A = \{x\in\mathbb{Z} | 2 < x < 5\}$ $B = \{x\in\mathbb{Z} | 4 ≤ x ≤ 7\}$ $C = \{x\in\mathbb{Z} | 2 ≤x< 6\}$ What is $B ∩ C^c$? If the complement of C is all ...
0
votes
1answer
8 views

Finding the smallest exponent $k$ for a non-cyclic permutation $\sigma$, so that $\sigma^k = id$.

What I am aware of (1) A cyclic permutation is a permutation that consists of a single nontrivial cycle (cycle of length $> 1$). Let $k$ be the length of the cyclic permutation $\tau$. Therefore ...
1
vote
1answer
33 views

Why is this predicate false?

I am stumped at my professor's answer to this predicate logic. all x and y are natural numbers. ∃y∃x(x >= y) I think it is true, since there is a pair ...
2
votes
2answers
42 views

Prove by contradiction Irrational number

I Need to prove this by contradiction : If $a$ is Irrational then $\frac{2a-3}{2a+3}$ is Irrational. I did: Iff $p$ is Irrational, then $\frac{2a-3}{2a+3}$ is Rational and a Rational number can ...
-4
votes
1answer
68 views

Difficuly in proving inequality [on hold]

I have trouble solving this inequality can some one please give solution to this? $$\left( n+\frac{1}{n} \right) ^{n+1} > e$$
7
votes
9answers
2k views

What do we actually prove using induction theorem?

Here is the picture of the page of the book, I am reading: $$P_k: \qquad 1+3+5+\dots+(2k-1)=k^2$$ Now we want to show that this assumption implies that $P_{k+1}$ is also a true statement: ...
0
votes
2answers
57 views

How do I calculate $\sum_{k=1}^{33}\binom{33}{k} k$

I started studying about binom's and sums, How do I calculate $$\sum_{k=0}^{33}\binom{33}{k} k$$ Note: I do know that it is $\binom{33}0\cdot0 + \binom{33}1 \cdot 1 + ... + \binom{33}{33} \cdot 33$, ...
0
votes
1answer
15 views

Chance of drawing 4 red marbles out of a big bag.

In a bag with an infinite number of marbles, where a third are red, a third are green and a third are blue. Given that you pick $10$ marbles, of which $3$ are blue, what are the chances of picking $4$ ...
-1
votes
5answers
73 views

Is it accurate to say that multiplication of two integers yields an integer?

I am reading a book in discrete mathematics and it assumes that a multiplication of two integers yields an integer. Although that this book's saying is justifiable since the book is making an ...
-1
votes
1answer
27 views

If $A⊆B∪C$ and $B⊆A∩C$, then disprove that $A≠B$ [on hold]

If $A⊆B∪C$ and $B⊆A∩C$, then disprove that $A≠B$ Need really quick help on this. I am really stuck on this, and I have a quiz on it tomorrow morning. Please help!
-1
votes
0answers
23 views

How many different ways can $6$ chocolate bars be selected in such a way that each type is chosen at least once? [on hold]

In a shop five different type of chocolates are sold. How many different ways can $6$ chocolate bars be selected in such a way that each type is chosen at least once? I know the answer is $5$. ...
-3
votes
1answer
13 views

Proving or disproving set statements. [on hold]

I'm not sure how to approach proving or disproving these statements. I don't know where to begin, or more specifically, what it's asking me to prove or disprove. If $ A \cap B \subseteq C$ and $A ...
1
vote
7answers
65 views

Proving $\frac{n}{n+1} < \frac{n+1}{n+2}$ by induction?

I have the inequality $\frac{n}{n+1} < \frac{n+1}{n+2}$ I'm not sure how to go about proving it. I've started by testing with n = 1, which results in $\frac{1}{2} < \frac{2}{3}$ which is true ...
0
votes
1answer
28 views

How can i find equation that does not have a solution?

An operation $*$ is defined on the set $\Bbb{Z} \times \Bbb{Z}$, ie. the set containing all pairs of integers by: $$ (u,v) * (x,y)=(u+x,v \cdot y) $$ if $(\Bbb{Z} \times \Bbb{Z}, *)$ is not a group ...
1
vote
1answer
37 views

Discrete math: What is the difference between false and inverse in conditional statemensts?

Let's say there is this conditional statement: If I am in Paris, then I am in France. So, p = 'I am in Paris', and q = 'I am in France' I do not understand when p and q are false, how would that ...
0
votes
0answers
13 views

$∀ Z^+$ can be written as $c_r * 3^r + c_{r-1} * 3^{r-1} + …. + c_2 * 3^2 + c_1 * 3 + c_0$

I am trying to prove the following statement: $∀ Z^+$ can be written as $c_r * 3^r + c_{r-1} * 3^{r-1} + …. + c_2 * 3^2 + c_1 * 3 + c_0$ where $c_r =$ 1 or 2, and $c_i$ = 0, 1, or 2 for all integers ...
0
votes
1answer
35 views

Any collection of n coins can be obtained using a combination of 3¢ and 5¢ coins where n ≥ 14

I am trying to prove this statement with strong induction, but I'm a little lost on the inductive step. Proposition: Let P(n) be the sentence ‘any collection of n coins can be obtained using a ...
1
vote
2answers
35 views

Recall that $ p \rightarrow \sim q$ is equivalent to $p \land \sim q$, how can this be used as an explanation for how to use proof by contradiction.

Recall that $p \rightarrow \sim q$ is equivalent to $p \land \sim q$, how can this equivalence be used as an explanation for how to use proof by contradiction. I'm having a hard time answering this ...
0
votes
1answer
12 views

How to solve a parameteric linear equation in Zn?

Given monoid ($\Bbb{Z}$124, ⋅ ) and a parametric equation with parameter $a$ where $ax+2=5(x+a)-1$ Give the number of parameters $a$ belong $\Bbb{Z}$124 for which the above equation has precisely ...
1
vote
3answers
52 views

How to prove that $A⊆B$ means that $A∪B=B$ [duplicate]

How does one prove that $A⊆B$ means that $A∪B=B$ ? I can understand it in my head but I don't know how you'd put down in logic notation.
0
votes
1answer
18 views

convert Hex value to two's Complement

for example, let's say: 0xE5 assume the system is 8 -bit in decimal it's = 229 and in Binary it's = 1110 0101 the Two's Complement rules said: sign-bit, which's the most left, indicates a negative ...
1
vote
1answer
28 views

Rewrite the following in symbolic forms using $\sim, \land, \lor $.

Let $h = $"Peter is handsome", $c = $"Peter is clever", $o = $"Peter is optimistic". Rewrite the following in symbolic forms using $ \sim , \land, \lor $. -Peter is neither handsome, clever nor ...
1
vote
1answer
21 views

How can I show that an argument or proposition is valid through logic proof sequence?

I know the logic of proof sequence as I solved many proof problems, I now have one that has been taken my attention for a couple of days and as easy as it may look, I don't seem able to simplify the ...
0
votes
1answer
27 views

Prove that $\sum_{i=0}^{k} \lg \frac{n}{2^i} = \Theta(\lg^2 n)$

Show that if $n$ is a power of $2$, say $n = 2^k$, then we have the equality $\sum_{i=0}^{k} \lg \frac{n}{2^i} = \Theta(\lg^2 n)$. The first step is to prove $O(\lg^2n)$: $$ \lg \frac{2^k}{2^0} + \lg ...
1
vote
1answer
23 views

How can i find all invertible elements?

An operation $*$ is defined on the set $\Bbb{Z} \times \Bbb{Z}$, ie. the set containing all pairs of integers by: $$ (u,v) * (x,y)=(u+x,v \cdot y) $$ What are all the invertible elements of the ...
0
votes
0answers
23 views

Can you show a proof of Unique Factorization of Integers Theorem (Fundamental Theorem of Arithmetic)?

I understand the proof of "Any integer greater than 1 is divisible by a prime number" by strong mathematical induction. But I don't understand why Unique Factorization of Integers Theorem follows ...
2
votes
3answers
145 views

Can the cardinality of a power set ever be odd? [on hold]

Can the cardinality of a power set ever be odd? If it can, what conditions must be met?
0
votes
0answers
26 views

Integral solution of equation $Ax + By = z$ with contraints on $x, y, z$

Given $x$, $y$ and $z$, how can I check if there exists integral solution of $$Ax + By = z$$ Such that : if $x > y$, $A$ must be positive and $z \geq y$ ( Given ) if $y > x$, $B$ must be ...
0
votes
0answers
94 views

Find number of rectangles

There is $N\times M$ grid present with numbering as $1,2,\cdots,NM$ (numbering is done row wise. 1st row will contain number from $1,\cdots,M$, second row will contain $M+1,\cdots,2M$ and so on). ...
1
vote
4answers
70 views

If $a > 0$,$b>0$, and $\frac{1}{a} + \frac{1}{b}$ is an integer, prove that $a=b$. And show that $a = 1$ or $2$

If $a$ and $b$ are positive integers, and $\frac{1}{a} + \frac{1}{b}$ is an integer, prove that $a=b$. And show that $a = 1$ or $2$ -I played around with numbers and the conditions and it seems that ...
1
vote
1answer
40 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 ...
3
votes
3answers
41 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
41 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 ...
4
votes
2answers
35 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
15 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
35 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 ...
-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 ...