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
7answers
53 views

Proving $\frac{n}{n+1} < \frac{n+1}{n+2}$ by induction?

I have the inequality $\frac{n}{n+1} < \frac{n+1}{n+2}$ I'm not sure how to go about proving it. I've started by testing with n = 1, which results in $\frac{1}{2} < \frac{2}{3}$ which is true ...
1
vote
2answers
24 views

Recall that $ p \rightarrow \sim q$ is equivalent to $p \land \sim q$, how can this be used as an explanation for how to use proof by contradiction.

Recall that $p \rightarrow \sim q$ is equivalent to $p \land \sim q$, how can this equivalence be used as an explanation for how to use proof by contradiction. I'm having a hard time answering this ...
0
votes
2answers
25 views

Any collection of n coins can be obtained using a combination of 3¢ and 5¢ coins where n ≥ 14

I am trying to prove this statement with strong induction, but I'm a little lost on the inductive step. Proposition: Let P(n) be the sentence ‘any collection of n coins can be obtained using a ...
0
votes
1answer
25 views

How can i find equation that does not have a solution?

An operation $*$ is defined on the set $\Bbb{Z} \times \Bbb{Z}$, ie. the set containing all pairs of integers by: $$ (u,v) * (x,y)=(u+x,v \cdot y) $$ if $(\Bbb{Z} \times \Bbb{Z}, *)$ is not a group ...
1
vote
0answers
23 views

Discrete math: What is the difference between false and inverse in conditional statemensts?

Let's say there is this conditional statement: If I am in Paris, then I am in France. So, p = 'I am in Paris', and q = 'I am in France' I do not understand when p and q are false, how would that ...
0
votes
0answers
10 views

$∀ Z^+$ can be written as $c_r * 3^r + c_{r-1} * 3^{r-1} + …. + c_2 * 3^2 + c_1 * 3 + c_0$

I am trying to prove the following statement: $∀ Z^+$ can be written as $c_r * 3^r + c_{r-1} * 3^{r-1} + …. + c_2 * 3^2 + c_1 * 3 + c_0$ where $c_r =$ 1 or 2, and $c_i$ = 0, 1, or 2 for all integers ...
1
vote
3answers
46 views

How to prove that $A⊆B$ means that $A∪B=B$ [duplicate]

How does one prove that $A⊆B$ means that $A∪B=B$ ? I can understand it in my head but I don't know how you'd put down in logic notation.
0
votes
1answer
9 views

How to solve a parameteric linear equation in Zn?

Given monoid ($\Bbb{Z}$124, ⋅ ) and a parametric equation with parameter $a$ where $ax+2=5(x+a)-1$ Give the number of parameters $a$ belong $\Bbb{Z}$124 for which the above equation has precisely ...
1
vote
1answer
16 views

How can I show that an argument or proposition is valid through logic proof sequence?

I know the logic of proof sequence as I solved many proof problems, I now have one that has been taken my attention for a couple of days and as easy as it may look, I don't seem able to simplify the ...
0
votes
1answer
13 views

convert Hex value to two's Complement

for example, let's say: 0xE5 assume the system is 8 -bit in decimal it's = 229 and in Binary it's = 1110 0101 the Two's Complement rules said: sign-bit, which's the most left, indicates a negative ...
1
vote
1answer
16 views

Rewrite the following in symbolic forms using $\sim, \land, \lor $.

Let $h = $"Peter is handsome", $c = $"Peter is clever", $o = $"Peter is optimistic". Rewrite the following in symbolic forms using $ \sim , \land, \lor $. -Peter is neither handsome, clever nor ...
0
votes
1answer
20 views

Prove that $\sum_{i=0}^{k} \lg \frac{n}{2^i} = \Theta(\lg^2 n)$

Show that if $n$ is a power of $2$, say $n = 2^k$, then we have the equality $\sum_{i=0}^{k} \lg \frac{n}{2^i} = \Theta(\lg^2 n)$. The first step is to prove $O(\lg^2n)$: $$ \lg \frac{2^k}{2^0} + \lg ...
1
vote
1answer
21 views

How can i find all invertible elements?

An operation $*$ is defined on the set $\Bbb{Z} \times \Bbb{Z}$, ie. the set containing all pairs of integers by: $$ (u,v) * (x,y)=(u+x,v \cdot y) $$ What are all the invertible elements of the ...
0
votes
0answers
20 views

Can you show a proof of Unique Factorization of Integers Theorem (Fundamental Theorem of Arithmetic)?

I understand the proof of "Any integer greater than 1 is divisible by a prime number" by strong mathematical induction. But I don't understand why Unique Factorization of Integers Theorem follows ...
1
vote
4answers
60 views

If $a > 0$,$b>0$, and $\frac{1}{a} + \frac{1}{b}$ is an integer, prove that $a=b$. And show that $a = 1$ or $2$

If $a$ and $b$ are positive integers, and $\frac{1}{a} + \frac{1}{b}$ is an integer, prove that $a=b$. And show that $a = 1$ or $2$ -I played around with numbers and the conditions and it seems that ...
0
votes
0answers
21 views

Integral solution of equation $Ax + By = z$ with contraints on $x, y, z$

Given $x$, $y$ and $z$, how can I check if there exists integral solution of $$Ax + By = z$$ Such that : if $x > y$, $A$ must be positive and $z \geq y$ ( Given ) if $y > x$, $B$ must be ...
2
votes
3answers
125 views

Can the cardinality of a power set ever be odd? [on hold]

Can the cardinality of a power set ever be odd? If it can, what conditions must be met?
2
votes
2answers
7k views

How many solutions are there to the equation $x + y + z + w = 17$?

How many solutions are there to the equation $x + y + z + w = 17$ for non-negative integers $w, x, y, z$ ? I don't know if I'm doing this right, but I guessed that the solution would be ...
4
votes
2answers
33 views

What is the probability that these two objects are of the same color?

We have $11$ bins with $10$ objects each. Every object is either black or white, and the $i$th bin ($1 \le i \le 11$) has precisely $(i -1)$ black objects in it. Someone selects, uniformly at random, ...
0
votes
0answers
65 views

Find number of rectangles

There is $N\times M$ grid present with numbering as $1,2,\cdots,NM$ (numbering is done row wise. 1st row will contain number from $1,\cdots,M$, second row will contain $M+1,\cdots,2M$ and so on). ...
2
votes
3answers
35 views

If $\gcd(a, c) = 1$ and $b | c$, prove that $(a, b) = 1$

If $\gcd(a, c) = 1$ and $b \mid c$, prove that $(a, b) = 1$ -Not sure how to approach this problem. -We have just started the greatest common divisor section, and looking at my notes I see that ...
1
vote
1answer
35 views

If $m | (8n +7)$, $m | (6n + 5)$, prove that $m = ± 1$

If $m | (8n + 7)$, $m | (6n + 5)$,prove that $m = ± 1$ -We have just starting going over the "divides" notation, and I am aware of a few properties and theorems from my notes. I am; although, a bit ...
3
votes
3answers
32 views

If a is an integer, prove that $gcd(14a + 3, 21a + 4) = 1$

If a is an integer, prove that $gcd(14a + 3, 21a + 4) = 1$ -We have just started the section on greatest common divisor, one thing I know is that $gcd(a,b) = ax + by$ -My initial thought is that we ...
2
votes
1answer
32 views

Are these two events $A$ and $B$ independent?

Abe and Bernard are dealt five cards each from the same $52$ card deck. Let $A$ be the event that Abe gets a flush (five cards of the same suit) and $B$ be the event that Bernard’s five cards are of ...
0
votes
1answer
12 views

How can i show a pair forms a semigroup?

An operation . is defined on the set $Z×Z$, ie. the set containing all pairs of integers by: $(u,v).(x,y)=(u+v,v.y)$ How can i show that the pair ($Z×Z$, . ) forms a semigroup?
-1
votes
0answers
18 views

How can i find a semigroup?

An operation * is defined on the set $\mathbb{Z} \times \mathbb{Z}$, ie. the set containing all pairs of integers by: (u,v)*(x,y)=(u+v,v*y) How can i show that ...
3
votes
2answers
174 views

Does anyone recognize this sequence?

I was wondering if anyone has come across this sequence and if so if they have a formula for it. $$\frac{1}{2},\ \frac{1}{6},\ \frac{2}{30},\ \frac{8}{210},\ \frac{48}{2310},\ \frac{480}{30030},\ ...
0
votes
2answers
29 views

Find a solution $x\in\mathbb{Z_{\mathrm{784}}}$ for $x\cdot\overline{602}=\overline{308}$

I know that I have to find a positive integer $x$ that I can multiply with $602$ and then divide the result by $784$ so that the remainder of that integer division is $308$. I am sure that this is ...
1
vote
1answer
14 views

Translate quantification into English and give the truth value

The problem is: $\exists x \in \mathbb{R} (x^3 = -1)$ I understand the following: $\exists x$ = There exists an $x$ $\in$ = shows the element before it is a member of a set after it $\mathbb{R}$ = ...
2
votes
1answer
33 views

In how many ways can we pick a group of 3 different numbers from the group $1, 2, 3, …, 500$ such that one number is the average of the other two?

Here's the question which I'm struggling with - In how many ways can we pick a group of 3 different numbers from the group $1, 2, 3, ..., 500$ such that one number is the average of the ...
4
votes
2answers
110 views

What am I counting wrong?

EDIT: I made a mistake in the beginning, the second condition has changed. Sorry for this. I'm asked to count the number of sets of 4 elements that satisfy the two following conditions: 1) Each ...
1
vote
1answer
20 views

equivalence relation and quotient set, Given $A = \{0,1,2,3,4,5\}$

Given $A = \{0,1,2,3,4,5\}$, Write the appropriate equivalence relation of this quotient set: $$A/_R = \{\{1,2\},\{3\},\{4,0,5\}\}$$ Well, if it was to compute $$A/_R = ...
4
votes
2answers
33 views

Pair of friends and a pair of “enemies” in each group of three students

The problem: There is a class. In each group of three students in the class there is a pair of friends and a pair of "enemies". Find the maximum number of students in the class. I tried to play with ...
2
votes
2answers
62 views

Example of a relation on $X$?

I can understand "relation $R$ in $X$" through the following example in the book, but I haven't got a clue of what "relation on $X$" looks like. Can you give an example of of a relation on $X$? ...
0
votes
1answer
22 views

If P(i) is true for all integers i with 2≤i≤k as inductive hypothesis, then why also p(t) is true by the inductive hypothesis?

"Let P(n) be the property n is divisible by a prime number. We prove that P(n) is true for all integers n with n> 1. Basis step. If n=2, then P(n) is true because 2 is a prime and every ...
0
votes
1answer
20 views

Determining if Argument is Valid via Short-Cut Method

I understand there are two ways to determine validity of an argument. The first way is to construct a truth table and if the statement consisting of the premises combined together implying the ...
0
votes
2answers
31 views

Discrete Math: Determining if Argument is Valid

I understand there are two ways to determine validity of an argument. The first way is to construct a truth table and if the statement consisting of the premises combined together implying the ...
0
votes
0answers
15 views

Small graphs containing all trees on $n$ vertices

What do those graphs look like which contain a copy of every tree on $n$ vertices and such that no proper subgraph has this property?
0
votes
1answer
39 views

Mathematical induction condition “p(k)$\Rightarrow$p(k+1)” for the divisibility by a prime number

" Mathematical induction If p(n) is a statement involving the natural number n such that: p(1) is true, and p(k)$\Rightarrow$p(k+1) for any arbitrary natural number k, then p(n) is true ...
0
votes
3answers
47 views

How did $-(2^{k-1})-(2^{k-2}) -\dotsb-(2^0)$ become $-2^k+1$?

I have a question, how was the geometric series collapsed to be in the form of $2^{k+1}$?
1
vote
2answers
37 views

Proof with Combinatorial Argument $\sum_{i = 1}^{n} (i-1) = nC2$

I am trying to prove below equation with combinatorial argument but I have no idea how this works. $$\sum_{i = 1}^{n} (i-1) = nC2$$ Can anyone give me a clue?
0
votes
1answer
641 views

Y-Axis units on FFT graph

A 50Hz sinusoid wave with a voltage range of +/-20V is sampled at 512Hz for 1 second. No bias or phase shift are present. The signal is run through an FFT. The result is one spike at 50Hz on the ...
3
votes
3answers
42 views

Simplify $(k +1)! > (k + 1)^2$ to prove true for $k ≥ 4$

I am trying to prove this statement is true for $k ≥ 4$. I don't know how to work with $k + 1$ factorial, so I'm a little lost on proving this.
1
vote
2answers
16 views

Prove equivalence ratio and find class of $B\subseteq A$ , $X \sim Y \Leftrightarrow X \cap B = Y \cap B$

Prove equivalence ratio and find class of $B\subseteq A$ , $X \sim Y \Leftrightarrow X \cap B = Y \cap B$. Well, I've proved really easily that it is reflexsive, symmetrical and transitive. But I'm ...
2
votes
3answers
53 views

Can I further simplify $5^k \cdot 5 + 9 < 6^k \cdot 6$ to prove this is true

I am trying to prove this statement, but I'm not sure where to go from here. Is don't think this is sufficiently reduced to conclude the statement is true, but I'm not positive. $k ≥ 2$ Can I ...
-1
votes
0answers
26 views

Number of solutions of equation with natural numbers [on hold]

Given natural numbers $s, n, k$. How to find number of solutions to equation $a_1 + a_2 + \ldots + a_s = n-s$ where $0 \leq a_i \leq k-1$ and $a_i \in \mathbb{N}$?
0
votes
3answers
47 views

Prove $n^3 + 7n + 3$ is divisible by 3 for all integers n ≥ 0

The statement I'm trying to prove is: $n^3 + 7n + 3$ is divisible by 3 for all integers n ≥ 0 I eventually need to prove $(k + 1)^3 + 7(k + 1) + 3$ is divisible by 3. I don't really understand ...
2
votes
1answer
45 views

Proving that a function grows faster than another

I'm told to prove or disprove that $4^{\sqrt{n}}$ grows faster than $\sqrt{4^n}$ As n tends to infinity. From my Previous years Calculus I know that if I take the derivative of two functions, and one ...
1
vote
2answers
40 views

Guide to solving Harary's exercises

Most of Harary's harder exercises are research problems (although solved), that need almost always a single key idea as a breakthrough. Often it so happens that even after thinking for a long time no ...
-1
votes
0answers
43 views

Closed form for $\left(\sum_{k=0}^n\frac{x^k}{k!}\right)^p$

The expression for the p-th power of the sum of the first $n+1$ powers of x is given analytically by ...