Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [discrete-mathematics]

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.

Discrete mathematics is not the name of a branch of mathematics, like number theory, algebra, calculus, etc. Rather, it's a description of a set of branches of math that all have in common the feature that they are "discrete" rather than "continuous".

The term "discrete mathematics" is therefore used in contrast with "continuous mathematics," which is the branch of mathematics dealing with objects that can vary smoothly (and which includes, for example, calculus). Whereas discrete objects can often be characterized by integers, continuous objects require real numbers.

Though there cannot be a definite number of branches of Discrete Mathematics, the following topics are almost always covered in any study regarding this matter −

  • Sets, Relations and Functions
  • Mathematical Logic
  • Group theory
  • Counting Theory
  • Probability
  • Mathematical Induction and Recurrence Relations
  • Graph Theory
  • Trees
  • Boolean Algebra

For an overview, see the Wikipedia entry on Discrete mathematics.

and http://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf

Consider using a more specific tag instead, such as: , , , , , , , , etc.

32903 questions
1
vote
2 answers

discrete math Quantifiers?

In the following exercises, V(x,y) means "x + y = 2xy", where x and y are integers. Determine the truth value of the statement: ∀x∃y¬V(x,y) what this says is for every x, there exists an y such that negation of V? what is the negation v? and also…
user105125
  • 13
1
vote
4 answers

Prove that $C_n < 4n^2$ for all n greater than or equal to 1

$C_1 = 0$, $C_n = C_{\lfloor n/2\rfloor} + n^2$ for all $n \ge 1$ Prove that $C_n < 4n^2$ for all $n \ge 1$. I don't know how to even approach this. I remember something about inductive proofs...but i really don't understand that, could you please…
Jasmine
  • 121
1
vote
2 answers

Prove that a set is countable

Show using a proper theorem that the set {2, 3, 4, 8, 9, 16, 27, 32, 64, 81, … } is a countable set. Im lost, this is for school, but there is a huge language barrier between students and professor. I have started it but have no idea if how i have…
Sampson
  • 9
1
vote
1 answer

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.
math Lee
  • 13
1
vote
1 answer

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?
eniid15
  • 145
1
vote
2 answers

If $r$ is irrational, there is a unique integer $n$ with $|r- n|<1/2$

I'm working on proving the following statement: Show that if r is an irrational number, there is a unique integer n such that the distance between r and n is less than $\frac{1}{2}$. How do I show uniqueness using a proof by contradiction? How do I…
Bob Shannon
  • 1,561
1
vote
1 answer

Making N baht using only 9 baht and 10 baht coins

The Thai government decides to issue coins of 9 baht. Show that, for all sufficiently large numbers N you can make N baht using only 9 baht and 10 baht coins.
mathis...Math
  • 343
1
vote
2 answers

$123^{561}$ find last $2$ digits Modular Exponentiation mod $100$?

$123^{561}$ Find the last $2$ digits Can't I work this out using modular exponentiation working mod $100$? $123^2 = 29\pmod{100}$ $123^4 = (123^2)^2 = 41\pmod{100}$ $123^8 = (123^4)^2 = 81\pmod{100}$ $123^{16} = (123^8)^2 = 61\pmod{100}$ $123^{32} =…
Ryan
  • 11
1
vote
3 answers

Proving two numbers $q1, q2$ are relatively prime, related to the the $gcd(a,b)$

$a,b > 1$ and are integers, and $g: = gcd(a,b)$ is their greatest common divisor. Show that if $a= g * q1$ and $b = g * q2$, then $q1$ and $q2$ are relatively prime.
user102653
  • 11
1
vote
1 answer

Representing the empty set on an Euler diagram

I try to describe with Euler diagram the following relations: $A \oplus A = \emptyset$ and $\emptyset \subset (A \cap B) \subset (A \cup B)$. But empty set confuses me. I even cannot imagine how to use Euler diagram with the first expression. But…
Dragon
  • 243
  • 1
  • 3
  • 8
1
vote
1 answer

Uniqueness Proof for Discrete Math

Can someone show me how to prove the uniqueness of (p is prime and q is prime and p-q=3)?
Jonathon
  • 11
1
vote
5 answers

Discrete structures exercise

I have this exercise in my worksheet I am a beginner. Prove or disprove that if $A,B$ and $C$ are sets such that $A\times B = A \times C$ then $B = C$.
user102291
  • 43
1
vote
3 answers

How many numbers from 1 through 60100 are divisible by none of the numbers from 2 through 6?

My thoughts on doing this problem: total numbers is 60100 so from the total I subtract the numbers divisible by 2, 3, 4, 5, and 6. Yet my answer 60100-30050-20033-15025-12020-10016 is a negative number. How to solve this problem?
Jinzu
  • 819
1
vote
1 answer

Recurrence relation $g(n) = g( \lfloor {n/2}\rfloor) + \lfloor{log_2{n}}\rfloor $

$g(n) = g( \lfloor {n/2}\rfloor) + \lfloor{log_2{n}}\rfloor \\ g(0) = 0$ Series is like this: $0,0,1,1,3,3,3,3,6,6,6,6,6,6,6,6,10,...$ and it's changes similar as $\lfloor{log_2{n}}\rfloor $ $0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,....$ But I can't find…
Machiaweliczny
  • 489
1
vote
2 answers

Solve recurrence relation $ a_{n+1} = (n+1)a_n + 1 $

$a_0 = 1 \\ a_{n+1} = (n+1)a_n + 1 $ Could you help me solve this? And maybe someone know good source explaining how to solve recurrence relations?
Machiaweliczny
  • 489
1 2 3
…
99 100