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

1
vote
2answers
76 views

What does “arrange all variables to range over one domain” mean?

In these notes (page 18, section 1.3.7) 1.3.7 Variables Over One Domain When all the variables in a formula are understood to take values from the same nonempty set, $D$, it’s conventional ...
1
vote
1answer
20 views

Injective Function satisfying all certain domain

The function $f : \mathbb R \to \mathbb R$ satisfies $f(f(x)) − f(x) = x$. Is f injective? Why? Find all values of x such that $f(f(x)) = 0$. I think the function is one to one, though I am somewhat ...
1
vote
1answer
49 views

Attempting a discrete proof: Not sure what I am doing wrong?

So this is an exercise that is a supplement to my studies in discrete math, I want to understand what my error is. The online training drill I am using reports the below is incorrect / or as we would ...
1
vote
1answer
80 views

Discrete Dynamical Systems & Credit Card Debt: How to solve for payment

I have the following problem, taken out of Giordano, Fox, and Horton's A First Course in Mathematical Modeling: Your current credit card balance is $\$12,000$ with a current rate of $19.9\%$ per ...
1
vote
3answers
38 views

Number theory problem! Prove the following using the method that relies on “Universal Generalization”.

If $n$ is the product of four consecutive integers then $n+1$ is a perfect square. Domain is all natural numbers What I got so far: Let $a$ be an element of natural numbers selected arbitrarily ...
1
vote
1answer
97 views

Is there any regular, balanced, connected bipartite graph that does not contain any Hamiltonian cycle? [duplicate]

In a set of balanced, connected bipartite graphs, all with regularity $r \ge 2$, is it possible that there exists a bipartite graph that does not contain a Hamiltonian cycle ? My argument: The ...
1
vote
1answer
19 views

I am trying to prove that a series has only non-integer entries after an element in the series.

I'm trying to prove that the series $a_n=\frac{6n}{4+n}$ has non-integer values for n>20. I attempted doing this by induction but couldn't get it to work.
1
vote
3answers
95 views

Proof by induction

The question is prove that for every integer greater than or equal to 2 $$\frac{1}{n+1} + \frac{1}{n+2} + \ldots + \frac{1}{2n} \geq \frac{7}{12}$$ So far I have Base case let $p(2)$ ...
1
vote
1answer
42 views

interpreting partitions of integers(generating functions)

the question is: In $ f(x) = \left (\frac{1}{1-x} \right )\left (\frac{1}{1-x^2} \right )\left (\frac{1}{1-x^3} \right )$the coefficient of $x^6$ is 7. Interpret this result in terms of partitions ...
1
vote
1answer
68 views

Discrete Math Boys and Girls

Problem 4: Boys and Girls Consider a set of m boys and n girls. A group is called homogeneous if it consists of all boys or all girls. In the following questions, practice the multiplication and the ...
1
vote
1answer
65 views

Find the number of bit strings which start with four zeroes and end with three ones

Count the number of bit strings that start with four $0$'s or end with three $1$'s if the length of the bit string is: $7$ $4$
1
vote
1answer
76 views

Usage of the term “perfect matching” for bipartite graphs

A textbook written by my discrete mathematics teacher defines a "perfect matching" in a bipartite graph as a matching that covers at least one side of the graph (i.e. for $G = (V1, V2, E)$ with $V1$ ...
1
vote
2answers
215 views

What mistake am I making when trying to apply Fermat's little theorem?

This is a problem from Discrete Mathematics and its Applications This is Fermat's little theorem from https://www.youtube.com/watch?v=w0ZQvZLx2KA, Here is my work so far First 41 is prime and ...
1
vote
1answer
37 views

Proving arguments logically by inference

I think I am on the right track but got stuck on 6. $p ∨ (r ∧ t)$ premise $¬p ∨ ¬(q ∧ u)$ premise $(q ∧ u) ∨ s$ premise $¬s$ premise $(r ∧ t) ∨ ¬(q ∧ u)$ 1,2, Resolution $(q ∧ u)$ 3,4, ...
1
vote
1answer
68 views

Induction or pigeonhole principle or what?

Hello I've this exercise but I am not sure how you prove it formally. Some guy $G$ was writing book for $81$ hours in $10$ consecutive days. Show that there was $2$ consecutive days that included ...
1
vote
4answers
171 views

How to prove this modular multiplication property to be true?

I am watching a youtube video on modular exponentiation https://www.youtube.com/watch?v=sL-YtCqDS90 Here is author's work In this problem, the author was trying to calculate $5^{40}$ He worked ...
1
vote
2answers
34 views

What is $E[x]$.

There are $m$ white balls and $n$ black balls in bag. We take out one-by-one each one of the $m+n$ balls. Let $X$ be the random variable denotes the number of white balls before taking out the ...
1
vote
1answer
166 views

Rewriting quantified statements using logical operators, but without using quantifiers.

I just need help verifying my answers cause I'm still not 100% what I'm doing at the moment! Let P and Q be predicates on the set S, where S has two elements, say,$ S = {a, b} $. Then the statement ...
1
vote
2answers
699 views

If $p$ divides $a^n$, how to prove/disprove that $p^n$ divides $a^n$? [duplicate]

The only thing I know for this problem is that an integer is a product of primes.
1
vote
2answers
42 views

Show function g(x) is continous

I'm not able to understand how to prove this theorem. Consider a continuous function, $f : \mathbb{R} \rightarrow \mathbb R$. Using the definition of continuity, show that the function $g(x) = ...
1
vote
1answer
48 views

How to prove elementary identities for binomial coefficients using combinatorial arguments?

I'm in a second year discrete mathematics course, and we have identities like this $$\binom{n}{k}(n-k) = \binom{n-1}{k}n$$ and Pascal's Triangle law. Our professor said that algebraic proofs are ...
1
vote
1answer
214 views

What does it mean for a function to be $\Omega(1)$?

I am having a lot of trouble understanding this. Could someone put this in a context I might understand?
1
vote
1answer
318 views

Let $G$ be a connected graph, then $G$ is a tree iff $G$ has no cycles

Prove the following: Let $G$ be a connected graph, then $G$ is a tree $\iff$ $G$ has no cycles. $\Rightarrow$ If $G$ is connected and a tree then by the definition of tree it has no cycles. ...
1
vote
2answers
44 views

Changing the state of coins and finding the minimum number of steps to do it

I have $N$ coins all showing heads. At each turn, I change the state (i.e., a head is changed to a tail, vice versa) of $N-1$ coins. Prove that all the coins can end up showing tails if and only if ...
1
vote
1answer
83 views

Discrete Gauß and geodesic curvature

Imagine that you have an n-polygon $S$ and you wanted to calculated the discrete Gaussian or gedoesic curvature. How are they defined? If $p$ is a vertex of $S$ then Gauß-Bonnet suggests that the ...
1
vote
1answer
57 views

Are these two statements logically equivalent?

Are the statements $D \Rightarrow H \vee S$ and $(D \Rightarrow H) \vee (D \Rightarrow S)$ logically equivalent?
1
vote
1answer
137 views

Discrete Math - Determine the proposition is true or false. $\urcorner\left(p \vee q\right) \wedge \left(\urcorner q \vee r \right)$

Give that p is false and q is true and proposition r is false, determine whether the propositions are true. $\urcorner\left(p \vee q\right) \wedge \left(\urcorner q \vee r \right)$ Can I get some ...
1
vote
2answers
74 views

Discrete Math - Sets and Complements

I have the following problem: List the elements of the set $\overline{A\cap B}\cup C$, where $\overline{X}$ denotes the complement of an arbitrary set $X$ and $U$ denotes the universe under ...
1
vote
4answers
88 views

Using proof by contraposition to show that if $n\in\mathbb Z$ and $3n+2$ is even, then $n$ is even

I have my answer below but there is one step that I am not understanding...and maybe my brain is just not trained to understand it. Prove that if $n$ is an integer and $3n+2$ is even, then $n$ is ...
1
vote
2answers
199 views

What does this symbol mean?

This is from Discrete Mathematics and its Applications What is the symbol used in 9c, 9d, 9f, 10c, 10f, 10g? I looked through the chapter section and the closest symbol I saw to this is the subset, ...
1
vote
2answers
34 views

Confused on Conditional Statements

Write these propositions using $p$ and $q$ and logical connectives (inclduing negations) $p$: You drive over $65$ miles per hour. $q$: You get a speeding ticket You will get a speeding ticket if ...
1
vote
1answer
106 views

Time & Distance : Pokemon Hunter and the Rogue Brook

I was working my way through some Puzzles in Discrete Maths by Rosen, when I came across the following question: A Pokemon Hunter is rowing upstream a brook As he passes under the ...
1
vote
1answer
26 views

Expected Value of Changing Data

We have an 30 grenades. 1/3 grenades are useless. One soldier throw grenades at every 30 seconds in 3 minutes (i.e. throw 6 grandes). What is the expected value of all grenades successfully explode?
1
vote
1answer
30 views

Prove by induction that $\sum_{\varnothing\ne S\subseteq[n]}(\prod S)^{-1}=n$.

I'm having a hard time visualizing how to prove the following by induction: For every positive integer $n$, let $[n]$ denote the set $\{1,\ldots,n\}$. Let $A$ be a set. Use the notation $P(A)$ ...
1
vote
3answers
51 views

Permutation in discrete math

Is the permutation $$\begin{pmatrix} 1& 2 &3 &4 &5 &6&7 \\ 7 & 4 & 2 & 1 & 3 & 6 & 5 \end{pmatrix}$$ even or odd? The product of disjoint cycles is ...
1
vote
1answer
52 views

induction, recursive function, discrete mathematics

Please help solve following recursive function. How can I solve $n-10$ for $M(99)$ or $M(98)$ if $n>100$ ? : Find $M(99), M(100)$, and $M(98)$ when $$ M(n) = \begin{cases} n-10, & ...
1
vote
1answer
177 views

A number trick: determining the boxes from which the numbers were taken, given their sum

Mr. X is a famous magician. He has 1 to 100 cards at his disposal. He puts them in 3 different boxes-red,green,blue. Now, he requests the audience to blindfold him and select 1 card each from any 2 ...
1
vote
2answers
70 views

How many time the digit 6 appear when we count from 6(base 8) to 400 (base 8)?

How many time the digit 6 appear when we count from 6(base 8) to 400 (base 8)? I am not sure if I am going in the right path. I want to find the most accurate approach of solving this problem. ...
1
vote
2answers
87 views

methods of proof, discrete mathematics

"Disprove: For all integers $r, m,$ and $n$, if $r$ divides $mn$ then either $r$ divides $m$ or $r$ divides $n$." I am not sure if I am on the right track To disprove I try the negation of a ...
1
vote
2answers
139 views

Identifying if a relation is reflexive, symmetric and/or transitive

I am totally lost on how to identify if a relation is the above. The only thing I know if you have a matrix, and is diagonally symmetric, then it is symmetric, but I do not know why. Could someone ...
1
vote
2answers
44 views

Prove the relation on $\Bbb N \setminus \{0,1\}$ is a partial order

I'm a bit new to this material and trying understand some problem I'm solving Let $R$ be a relation on the set set = $ \{ N \setminus \{ 0,1\}\} $ that's defined like this: $aRb$ if there is an ...
1
vote
2answers
31 views

Describes Equivalence Classes

Let $R$ be the relation on the natural numbers defined by $(a,b)\in R$ if and only if $2\mid(a+b)$ I already proved this was an equivalence relation, but how do I determine the number of equivalence ...
1
vote
2answers
120 views

Help with understanding this proof in discrete mathematics?

This is the question and solution: Q: Prove that for any integer $a$, $2a + 1$ and $4a^2$ + 1 are relatively prime. A: Since $4a^2 + 1 = (2a − 1)(2a + 1) + 2$, any common divisor of $2a + 1$ and ...
1
vote
1answer
60 views

Expected Value Review Question Help; Discrete Mathematics

I'm studying for my discrete exam and I can't figure out this problem in the review, any help is appreciated. When Jane and Bob have a child, this child is a boy with probability 1/2 and a girl with ...
1
vote
1answer
293 views

Recurrence relation to find ternary strings that do not contains 3 consecutives 0's

I'm stuck and I can't find this recurrence relation which is : Find a recurrence relation that count the number of ternary strings $(0,1,2)$ of length n that do not contains three consecutives 0's. ...
1
vote
1answer
55 views

Arithmetics of cardinalities: if $A=C$ and $B=D$ then $A\times B=D\times C$

Suppose that $A, B, C$, and $D$ are sets with the cardinalities related as $A=C$ and $B=D$. Prove that the cardinality of $A\times B$ is equal to the cardinality of $D\times C$. I know that I must ...
1
vote
3answers
251 views

Discrete Structures : predicate logic (negations)

Could someone please explain why the negation makes "nobody" into "someone" and not "everyone" Which of the following is the correct negation for “Nobody is perfect.” 1. Everyone is imperfect. ...
1
vote
1answer
43 views

Write down the union and intersection of $100$ sets

I'm trying to solve the following exercise in elementary set theory. Let $A_i=\{-i,i+1,-i+2,...,i\}$. We are asked to explicitly find and write down $\bigcup_{i=1}^{100} A_i$ and ...
1
vote
1answer
654 views

Find the GCD and LCM of the factorials of two given numbers

Find $\gcd(20!, 12!)$ and $\text{lcm}(20!, 12!)$. My answer is: $20=2^2 \times 5$ $12=2^2 \times 3$ GCD $= 2^2 = 4$ LCM $= 2^2 \times 3 \times 5 = 60$ .... But my teacher said that this symbol ...
1
vote
1answer
67 views

Counting regions in a disk that has been cut by lines

Let $n$ be a positive integer, and $n$ lines drawn in a ring such that each one of them intersects with all of them, but no more than two intersect at one point. prove that the lines cut the disk ...