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

learn more… | top users | synonyms

0
votes
0answers
11 views

Proof for Ordering

I am pre-studying a course (Discrete Mathematics) that I will be taking come Fall quarter this October. We are using the textbook Invitation to Discrete Mathematics and I am having trouble starting to ...
0
votes
1answer
21 views

conjecture formula/prove by induction

Conjecture formula from following equations, and prove conjecture: $1=1,\\2+3+4=1+8,\\5+6+7+8+9=8+27,\\10+11+12+13+14+15+16=27+64\\$ $S(n)=\sum_{i=(n-1)^2+1}^{n^2}i=(n-1)^3+n^3$ ...
2
votes
1answer
32 views

Unsolveable equation?

If we have the inhomogenous recurrence relation $$f(n+2) - 6f(n+1)+9f(n) = 6*3^{n} + 2^{n} = 2 * 3^{n+1} + 2^n, f(0) = 0, f(1) = 1, n \ge 1$$ Step 1: Find the homogenous solution $f(n) = C_13^n + ...
0
votes
0answers
13 views

Expanding Algebra set

I am doing Discrete maths on self-study basis. I am wondering how this set algebra comes about: that $(A\cup B)\cap (A^\complement \cup B^\complement) $ expands to $(A\cup A^\complement)\cup (A\cap ...
0
votes
0answers
7 views

Proof on Lattices

Prove that a partially ordered set is a lattice if every two elements in the set have a unique least upper bound and a unique greatest lower bound. I was unable to find a way to prove this.
0
votes
0answers
64 views

Fibonacci sequence: Prove the formula $f_{2n+1}=f_{n+1}^2 + f_n^2$ [duplicate]

I can't seem to figure out this proof. I'm using weak induction and always get stuck during the inductive step. Prove for n > 0: $$f_{2n+1} = f_{n+1}^2 + f_n^2$$
1
vote
0answers
35 views

Problem on pigeon hole principle

This is a problem based on pigeon hole principle. A tennis player has three weeks to prepare for a tennis tournament.She decides to play at least one set every day but not more than 36 in all.Show ...
-3
votes
1answer
33 views

How do you answer this Bayes theorem question? [on hold]

Your computer is acting strangely and you suspect it has a virus. Unfortunately all 5 of your virus detection programs are outdated. If your computer has a virus then each program, independently of ...
0
votes
3answers
23 views

Prove that: if $x \sqcup \bar{y}=1$, then $x \sqcup y=x$ (in a Boolean algebra)

Suppose X is a Boolean algebra. Prove that: if $x \sqcup \bar{y}=1$, then $x \sqcup y=x$ I suspect this one is not that difficult, but for some reason I can't find the answer. This homework ...
1
vote
1answer
17 views

What is the supremum of {36,72} in this Hasse-diagram?

In this Hasse-diagram is sup({36,72})={72} or is it non-existent? I think it might be {72} because {72} seems to be the upper bound of {36,72}. Then again, {72} seems to be the only upper bound, so ...
0
votes
2answers
36 views

How many of the n! permutations π from set N to N satisfy min(π(A)) = min(π(B))

Given a set of elements $N = \{1, 2,\ldots, n\}$ and two arbitrary subsets $A\subseteq N$ and $B\subseteq N$, how many of the $n!$ permutations π from $N$ to $N$ satisfy min(π$(A)$) = min(π$(B)$), ...
-5
votes
2answers
48 views

If $x \in \mathbb{R}$ and $x \neq 15$, then $x^3 - 5x^2 + 3x \neq 15$ [on hold]

I tried this and managed to disprove it. Not sure if this is correct. Someone please help me
0
votes
4answers
26 views

How to write a formal proof of the statement: For all integers n, if n is a multiple of 5 then 3n is a multiple of 5.

Prove: For all integers $n$, if $n$ is a multiple of $5$ then $3n$ is a multiple of $5$. Proof: Assume $n$ is a multiple of $5$. Then $n$ must have the form $5k$ where $k \in \mathbb{N}$. We have ...
-1
votes
2answers
39 views

$2^n \geq n+1$ by mathematical induction [on hold]

What is proof by mathematical induction? Show that for any integer $n$ greater than zero, $2^n \geq n+1$. I got this question as assignment. But I can't find the solution. Please help me to solve ...
0
votes
0answers
22 views

City grid problem: how to interpret such that we use Vandermonde's convolution

A person wants to return to their house that is two blocks north and three blocks east. The problem resolves to taking five moves such that two are northward; there are thus $C(5,2) = 10$ total paths. ...
-1
votes
0answers
16 views

Finding $R(X)$, if $R ⊆ [0,1]x[0,1]$ and $X=[1/4, 1/2]$ in discrete mathematics. [on hold]

Let $X=[1/4, 1/2]$ and define the relation $xRb = (x≤y) \land (x+2y≤1)$. What would be $R(X)$?
-1
votes
0answers
19 views

Prove or Disprove? log(n^n) is Theta(log n)

I need help confirming that my way of proof is alright. This is my first class in algorithms so I just wanna know if I'm on the right track. :)
2
votes
3answers
40 views

Prove or Disprove n! = BigOh(2^n) via mathematical induction.

My computer science professor has us tasked with proving or disproving the statement the n! = BigOh(2^n). We are then suppose to say if it's always true, always false, or non-conclusive, ...
0
votes
1answer
15 views

Find the possible number of assignments?

S students, I interviewers, each student has to undergo R interviews, each interviewer can interview at max X students. No student interviews with an interviewer more than once, and no interviewer ...
0
votes
1answer
21 views

Modular Arithmatic $(-17*23)$mod$(11)$

Evaluate $(-17*23) \mbox{ mod }(11)$ Can you show the working for this? Im trying to understand how you do this so clear instruction would be great. Thank you.
0
votes
1answer
44 views

Predicate Logic and Logic Proofs(Review & Homework Questions)

I'm working on some homework questions and I am struggling very hard with the logic proofs. I might have an incorrect answer for 1 of the predicate questions but I think my question makes some sort of ...
0
votes
3answers
35 views

What is wrong with my algorithm for finding how many positive integers are divisible by a number d in range [x,y]?

I have been solving basic counting problems from Kenneth Rosen's Discrete Mathematics textbook (6th edition). These come from section 5-1 (the basics of counting), pages 344 - 347. This question ...
1
vote
1answer
41 views

Solving for a variable in an integer divisibility problem

Say I have a problem of the form Where , , and are known integers, is some unknown variable, and is an integer output. Is there an approach I could take to determine if there is some integer ...
1
vote
2answers
51 views

Can the expected value of a PMF be zero, as in E[X] = 0?

The whole question is: Let X be a discrete random variable and let Y = 0.5 X + 3. (i) Assume that the PMF of X is given by where k is some suitable constant. Determine the value of k. (ii) Find E ...
0
votes
1answer
25 views

Need help to understand some terminology in discrete math

1) "Suppose that f is a function from set A to itself." 2) "(...)from the set of real numbers to itself." In these two sentences, what does "to itself" mean? Is this the same as saying that 1) is f: ...
0
votes
5answers
52 views

How to work out $-1 \bmod 7$?

What is the working out for $-1 \bmod 7$? I can do it if the numbers are positive just the negative throws me off.
1
vote
2answers
42 views

Discrete Math sequence question

The question is find $a3$: $a_0 = 2, a_1 = 4$ and $a_{k+2} = 3a_{k+1}-a_k$ for any integer $k \geq 0 $ I know the answer is 26, although how do you get the answer?
4
votes
4answers
478 views

How many integers in the range [1,999] are divisible by exactly 1 of 7 and 11?

This is a question in Kenneth Rosen's Discrete Mathematics textbook 6th edition. I haven't had trouble with any other counting problems regarding "how many numbers in range [x,y] have divisibility ...
1
vote
2answers
34 views

Well Ordering Principle for a sum and why we only care about the set less than the smallest in our counter example set?

I was trying to prove: $$ \sum_{i=1}^n{i} = \frac{n(n+1)}{2}$$ using the WOP. I think the part that is confusing me about this proof is a more general pattern for proofs by WOP. To prove it we ...
1
vote
2answers
37 views

Need help with $(¬p \vee ¬(p\wedge¬q)) \wedge ¬(p \wedge q) ≡¬p$

Hey guys I just need help solving this solution here. Sorry if I didn't type the symbols correctly. My solution so far: $$ (¬p \vee ¬(p\wedge¬q)) \wedge (¬p \vee ¬q)≡ (¬p \vee (¬p \vee q)) \wedge (¬p ...
0
votes
2answers
36 views

On proving quadratic residues have 4 square roots

I'm trying to write up a proof of "if a is a quadratic residue modulo N then it has 4 separate square roots". N is the product of two primes and I have to consider the multiplicative group of the ...
0
votes
1answer
32 views

Negation of a proposition of the form “not(p) & q”

This is a homework question I'm working on. I think it's right but I'm just curious if I'm supposed to state the negation of "but it is always right" differently. Find the negation of the ...
0
votes
1answer
29 views

$(a \vee b)\wedge c=b\wedge c$ implies $(c\wedge b)\wedge a= b \vee c$

Show that for any elements a,b,c in a modular lattice $(a \vee b)\wedge c=b\wedge c$ implies $(c\wedge b)\wedge a= b \vee c$ ? $\wedge$ is meet and $\vee$ is join operations respectively .
10
votes
0answers
144 views

$1^2+2^2+\cdots+24^2=70^2$ and squarily squaring the torus

The unique nontrivial solution to $1^2+2^2+\cdots+n^2=m^2$ is $(n,m)=(24,70)$. (This fact has connections to modular forms, special functions, lattices and string theory.) Martin Gardner, in the ...
0
votes
0answers
14 views

Optimize the distribution if it is left unsmoothed

I have a question about distribution. Let see my problem The paper said that the distributions p and q are left unsmoothed, so we can ignore Kernel density. But I don't understand what is left ...
1
vote
4answers
54 views

Prove this by induction?

I'm trying to do homework problems and for the most part I've been getting the results. For this one though, I am having some trouble since its $2^n$ and I can't relate it properly: So obviously, the ...
4
votes
0answers
92 views
+50

How to show that this discrete function respects the strict ordering of its input.

Suppose you have a vector $\pmb x=\{x_i\}_{i=1}^n$ such that, for any given index $1\leq i\leq n$ the $n-1$ vector of values $$\{|x_i-x_{j}|\}_{j \neq i}$$ contains no tie (i.e. no two values are ...
-3
votes
0answers
22 views

determine the validity of the argument [on hold]

Determine the validity of the following argument: If an object is not blue then it is not a triangle. If an object is not above all the black objects, then it is not a square. All ...
2
votes
1answer
21 views

I have two symmetric relations on a set. How can I prove that the symmetric difference is irreflexive?

I have this problem. Let R and S be symmetric relations on a set A. Prove or disprove: $R \oplus S$ is irreflexive. Now I'm assuming it's not true, because $(x,x)$ can be an element of $R$ ...
2
votes
5answers
107 views

Is $\mathcal P(A) \times \mathcal P(B)=\mathcal P(A\times B)$?

Let $A=\lbrace 1,2 \rbrace$ and $B=\lbrace 2,3,4 \rbrace$. Is $\mathcal P(A)\times \mathcal P(B)=\mathcal P(A\times B)$? My attempt and reasoning, from the first one, I compute the powerset of both ...
0
votes
2answers
40 views

prove that the sum to n terms of the sequence is $n(n+1)/2(2n+1)$ [duplicate]

Prove that the sum to n terms of the Sequence: $1^2/(1×3),2^2/(3×5),3^2/(5×7),...$ is $ n(n+1)/2(2n+1).$ Im having trouble with this question, firstly ive begun by stating that p(n) denotes the ...
0
votes
1answer
38 views

Proof Question involving Binary Strings & Sets

I'm just wondering about this question I've been working on for my review homework. I tried to solve it on my own and I feel my proof makes decent sense but not the best sense. Please try to give any ...
-1
votes
0answers
10 views

Discrete Structure. Which of the following statements is right and which is wrong [on hold]

∀x F(x) ∧ ∀x G(x) ≡ ∀x (F(x) ∧ G(x)) I would like an explanation please. I'm not quite sure i understand how to go about solving this.
0
votes
0answers
72 views

Let Cn denote the number of ways of writing a valid list of open and closed parentheses of length 2n

(a) Let Cn denote the number of ways of writing a valid list of open and closed parentheses of length 2n (valid means that at any point along the list, the number of open parentheses must be greater ...
0
votes
2answers
49 views

Probability/Set theory problem

The problem is: In some country, there are 3 newspapers. 20% of the population read newspaper A, 16% read B, and 14% read C. 8% of the population read both A and B, 5% read A and C, and 4% ...
0
votes
1answer
33 views

I need help in understanding O(nlogn) question

I wish I could think of a better way to word my question. Maybe some one here could offer s suggestion for that, as well. On to my question. Before I do, this is a class question that has been asked, ...
1
vote
1answer
45 views

Strong mathematical induction with a sequence

The question: The terms of a sequence are given recursively as $a_0 = 1$, $a_1 = 1$ and $a_n=2a_{n-1} + 3a_{n-2}$ for $n \geq 2$ prove by mathematical induction $a_n = \frac12(3^n) +\frac12(-1)^n$ ...
0
votes
3answers
30 views

Induction assuming n-1

In induction, I always thought that one assumed that some statement was true for n and then showed it's true for $n+1$. But in one proof I am trying to understand, I think that they assume that it's ...
2
votes
3answers
69 views

Maximum value of $a+b$ given that $\frac{1}{a} + \frac{1}{b} = \frac{1}{20}$

What is the maximum value of $a+b$ given that $\frac{1}{a} + \frac{1}{b} = \frac{1}{20}$ here $a,b \in \mathbb{Z^+}$? What I have gotten so far: From the above, $\frac{a+b}{ab} = ...
2
votes
0answers
28 views

Fast algorithm/formula for serial range of modulo of co-prime numbers [migrated]

In my project, one part of problem is there. But to simplify, here the problem is being formulated. There are two positive co-prime integers: $a$ and $b$, where $a < b$. Multiples of $a$ from 1 ...