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
2
votes
2 answers

Recurrence Relation: $a_{n+2}+a_n=5\cos (n\pi/3)-7\sin(n\pi/4)$

Recurrence Relation: $a_{n+2}+a_n=5\cos \left(\frac{n\pi}{3}\right)-7\sin\left(\frac{n\pi}{4}\right)$ Attempt: The solution of the associated homogeneous relation is \begin{align} a_n^{(h)}&=c_1\left(\cos \left(\frac{n\pi}{2}\right)+i\sin…
Gabriela
  • 850
2
votes
3 answers

Proving if $x$ is an even integer then $x^2 -6x +5$ is odd

If $x$ is an even integer, then $x^2 - 6x + 5$ is odd. My solution (direct proving): $$ x = 2k$$ $$ x^2 - 6x + 5 = 4k^2 -12k + 5 $$ $$ 4k^2 -12k + 4 + 1 = 2(2k^2-6k+2)+1$$ which is by definition is odd. Is my solution correct?
jantristanmilan
  • 1,085
2
votes
1 answer

How to prove that "$\forall x(P(x)\vee Q(x))$” and "$\forall xP(x)\vee\forall xQ(x)$” are not equivalent?

How to prove that $”\forall x (P(x)\lor Q(x))”$ and $”\forall xP(x)\lor\forall xQ(x)”$ are not equivalent? How to prove it? I don't even know how to start.
Bill
  • 23
2
votes
4 answers

$R_n = 3(2^n)-4(5^n)$, $n \geq0$, prove $R_n$ satisfies $R_n = 7R_{n-1}-10R_{n-2}$

So the question is: $R_n=3(2^n)-4(5^n)$ for $n\ge 0$; prove that $R_n$ satisfies $R_n=7R_{n-1}-10R_{n-2}$. I don't really know what to do from here. If I substitute $$R_n = 3(2^n)-4(5^n)$$ into $$Rn = 7R_{n-1}-10R_{n-2}$$ I end up getting $$R_n…
MK3GTX
  • 25
2
votes
0 answers

correlation between three variables -1 to 1

Let $X,Y,Z$ be 3 random variables. If the correlation between $X$ and $Y $ is $c_1\ge 0$ and the correlation between $Y$ and $Z$ is $c_2\ge 0$, what is the maximum and minimum possible correlation between $X$ and $Z$ in terms of $c_1$ and $c_2$?…
vootoo
  • 21
2
votes
2 answers

Difference of sets and power set question

I am asked to state whether the following statements are TRUE or FALSE $\emptyset$ is in $P(A)$. $\emptyset$ is subset of A. My answer is that both of these statements are true.
user894189
2
votes
3 answers

How can I prove that the l.h.s equals the r.h.s?

I can't move forward. Can anyone help? $$\frac{k (2k) + 2 }{ k (k + 1) }= \frac{2k + 2 }{ k + 2}$$ I'm trying to prove that the left side equals the right side. It started like this $$\frac{2k }{ k + 1} + \frac{1}{1+2+3+...+(k+1)}= \frac{2(k + 1)…
Alaa Mhmd
  • 31
2
votes
4 answers

Understanding basic concept of prime numbers

My textbook provides a theorem but I cannot understand the structure of the sentence being used. Could someone please help me understand the meaning of this theorem? A natural number $n>1$ is prime if and only if for all primes $p\leq \sqrt{n}$,…
Bobby B
  • 419
2
votes
0 answers

Find last remaining person in the game

In a game, $N$ people are lined up in a circle and numbered from $0$ to $N-1$. At each turn, the next $K$th person, starting with the last eliminated person, is eliminated from the game. The first person to be eliminated is the $K$th. Find the last…
M3601
  • 21
2
votes
1 answer

Aggregate Relationships

Which of the following represents an aggregate relationship (has-a)? Parent and child. Animal and dog. teacher and computer phone and fax machine All of the bove The correct answer is 3. But why is not 1 also an aggregate relationship?
Avv
  • 1,159
2
votes
1 answer

Prove that a strictly decreasing function from $f:\Bbb R \to \Bbb R$ is one-to-one

I would like to prove that a strictly decreasing function from $f:\Bbb R \to \Bbb R$ is one-to-one. We want to show that show that $f(a) = f(b)$ implies $ a = b$ for all $a, b \in \Bbb R$. One proof I saw online was as follows (although I did the…
Avv
  • 1,159
2
votes
0 answers

Set Theory Venn Diagram Question

I have to use the above-provided information in the venn diagram to figure out $|C\setminus B\setminus A|$. I know that \ means the same thing as - (or 'subtraction'). $C = \{1, 8, 13\}$ $B = \{2, 11, 13\}$ $A = \{1, 2, 9, 13\}$ Now, I just have to…
seoul_007
  • 203
2
votes
1 answer

If $f: [0, 1] \to \mathbb R$ is defined by $() = ^2$, check $f$ is bijective or not?how?

If $f: [0, 1] \to \mathbb R$ is defined by $() = ^2$, check $f$ is bijective or not?how? I don't think it is onto because 6 doesn't have any pre image but 6 belongs to R
SHUVAM JASWAL
  • 23
2
votes
1 answer

Please help me understand the solution of this question!

Question : Six bells commence tooling together and toll at intervals 2,4,6,8,10,12 minutes.In 30 hours,how many times do they toll together? I found the LCM of 2,4,6,8,10,12 minutes in order to find the minimum minutes after they will tool…
Harsh Gautam
  • 89
2
votes
2 answers

Show using induction (coupled linear recurrences)

Some homework help would be greatly appreciated, took a screenshot and made an image to make it easier to show and get help with. (2) Consider the numbers defined recursively by $a_1=3$, $c_1=5$, $$a_{n+1}=3a_n+2c_n+1\text{ and…
Miguel
  • 147
1 2 3
…
99 100