Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

1
vote
2answers
199 views

Trouble determining whether relations are reflexive, symmetric and transitive.

I'm having trouble understanding whether or not relations are reflexive, symmetric and transitive. I know that for a relation to be any of those it must satisfy the conditions: reflexive: for every ...
1
vote
1answer
38 views

I was trying to compute $\sum_{j=0}^{m} 3^j {m \choose j}$, but don't know where to start

compute $\sum_{j=0}^{m} 3^j {m \choose j}$. Then, use the binomial theorem to verify the result.
2
votes
1answer
70 views

Is this function one-to-one, onto, both or not a function?

$P(N) \times P(N) \to P(N)$ defined by $f(A,B)=A \cup B$. Answer: I gave a counterexample for one-to-one because if $A=\{\{\},\{1,2\},\{1\},\{2\}\}$ and $B=\{\{\},\{2\},\{3\},\{2,3\}\}$ then $A \cup ...
2
votes
1answer
129 views

Proving a Property of a Set of Positive Integers

I have a question as such: A set $\{a_1, \ldots , a_n \}$ of positive integers is nice iff there are no non-trivial (i.e. those in which at least one component is different from $0$) solutions ...
0
votes
2answers
37 views

Show that $(\phi_{n}^{(n)})^{-1}= -(\sum_{i=0}^{n-1}(\phi_{i}^{(n)})^{-1})$

So I have $n+1$ points $x_{0},x_{1},...,x_{n} \in \mathbb{R}$ and a following quasi-function: $\phi_{j}^{(n)}=\prod_{i=0,i \neq j}^{n}(x_{j}-x_{i})$ Show that $(\phi_{n}^{(n)})^{-1}= ...
0
votes
1answer
75 views

Compute C1, C2, C3, C4, C5

I have a question C1 = 0, C$n$ = C$\lfloor n /2\rfloor$ + $n^2$ for all $n > 1$ Compute C1, C2, C3, C4 So what I did is: C2 = C$\lfloor 2/2\rfloor + 2^2$ = 1 + 4 = 5 -- but that is wrong ...
1
vote
1answer
55 views

Strong explanation of Strong Form of Mathematical Induction

I don't quite understand induction well, and was wondering if you could explain to me what induction is and what the strong form of induction is.
0
votes
0answers
25 views

Discrete Math Equation Proof (by induction?) [duplicate]

Consider the following description of a game. There are n people playing, one of whom leads the game. They are playing on a playing field with no obstacles. Everyone carries one water balloon. ...
2
votes
1answer
84 views

Prove that every number between two factors of primes is composite.

I am looking for some help with this problem: Let p1, p2, ... , pn+1 be the first n+1 primes in order. Prove that every number between p1 * p2 * p3 ... pn + 1 and p1 * p2 * p3 * ... * pn+1 -1 is ...
0
votes
1answer
41 views

dependent or independent probability?

We have 80 professors: 25 engineers 15 computer science 35 math 5 stats What is Pc(D)=P(D|C), where the experiment is to choose 6 professors at random and ...
3
votes
2answers
186 views

Combinatorics help. Palindromic 6 letter sequences.

The genetic code can be viewed as a sequence of four letters T, A, G, and C. There were two parts to the question: (a) How many 6-letter sequences are there? I just said $\binom{4}{1}^6$, or ...
0
votes
2answers
240 views

creating binary search trees

Assume that your tree is constructed by inserting, from left to right, the values Q = {7; 6; 5; 4; 3; 2; 1} into the tree starting from an empty tree. I have to Give an array of Q that compels the ...
0
votes
1answer
86 views

Is this poset a lattice?

Given the set $\Bbb Z^+\times\Bbb Z^+$ and the relation $$\begin{align*} (x_1,x_2)\,R\,(y_1,y_2)\iff &(x_1+x_2 < y_1 + y_2)\\ &\text{ OR }(x_1 + x_2 = y_1 + y_2\text{ AND }x_1 \le y_1)\;: ...
0
votes
0answers
32 views

Need help with a Partitions question

For $m \in \mathbb{N}$, let $C_m = \{x \in R \mid m-1 \leq x^2 < m\}$. Is $\ell=\{C_m \mid m \in \mathbb{N}\}$ a partition of $\mathbb{R}$? If I understand it correctly, $C_m$ will always be a ...
4
votes
2answers
103 views

Prove $m=3k+1 \quad m,k \in \mathbb Z \implies m^2=3l+1 \quad m,l \in \mathbb Z$

Suppose we call an integer "throdd" $\iff$ $m=3k+1$ for some integer $k$. Prove that the square of any throdd integer is throdd. So here is what I have so far: $$(3k+1)^2 = 3k+1$$ ...
0
votes
2answers
40 views

For all integers $m$ and $n$

Prove or disprove: For all integers $m$ and $n$, if $m+n$ is even then so is $m-n$. Would you just set them even to each other because you are given $m+n$ is even?
0
votes
1answer
70 views

Clarification on proof by contradiction in a directed graph

Let's say that I have a finite directed graph. Also assume that every vertex in the graph has only one unique closest neighbor. How can I prove that the maximum length of any cycle in this graph is 2? ...
0
votes
1answer
106 views

conditional probability of dependent events

I posted another question earlier but i can't modify it so please bare with me. I have a problem where i need to find it's conditional probability: probability of Pc(B)=(B|C) where the event of B={no ...
2
votes
2answers
178 views

basic induction probs

Hello guys I have this problem which has been really bugging me. And it goes as follows: Using induction, we want to prove that all human beings have the same hair colour. Let S(n) be the ...
-3
votes
2answers
43 views

Product of three integers [closed]

Prove or disprove the conjecture: if the product of three integers is divisible by 3 then the integers are consecutive. Counter ex. Suppose a, b, c are PBAC integers. a=2 b=10 c=30 abc=600 2, 10, ...
1
vote
1answer
86 views

A simple floor inequality proof

If $x,y ∈\Bbb R$, I have problems to show that $$⌊x+y⌋-1 ≤ ⌊x⌋+⌊y⌋ ≤ ⌊x+y⌋$$ Can someone help me?
0
votes
1answer
71 views

conditional probability with independent and non independent events

I need to clear up some confusion on conditional probability and independence. Two events are said to be independent if the probability of two events equal their product. So $$P(B\mid ...
2
votes
1answer
36 views

Arranging Prime Factors to form Integer Solutions

I have a problem as such: How many solutions in positive integers are there to the equation $x_1 \cdot x_2 \cdot x_3 \cdot x_4 = 2^{20} \cdot 13^{13}$? Let $x_1,\ldots,x_4$ all be distinguishable, ...
2
votes
2answers
227 views

Fermat's 2 Square-Like Results from Minkowski Lattice Proofs

Minkowski's Convex Body Theorem for lattices in the plane: Suppose $\mathfrak{L}$ is a lattice in $\mathbf{R}^2$ defined as $\mathfrak{L}=\{m\vec{v_1}+n\vec{v_2}:m,n\in\mathbf{Z}\}$, where ...
2
votes
1answer
67 views

Prove a sum of sequence: Discrete math and weak induction

The problem is as follows: Prove that $2 - (2\cdot7) + ((2\cdot7)^2) - ... +(2(-7))^n = > \frac{(1-(-7)^{(n+1)})}{4}$ whenever $n$ is a non-negative integer. Our book is asking for a basic ...
2
votes
2answers
59 views

Why $p \leftrightarrow q$ is equivalent to $(p \wedge q) \vee (\neg p \wedge \neg q)$? Without using the truth table

I want to know why $p \leftrightarrow q$ is equivalent to $(p \wedge q) \vee (\neg p \wedge \neg q)$? Without using the truth table. Thanks all
2
votes
2answers
617 views

How to find the LCM of One Negative and one positive Integer

The title pretty much explains my question. While studying theory of numbers I came across this problem. The way I did LCM in childhood gave me a negative result.Maybe the method I used is wrong. But ...
1
vote
1answer
41 views

Help me solve this equation: $A-B = A- (A\cap B)$ [closed]

There're 2 sets A and B. Prove, that: $$ A \setminus B = A \setminus (A \cap B) $$
0
votes
1answer
91 views

How to prove this just by using Natural Deduction?

I need your help to prove this by using Natural Deduction: $$(\exists x)(p(x) \implies q) \dashv\vdash (\forall x)(p(x) \implies q).$$ I want to show the proof for both sides. It is a bit easy for ...
1
vote
1answer
220 views

How to prove these using natural deduction

I'd like to prove the following logical equivalence by using natural deduction: $$(\exists x)(p(x) \implies q) \dashv\vdash (\forall x)(p(x)) \implies q.$$ As far as I'm concerned to show that two ...
1
vote
1answer
33 views

How come when $2^{k} | (x-1)(x+1)$ one of the terms is divisible by $2$ and not by $4$ when $k \in \mathbb{N} $ and $3 \leq k$

So I'm reading Knuth's 'Discrete Mathematics' at the moment and there's a paragraph detailing how many solutions are there for $x^{2} \equiv 1 \pmod{p}$. So other cases (when $p$ is an odd prime or ...
0
votes
1answer
59 views

Does my logic statement make sense?

I'm trying to convert this sentence to logic notation. "there is an integer less than or equal to all other integers greater than 0". "An integer exists that is less than or equal to all other ...
0
votes
1answer
34 views

Proving antisymmetry for this partial ordered set

I need to prove the anti-symmetric property of the following relation (the set is the cross-product of all positive integers). (x1,x2) R (y1,y2) <=> EITHER (x1 + x2 < y1 + y2) OR (x1 + x2 = y1 ...
0
votes
1answer
37 views

Question about $a \equiv b \pmod{mn} \Leftrightarrow a \equiv b \pmod{m} \wedge a \equiv b \pmod{n}$

So Knuth's 'Discrete Mathematics' states that: $a \equiv b \pmod{mn} \Leftrightarrow a \equiv b \pmod{m} \wedge a \equiv b \pmod{n}$ if $m$ and $n$ are relatively prime. But being a curious human ...
0
votes
2answers
248 views

Proof by strong induction [closed]

Consider the sequence: $$a_0=1, a_1=2, a_2=3; \,\, a_k=a_{k-1}+a_{k-2}+a_{k-3}, \, k \geq 3,$$ and the statement $P(n):a_n \leq 2^n$. Prove $\forall \, n \in \mathbb{N}, \, P(n)$. ($\mathbb{N}$ ...
0
votes
2answers
58 views

regular expression for a number

It is a regular expression for a number. I have several questions about it. (0U1U2U3U4U5U6U7U8U9)* Does it means a set containing a number from 0 to 9 and then concatenate itself n times, or a ...
4
votes
2answers
169 views

If $n$ is squarefree, $k\ge 2$, then $\exists f\in\Bbb Z[x_1,\dots,x_k] : f(\overline x)\equiv 0\pmod n\iff \overline x\equiv \overline 0\pmod n$

Starting from this question, we set $n=k=2$ and use the function $f\in\Bbb Z[x,y]$ where $f(x,y)=x\cdot y+x+y$, then the proofs applied to that question satisfy this case. Note that for $k=1$ the ...
0
votes
1answer
101 views

What's the probability that nine people were born in the same two months (but not the same month)?

Find the probability that nine people were born in the same two months (but not all in the same month). No clue how to approach this. I was thinking well you have to choose 8 out of the 9 people and ...
0
votes
3answers
68 views

Problem with permutations

The problem says: We have strings formed by two letters, followed by two digits and then followed by three letters. In each group repetitions are not allowed, but the last group of three letters ...
2
votes
2answers
1k views

Using DeMorgan's Laws to complement a function

Using DeMorgan's Law, write an expression for the complement of $F$ if: $F(x,y,z) = x(y' + z)$. $F=x'+(y'+x)'$ $F(x,y,z) = xy + x'z + yz'$ $F=(xy)'(x'z)'(yz')'$ $F(w,x,y,z) = xyz' (y'z + x)' + ...
3
votes
1answer
810 views

How to prove if log is rational/irrational

I'm an English major, now doubling in computer science. The first course I'm taking is Discrete Mathematics for Computer Science, using the MIT 6.042 textbook. Within the first chapter of the book's ...
0
votes
1answer
46 views

conditional probability Pc(B)

I am looking for the probability of Pc(B) where the event of B={no two people are born in the same month} and event C= {exactly three people were born in the summer of june, july august} and there are ...
-1
votes
1answer
57 views

I am not how they got characteristic equation from the given equation.

![can someone tell me they got characteristic equation from the given recursive equation.][1] i know how to do the rest of problem but getting characteristic equation stopped me. The recurrence is ...
4
votes
2answers
62 views

Smallest such $n \in \mathbb{N}$ that $2^{n} \equiv 1 \pmod{5\cdot 7\cdot 9\cdot 11\cdot 13}$

Can anybody give me a hint about how to find smallest such $n \in \mathbb{N}$ that $2^{n} \equiv 1 \pmod{5\cdot 7\cdot 9\cdot 11\cdot 13}$? I thought that I will find it piece by piece with help ...
0
votes
1answer
29 views

In which the real number system that sum of geometric progression involve? [closed]

I want to know about sum of geometric progression a and r Are they real number it integer .. Etc ?
1
vote
1answer
157 views

'possible outcomes' definition and interpretation

I am baffled on a practice problem I am doing: "A fair coin is flipped 25 times, what are the total possible outcomes?" My question is how do we define and interpret 'possible outcomes'? ...
0
votes
1answer
278 views

Among these figures circle, square, rectangle, isosceles triangle which has the greatest perimeter had the same area?

Among these figures circle, square, rectangle, isosceles triangle which has the greatest perimeter had the same area geometrically ?
3
votes
4answers
61 views

Is $\mbox{lcm}(a,b,c)=\mbox{lcm}(\mbox{lcm}(a,b),c)$?

$\newcommand{\lcm}{\operatorname{lcm}}$Is $\lcm(a,b,c)=\lcm(\lcm(a,b),c)$? I managed to show thus far, that $a,b,c\mid\lcm(\lcm(a,b),c)$, yet I'm unable to prove, that $\lcm(\lcm(a,b),c)$ is the ...
4
votes
2answers
148 views

Minimum number of coins to ensure 10 coins of one type are selected

One coin is labelled with the number $1$, two different coins are labelled with the number $2$, three different coins are labelled with the number $3$, $\ldots$ , forty-nine different coins are ...
1
vote
1answer
81 views

which one? permutation or combination?

Let say we have a bookshelf that can fit 6 books, we want 4 computer science books and 2 physics books but computer books should be together and physics books also should be together, we have 8 ...