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.
33,177
questions
2
votes
0
answers
19
views
Closed formula for sum of rounded up power of two fractions of a positive whole number
Given $n\in\mathbb{N}_{\gt 0}$ provide a closed formula for
$$
f(n):=\sum_{l=0}^{\lceil\log_2(n)\rceil} \bigg\lceil\frac{n}{2^l}\bigg\rceil
$$
If there is $k\in\mathbb{N}$, such that $n=2^k$, we have
$...
- 121
0
votes
1
answer
37
views
Confusion on the proof of the transitivity of Big-O
This proof comes from Rosen's Discrete Math Textbook. It talks about how if $f(x) = O(g(x))$ and $g(x) = O(h(x))$, then $f(x) = O(h(x))$. My confusion is with the constants $C_1, C_2$, where how would ...
- 865
0
votes
3
answers
56
views
Big-O definition question on the constant C
From Rosen's discrete Math textbook. Based on the definition of Big-O given, do we assume C is positive or at least non-negative? Otherwise if not I feel the inequality wouldn't hold. Kindly let me ...
- 865
-1
votes
2
answers
179
views
What does "the set of all $x$'s" mean?
In the context of set theory, I see on websites that set builder notation like $$\{x \mid P(x)\}$$ is read in natural language as "the set of all $x$'s that satisfy the predicate $P(x)$". ...
- 11
-1
votes
1
answer
112
views
Basketball players and quantifiers [closed]
From Susanna Epps's Discrete Mathematics:
Statement: For all basketball players x, x is tall.
(c) Some of the tall people are basketball players.
Are the first statement and (c) equivalent?
The given ...
- 9
0
votes
1
answer
48
views
A proof for the statement: The 3-Dimensional matching problem is NP-Complete
The 3-Dimensional Matching Problem is relatively well known in the fields of discrete mathematics and computer science. The problem consists of determining whether a tripartite
$3$-hypergraph with ...
- 3,408
0
votes
1
answer
47
views
Proof that if a graph has edge connectivity 3, then the girth is bounded by the number of nodes divided by two + 1, g(G) <= |V(G)| / 2 + 1
I've not been able to solve this problem for a week now. My idea was that I start with a circle with n nodes and because the edge connectivity is 3, every node must have at least 3 neighbours, so to ...
- 11
-1
votes
0
answers
92
views
Solve the recurrence relation: $a_{n+2} + a_n = 0$ [duplicate]
Hello I would like to know if this is the correct way to solve this recurrence relation and also if it's the right answer. I would be really thankful if somebody could help me or confirm that this is ...
- 111
0
votes
1
answer
33
views
Graph with no induced C4 or P4 has an n-1 degree vertex [closed]
Prove: Graph with no induced C4 or P4 has an n-1 degree vertex
Reuploading this question, since I haven't got a satisfied response from there.
Basically the question is: Connected Graph G with no ...
0
votes
1
answer
34
views
Confused on Big-O theorem
When in Rosen's Discrete Math Textbook they give the theorem:
Suppose that $f_1(x)$ is $O(g_1(x))$ and that $f_2(x)$ is $O(g_2(x))$.
Then $(f_1 + f_2)(x)$ is $O(g(x))$, where $g(x) = (max(|g_1(x)|,\, ...
- 865
0
votes
0
answers
65
views
Logic, deductive systems and mathematics
I'm studying logic as part of my discrete mathematics course, and while the book does a good job at explaining propositions, connectives, quantifiers, proofs, etc, in a mechanical way, I'm trying to ...
- 43
1
vote
1
answer
38
views
If G is a 2$\le$k-th regular graph then every edge is part of a circle.
I'm not certain if the following statement is true: If G is a $2 \le k$-th regular graph then every edge is part of a circle.
I was trying to prove this lemma for a bigger proof, I'd like to get a ...
1
vote
0
answers
40
views
Feeling this proof that $\log_b(n)$ is $O(n)$, where b is any positive real number $\neq 2$, has an error.
From Rosen's Discrete Math textbook, I feel the part of the proof where they say
$$\log_b n = \frac{\log_2 n}{\log_2 b} < \frac{n}{\log_2 b}$$ where $b$ is any positive number not equal to $2$ is ...
- 865
3
votes
2
answers
186
views
Why does $\forall n \in \mathbb{N} \vdash P(n)$ not imply $\forall n \in \mathbb{N}P(n)$?
I am trying to understand why $\forall n \in \mathbb{N} \vdash P(n)$ doesn't imply $\forall n \in \mathbb{N}P(n)$ by studying the concepts in this answer, and had 2 questions about the difference ...
- 2,979
-1
votes
0
answers
54
views
why sum of $2^k + 2^{k+1}+2^{k+2} ......... + 2^s= 2^{s+1} - 2^k$? [duplicate]
Prove $$2^k + 2^{k+1}+2^{k+2} ......... + 2^s= 2^{s+1} - 2^k$$
I recently solved a problem on Codeforces (contest 1977, problem B) which utilized a mathematical formula, but I don't fully understand ...
