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

2
votes
1answer
39 views

Prove: $ 1\times3 +2\times4 + \cdots + n(n+2) = \frac{1}{6} \times n(n+1)(2n+7)$ using Induction

I'm told to prove this by Mathematical Induction: $ 1\times3 +2\times4 + \cdots + n(n+2) = \frac{1}{6} \times n(n+1)(2n+7)$ This is what I have so far: BC: Try $n=1$: $ 1\times3 +2\times4 + \cdots ...
0
votes
2answers
47 views

What is the contrapositive of “if $x^2 (y + 3)$ is even, then $x$ is even or $y$ is odd”?

I believe the contrapositive of this would be: If $x$ is odd, or $y$ is even, then $x^2 (y + 3)$ is odd. Or would it be: If $x$ is odd, AND $y$ is even, then $x^2 (y + 3)$ is odd. Is one of these ...
0
votes
3answers
36 views

Prove that the sum of two multiples of 3 still a multiple of 3

If a and b are multiples of 3 and if I add a+b the result will be a multiple of 3. How can I prove that is true? First of all I know that multiples of 3 are : 3,6,9,12,15 etc. I tried to find a ...
2
votes
1answer
57 views

How to express logical equivalence arrow using Pierce's arrow?

I am really confused about this and not sure how to show $P\iff Q$ with the ↓ arrow and only the ↓ arrow. I understand that $P \iff Q$ is $P\implies Q$ and $Q\implies P$. I also know that $P\implies ...
1
vote
1answer
29 views

Show that K and K' cannot both contain an Eulerian trail

For question (b), I understand how to prove that they can't both contain an Eulerian trail--eulerian trail exists if and only if there are no more than 2 odd degrees of the vertices. So for a ...
0
votes
0answers
19 views

Specific type of Eulerian cycle

Suppose i have a 4-regular planar graph, and furthermore suppose i pair the 4 edges incident to each vertex, so if $v \in V$ is adjacent to edges $\{e_{1},e_{2},e_{3},e_{4}\}$ i could for example pair ...
0
votes
3answers
33 views

Is “$A_i=A_j$” in the definition of a partition correct?

"Definition 5 Let X be a nonempty set. By a partician P of X we mean a set of nonempty subsets of X such that: (a) If A, B$\in$P and A$\neq$B, then A$\bigcap$B=$\emptyset$ (b) $\bigcup \limits_{C ...
0
votes
2answers
19 views

Can I apply the absorption law here?

The absorption law is as: p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p It looks like q doesn't matter. ...
0
votes
2answers
50 views

Bound for $\log { \binom{n}{i}}$?

(1) Are there better (smaller; tighter) bounds for $\log { \binom{n}{i}}$, than $O(n \log n )$? (2) Under what conditions $O(i \log n)$ is a good bound? Clearly this bound should be in a way that it ...
1
vote
2answers
54 views

Taylor series of $e^{-x}$

I am a little bit confused and this could be a stupid question. The Taylor series of $e^x$ is $\sum_{n=0}^\infty \frac{x^n}{n!}$. Based on this, is it true that the Taylor expansion of $e^{-x}$ is ...
0
votes
1answer
14 views

Amount of Bridge Hands

A bridge hand has 13 cards. How any bridge hands can there possibly be if the hands contains exactly two suits? I think it is a few combinations multiplied together, don't know how to set this up.
17
votes
3answers
385 views

How, if at all, does pure mathematics benefit from $2^{74207281}-1$ being prime?

So a couple of days ago the $17$ million digit number $2^{57885161}-1$ was beaten by the $22$ million digit number $2^{74207281}-1$ at being the largest known prime number. Are there any specific ...
0
votes
2answers
30 views

Efficient/easy way to do simple set manipulation

Have two large set of words (strings). Would like to subtract one set from the other. The resulting set would contain only the words not found in the second set. What is an efficient way to do this? ...
0
votes
1answer
44 views

Does discrete topology have interior?

Our textbook define interior as: Let $A$ be a subset of $\mathbb{R}^n$. The interior of $A$, as a subset of $\mathbb{R}^n$ is defined to be the union of all open sets of $\mathbb{R}^n$ that are ...
1
vote
2answers
30 views

How many ordered pairs (with limitations)?

having hard time with the following question: $$A = \{1,2,.....,n\}$$ How many ordered pairs $(B,C)$ which are members of $P(A) \times P(A)$ are there where $B\cap \overline{C}$ is the empty set?
1
vote
1answer
48 views

How can I find the size of this set?

I'm sorry in advance for my bad english. I got this question for homework and just can't solve it: There are 2 sets, $A$ and $B$ which are contained in $\mathbb{N}$ (the set of all natural ...
0
votes
0answers
9 views

Min-cut of a graph using node set partitions

Denote the $x-y$ min-cut value by $g(x,y)$, can I always find a partition of the node set $V$ into three non-overlapping sets $A, B, C$ each containing $x,y$ and $z$ respectively, such that a $x-y$, ...
0
votes
5answers
74 views

Prove that if $n^2 -2n +2$ is odd then $n$ is odd

Prove that if $n^2 -2n +2$ is odd then $n$ is odd I was wondering if you would prove this by using proof by contrapostive. I tried using proof by contrapostive, but I end up with the wrong ...
0
votes
3answers
25 views

Why it's $2^8-127$, not $2^8-(-127)$ when “two's complement of $a$” is $2^n-a$ in binary notation?

"Table 2.5.1 Powers of 2 $$\begin{array} {|c|c|c|c||c|} \hline \text {Power of 2} & 2^{10}& 2^9 & 2^8 & 2^7& 2^6&2^5 &2^4 &2^3 &2^2 &2^1 &2^0 \\ \hline 2 ...
1
vote
0answers
14 views

eccentrcity of vertices in the given graph

I was calculating eccentrcity of vertices of the following generalized Petersen graph $P(15,2)$. For the vertx $u_0$, vertices $u_6$ and $u_7$ are farthest at a distance 4 and for the vertex $v_0$ ...
0
votes
1answer
20 views

Induction on String? (automata related)

Honestly, all I know about mathematical induction is as follow: prove $P(0)$ - base step for all $n \ge 1$, prove $(P(n − 1) \rightarrow P(n))$ - inductive step Prove the following claim by ...
0
votes
1answer
42 views

Is isolated points always boundary points? Is Discrete Topology consisting of isolated points?

Is isolated points always boundary points? What happens in the discrete topology space? If the space is R with discrete topology s.t f(x) = 0 if x is odd natural number, f(x) = 1, x is even natural ...
2
votes
0answers
30 views

Kuratowski theorem methodology

Let's say I have a graph and I have to proof that is is not planar.If it is difficult to find a subgraph that is K3,3 or K5, how can I make the graph more clear so I can spot it.
1
vote
1answer
33 views

How to draw a triangle on a sphere surface where each angle has 90°?

The problem statement says this: Explain how to draw a triangle, on a sphere surface, where each of its angles 90 degrees. In this right triangle, do the hypotenuse and the sides (adjacent and ...
3
votes
1answer
35 views

Can I extend mathematical induction to real numbers? [duplicate]

Here is my rather simple idea. I will treat the set of real numbers as a set of discrete continuities, each separated by an Epsilon ball that tends to 0. So, let's say P(b) is true. We then assume ...
0
votes
1answer
19 views

Why these propositional statements are (basically) identical?

I have this two statements: $A$ if and only if $B$. (Not $A$) if and only if (not $B$). One of requests is to determine when these statements are true. Here is what I done: Then, it is also ...
1
vote
1answer
12 views

Inhomogeneous recurrence relation

I shall solve an inhomogeneous recurrence relation: $$x_n=2x_{n-1}+2^n,\quad x_0=2$$ My approach: The homogeneous part: $$x_n=2x_{n-1}\implies x_n-2x_{n-1}=0$$ With $x_n=x^n$ approach: ...
0
votes
1answer
28 views

How many 6-letter arrangements (without repetitions) of A, B, C, D, E, F are there in which A is just before B and C is just after B?

So i was given this question How many 6-letter arrangements (without repetitions) of A, B, C, D, E, F are there in which A is just before B and C is just after B? What throws me off is how to make ...
1
vote
1answer
12 views

Exercise of conditional and converse clarification

I have this exercise in logic and discrete mathematics: *It's a common error to confuse the following statements: If $A$, then $B$. If $B$, then $A$. Describe two conditions $A$ and $B$ such as ...
-1
votes
1answer
50 views

What is the probability that a randomly chosen 3-digit integer is divisible by $5$?

So I was given a question with two parts: The first part is like this: How many 3-digit integers (integers from 100 to 999 inclusive) are divisible by 5? My solution: $\frac{(999-100+1)}{5} = 180$ ...
2
votes
3answers
83 views

Circular definition in proof

I am confused by the following exercise in Velleman's How To Prove It: 'Suppose $m$ and $n$ are integers. If $mn$ is even, then either $m$ is even or $n$ is even. Proof: Suppose $mn$ is even. Then ...
0
votes
1answer
38 views

Is “a” in $2^n$-a **two's complement of a relative to a fixed bit length n** decimal number?

Definition : Given a positive integer a, the two's complement of a relative to a fixed bit length n is the n-bit binary representation of $2^n$-a Bit lengths of 16 and 32 are the mostly used in ...
2
votes
1answer
30 views

How many words are there of length $7$ are on $\{u,v,w,x,y,z\}$ without the string of letters $xxxx$?

How many words are there of length $7$ are on $\{u,v,w,x,y,z\}$ without the string of letters $xxxx$? My idea here is to use inclusion-exclusion. I was thinking of setting up the problem as ...
1
vote
2answers
27 views

If $P(ABC)=0.2$, are $A$ and $C$ mutually exclusive?

I was finishing up my statistics homework But I was unsure if I was thinking of the last problem correctly. It reads If $P(ABC)=0.2$, are $A$ and $C$ mutually exclusive? My thinking is that ...
2
votes
1answer
45 views

Use induction to prove that any (finite) list is a permutation of itself—in other words, that the permutation relation is reflexive.

I'm having a bit of trouble with starting this proof by induction. I'm given that the definition of a permutation is: List a is a permutation of list b if any of the following are true: • list a and ...
0
votes
1answer
43 views

Is this a valid proof of “For all integers m and n, if mn is even, then m is even, or n is even”?

Theorem: For all integers $m$ and $n$, if $mn$ is even, then $m$ is even, or $n$ is even. Proof: Assume for all integers $m$ and $n$, if $mn$ is even, then $m$ is odd and $n$ is odd. By the ...
3
votes
1answer
56 views

$a_n$ is the number of sequences with length $n$ over ${1,2,3,4,5,6}$

$a_n$ is the number of sequences with length $n$ over ${1,2,3,4,5,6}$ It is allowed up to 2 odd numbers in a row. It is allowed up to 2 even numbers in a row. Find $a_3$ and find the recursion ...
1
vote
0answers
39 views

Is this a valid proof of “a, b are rational, b ≠ 0, r is irrational, then a + br is irrational”

Theorem: If a and b are rational numbers, b ≠ 0, and r is an irrational number, then a + br is irrational. Proof: Assume that if a and b are rational numbers, b ≠ 0, and r is an irrational number, ...
2
votes
4answers
31 views

How many lineups of 20 are possible where Sally is first, second or third, and Adam is somewhere in the line?

The line of 20 is created from 300 students. The next part of the question was to find how many ways there are where Sally is first, second or third. I did a permutation of 299 choose 19 for the ...
2
votes
5answers
100 views

How to write a definition of less than $<$?

I'm learning the fundamentals of discrete mathematics, and I have been requested to solve this problem: According to the set of natural numbers $$ \mathbb{N} = {0, 1, 2, 3, ...} $$ write a ...
2
votes
1answer
24 views

What is meant by “maximal proper factors” of a integer?

I understand what is meant by proper factors, e.g. the proper factors of 36 are 2, 3, 4, 6, 9, 12, & 18. However I've just seen the phrase "maximal proper factors" used in the context of ...
0
votes
0answers
31 views

${a_n}$is the number of series of length $n$ on $\{a,b,c\}$ where $b$ must be before $c$

${a_n}$ is the number of series of size $n$ on $\{a,b,c\}$ where $b$ must be before $c$. So I started by saying that for $f_1$ we get $f_1 = 3$, because only $(a,b,c)$ is allowed. For $f_2$ we get ...
0
votes
1answer
28 views

Knights and Knaves B: “B is a knight only if A is a knight”

I was wondering if someone could help me with this question in Logic. There are two types of inhabitants on an island: One consists of knights, who always tell the truth and the other consists of ...
1
vote
2answers
39 views

Countably Infinite Cartesian Product

I'm having an extremely hard time figuring out how to prove this, would you have to start from one side of the proof and move to the other or prove with induction? For any $n\in\mathbb{N}$, prove ...
0
votes
0answers
19 views

Minimising logistic loss function to find optimal matrix

Please take a look at this paper on classifying triples (re link prediction): http://arxiv.org/pdf/1510.04935v2.pdf The question is about how to solve equation 2 using stochastic gradient descent. It ...
0
votes
2answers
42 views

Find $x \in{Z_{250}}$ so that $ x\equiv{248^{156,454,638}} \pmod{250}$?

I am looking for a easy way to solve it, without use the computer. I did that but with the computer. $GCD(250,248) \ne 1$ So I did: $250 = 125*2$ $248^{156454638}$ (mod 250) = $248^{156454638}$ ...
0
votes
1answer
10 views

Are any two pairs in a cyclic path of a transitive relation symmetric?

Suppose $R$ is a transitive binary relation that contains a cycle $a_1Ra_2$, $a_2Ra_3$, $\dots$, $a_{n-1}Ra_n$, $a_nRa_1$. Does this imply that $R$ is symmetric for any pairs in this cycle, i.e. ...
0
votes
0answers
39 views

how to solve this system of equations using gaussian?

Please explain it step by step. I couldn't do it on my own. tried $3$ times, still got no solution to it. but it has infinitely many solutions. $$ \begin{cases}2y+z+4v= -5\\ 2x-3y-z+2w+3v= 4\\ ...
0
votes
1answer
45 views

What is a class of a graph?

I found this question on my textbook.What is the class of the graphs in which every Eulerian cycle is also a Hamiltonian cycle, but I don't understand what he means by class.
0
votes
1answer
33 views

Shortest path change in weighted graph

In a weighted graph does the shortest path between two vertices change if we add to all the weights the same positive number?