Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

3
votes
2answers
84 views

How many tuples of numbers from [1..n] have the sum of its elements equal to n?

[1..n] is the set of integers from 1 to n. The tuples can be of any finite length. The length of each tuple should range from 1 to n. I am asking how many tuples have elements such that the total sum ...
0
votes
1answer
29 views

Show that $\frac{a^{n+2} - 1}{a - 1}=\frac{a^{n+1} - 1}{a - 1} + (n + 1)$ [on hold]

How can I show that \[ \frac{a^{n+2} - 1}{a - 1}=\frac{a^{n+1} - 1}{a - 1} + (n + 1) \]
0
votes
0answers
23 views

Applying De Morgan's Law

I'm working on my assignment for Discrete Math and I'm not fully understanding how to do this question for it so I was wondering if anyone here could help show me how to do it properly; Use De ...
1
vote
1answer
38 views

Is ∃xP(x) ∨ ∃xQ(x) the same as ∃xP(x) ∨ ∃yQ(y)?

Very simple question: is ∃xP(x) ∨ ∃xQ(x)the same as ∃xP(x) ∨ ∃yQ(y) Thank you.
3
votes
1answer
13 views

Question about Growth Rates

I see in some notes from my instructor in Algorithm course that $\Sigma_{i=0}^{log n} (n/2^i)$ has growth bigger than $\Sigma_{i=1}^{n} (i log i)$. i couldn't understand why? any tutorial or hint?
3
votes
1answer
42 views

Let a,b,c be integers. Prove that if a|c and b|c, then either a|b or b|a.

Let a,b,c be integers. Prove that if a|c and b|c, then either a|b or b|a. Any ideas? (Suggested proof by contradiction). Not really sure how to go about this.
0
votes
3answers
41 views

Turn 6 cards upside down

Six identical cards are placed on a table. Each card has number '1' marked on one side and '2' on the other. All cards are placed with '1' facing upward on a table. In one try, exactly four cards ...
-1
votes
2answers
20 views

Is there any compact notation for the count [on hold]

Can any one suggest what is the best compact notation that I can use for the following pseudo problem. I think it is simple counting with some constraints but don't know if is there any notation for ...
0
votes
1answer
18 views

Find the coefficient of $x^1y^7$ in the expansion of $(2x−y)^8$.

I was doing practice problems for a discrete math class and came across this one which has stumped me. I know that if the problem was "Find the coefficient of x^1y^7 in the expansion of $(x−y)^8$" the ...
0
votes
1answer
13 views

Let n be an arbitrary natural number and let the property P(n) be the equation 2 · 6 · 10 · 14 · … · (4n - 2) = (2n)! / n!

Here's my proof: Base Case: Show that P(1) is true: n = 1 (4(1) - 2) = (2(1))! / (1)! 4 - 2 = 2! / 1 2 = 2 The base case holds. Induction Step: Show that for all natural numbers k, if P(k) is ...
0
votes
2answers
22 views

Greedy Algorithm, Fewest overlaps

Hi I need help doing this problem. I've been working on it for like 2 hours now and I'm no where. I'm literally about to throw my computer. I've watched youtube videos, reread my notes. The homework ...
0
votes
1answer
24 views

Geometric series for values between 0 and 1

I am given that geometric series is defined as the following $1-x+x^2-x^3+x^4$ for values in range $0<x<1$. I am also told expected value can be calculated by using the following equation: ...
0
votes
0answers
22 views

Bijectivity of a function $f(i,j)=\frac{(i+j)(i+j+1)}{2}+j$

Define $f\colon \mathbb N\times \mathbb N \rightarrow \mathbb N$ by $f(i,j)=\frac{(i+j)(i+j+1)}{2}+j$. how can I prove that f is bijective help please! I should prove that f is surjective and ...
1
vote
2answers
17 views

Recurrence problem with a game of probability [duplicate]

Fair coin flipping (50% on both sides) $P_1$ and $P_2$ plays a few games of fair coin flipping. Assume player $A$ starts with $x$ coins and player $B$ with $y$ coins. Let $P_n$ denote the ...
-5
votes
1answer
83 views

Are variables the same in pure mathematics???

my question is In pure mathematics, $x$ always $=x$ $x = x$, the variables are abstract. In modelling, $t$ could mean the time that has elapsed since you started a machine for example. Or ...
1
vote
1answer
35 views

Prove using structural induction?

First off: I am not sure if I have posted to the correct site, but I am quite lost with this question. I am in a theory of computation class after taking 1.5 years off school and we are on ...
0
votes
1answer
58 views

Gambler's ruin and coin toss

Edit 3. Fixed question to be more clear and include current solution Problem Two players player 1 and player 2 plays a game of fair coin flipping. Player 1 starts with $A$ coins and Player 2 with ...
1
vote
3answers
26 views

Proof with inequalities and a function

I need help approaching a proof which deals with inequalities: If p and r are the precision and recall of a test, then the F1 measure of the test is defined to be $$F(p, r) = \frac{2pr}{p+r}$$ Prove ...
1
vote
2answers
25 views

The difference between the statements $“\forall x \exists y y > x”$ and $“\exists y \forall x y> x”$

I have here an explanation for the difference between the two statements but I don't understand something in it. The first statement says that for each positive integer $x$, there is a larger positive ...
0
votes
1answer
42 views

Use the following definitions to give a careful proof that, for every binary string x, $(x^C)^R = (x^R)^C$

If $ w : \{{1...l}\} \rightarrow \{{0,1}\} $ is a binary string, the complement of $w$, denoted $w^C$, is the string of length $l$ defined by $w^C(i) = 1 - w(i)$. The reverse of $w$, denoted $w^R$, is ...
0
votes
1answer
17 views

Discrete Math: Which of the following statements is right and wrong

a) ∀x F(x) ∧ ∀x G(x) ≡ ∀x (F(x) ∧ G(x)) b) ∀x F(x) ∨ ∀x G(x) ≡ ∀x (F(x) ∨ G(x)) c) ∃x F(x) ∧ ∃x G(x) ≡ ∃x (F(x) ∧ G(x)) d) ∃x F(x) ∨ ∃x G(x) ≡ ∃x (F(x) ∨ G(x)) This is Discrete Mathematics. the ...
0
votes
0answers
17 views

number of ways to make a grid 2/3 [on hold]

in 2 × m grids we want to move from (1, 1) to (2, m) using the following rules : moving one step up or one step right or one step down. if we move down then we can not move up immediately. if we move ...
0
votes
1answer
42 views

Finding the integers between {1, 2, …, 100} that are divisible by 2 or 3 but not both.

I'm having trouble determining this problem. I need to find the integers in the set {1, ... , 100} that are divisible by 2 or 3 but not both. The way I tried to approach it was: If a number is ...
0
votes
0answers
19 views

Congruence $\bmod k$ with two unknown variables

I need help with an exercise: Suppose that $n$ is an integer and $$n^4 \equiv p \pmod 5$$ I need to find the possible values for $p$ such that the equivalence holds. I'm not even sure how to ...
1
vote
2answers
22 views

Evaluating modulos with large powers

I need some help evaluating: $$13^{200} (mod \ 6)$$ What I've been trying to do: $$13^1 \equiv 1 (mod \ 6)$$ $$13^2 \equiv 1 (mod \ 6)$$ Can I just say that: $$13^{200} = 13^2 * 13^2 * ... * 13^2 ...
0
votes
1answer
21 views

Prove boundedness of recurrence relation

For a number sequence $\{y_n\}$ we know that $y_{n+1} = 2y_n-y^2_n$ If: $0<y_0<1$ show that $0<y_n<1$ for all integers $n>0$ I've tried solving the recurrence relation, but I couldn't ...
0
votes
0answers
10 views

Universal Set and Empty Set within membership tables

If I were to do proofs within a membership table and needed to make a column for both the universal set as well as the empty set, would I be correct in assuming all rows under the universal set are 1 ...
-2
votes
1answer
21 views

Get unknown value in discrete random variable

Let $X$ be a discrete random variable (i) Assume that the PMF of $X$ is given by $$\operatorname{Pr}(X=x)=\begin{cases}kx^{2} & x \in \{-4,-2,0,2,4\} \\ 0 & x\not\in \{-4, -2, 0, 2, ...
-2
votes
0answers
10 views

A car drivers income consists of his salary and tips.his salary is TK 50 a week [on hold]

A car drivers income consists of his salary and tips.his salary is TK 50 a week .during one week his tips were 5/4 of his salary.What fraction of his income for the week came from tips?
2
votes
3answers
80 views

Solving a recurrence relation of second order

I have a pattern, which goes: $x_n =2(x_{n-1}-x_{n-2})+x_{n-1}$ and this pattern holds for all $n \ge 2$. I also know that $x_0 = 1 \ and \ x_1 = 5.$ $x_2 = 2(x_1-x_0)+x_1$ $\begin{align} x_3 = ...
1
vote
2answers
31 views

$p ⇒ (q∨r) ≡ (p∧(\neg r)) ⇒ q$ are logical equivalent?

I have determine whether the following equivalence is true or not $$p ⇒ (q∨r) ≡ (p∧(\neg r)) ⇒ q$$ using logical equivalences definitions. I am never able to do these sorts of questions correctly no ...
0
votes
0answers
23 views

Show that a relation is a partial order with lubs and glbs of all pairs

I came across this question while doing my discrete mathematics and couldn't understand it completely. The question is as follows: Let $(N, ≤) $ be the set of natural numbers with the relation $ m ≤ ...
0
votes
3answers
19 views

Game Theory Voting Utilities

! So far, I've managed to come up with this solution: ! But as far as here...I can convert this into payoffs, however I'm unsure of how to figure out the Nash equilibria as when we convert from ...
1
vote
2answers
90 views

How do you make the coefficients of the simple linear combination of the gcd positive?

I was trying to convert a simple linear combination (and gcd): $$gcd(a,b) = ax + by$$ To have positive coefficients. I did read the following here but didn't really understand it and was looking ...
2
votes
1answer
44 views

How big are Kostka-Numbers

Let $n\in\mathbf{N}$ and $\lambda=(\lambda_1,\ldots,\lambda_\ell)$ be integers such that $\sum_{i=1}^\ell\lambda_i=n$. To this partition consider the Schur-Polynomial $s_\lambda$. When expressed in ...
1
vote
1answer
24 views

raBinomial distribution with dependent trials?

I need your help with following problem: String with n characters is given. For each character in string there is probability p that it is wrong. Now you take a sliding window of length k, k<= n, ...
0
votes
0answers
29 views

How to write a formal proof of the statement: For all integers p, m, n, if p|m and p|n then p|(m+n)

Prove: For all integers $p$, $m$, $n$, if $p|m$ and $p|n$ then $p|(m+n)$ Proof: Let $p,m,n \in \mathbb{Z}$. Suppose $p|m$ and $p|n$. Then $\exists x,y\in \mathbb{Z}$ such that $m = px$ and $n = ...
0
votes
0answers
21 views

CRT Algorithm using InvMod + Undefined

I am trying to implement a modified CRT function in c++ that calls a function called invMod which is simply the inverse modulus function. I am having difficulty randomly generating values while ...
2
votes
2answers
46 views

Integration of dirac function explanation

I have a problem that need your help. I have a gray image. We denotes $I(x)$ is gray level of a pixel in the image and $f(z)$ is a function of $z$(ie: histogram function...)-where $z$ is the set of ...
-1
votes
0answers
22 views

Entropy of sum of two dependent random variables [on hold]

What is the entropy of sum of two dependent random variables, $$h(X+Y)$$ when X y Y have the same distribution. In particular, is it larger or smaller than the entropy of the sum of two ...
0
votes
0answers
46 views

Determine whether the set is finite or infinite. If the set is finite, write down explicit list of all the elements. If the set is infinite, say so.

Determine whether the set is finite or infinite. If the set is finite, write down explicit list of all the elements. If the set is infinite, say so and list five laments of the set. $A = \{ n \in ...
1
vote
1answer
25 views

Proof that falling power can be converted to sum of normal powers

I'm trying to follow a proof that any falling power can be converted to a sum of multiples of regular powers, i.e. $x^{\underline{n} = \sum_{k=0}^n s_{n,k}x^k}$ with $s_{n,n}=1$ and $s_{n,0}=0$ for ...
1
vote
1answer
27 views

Exponential growth with a constant

Some guy opens a bank account with an initial amount of $\$1,000$. Each month he deposits $\$200$ and the bank gives him a monthly interest of $6\%$. I want to find the closed formula. Given this, we ...
0
votes
0answers
24 views

Stat problem! Why is this? [duplicate]

This is a statistics problem. although this is not a problem which needs an answer, I want to know the reason Why this is right. Can you guys help me ? Thanks in advance!
0
votes
3answers
57 views

Need help solving a Venn Diagram

I am trying to figure out how to solve this Venn diagram problem for my Discrete Mathematics class. So the problem goes like this: In a school there are 420 students. 300 of them have gone to school ...
0
votes
1answer
19 views

Algebra of sets application

In the problem below algebra of sets is being evaluated, Venn diagrams are allowed. There's a Modern Languages reading exam where 200 students are being evaluated. The exam content is in French, ...
0
votes
1answer
41 views

Greatest Common Divisor problems [on hold]

I've been finding difficult with these questions. Decide if the following assertion is true or false, and provide clear arguments for your answer: The assertion is that for all natural numbers $n,m$ ...
1
vote
1answer
30 views

Trying to wrap my head around the idea of Proving Rule of Cases is a valid arument

I had a question on my assignment today that asked to "Prove that the Rule of Proof by Cases is a valid argument." Based of what I've read, Proof by Cases is valid when all cases produce the same ...
0
votes
1answer
17 views

How to approach conversions of statements using predicates, quantifiers, and logical connectives.

I have an example problem where I must use predicates, quantifiers, and logical connectives to convert the statements. The statement is... ...
1
vote
1answer
22 views

Extend an acyclic relation to an ordering

I am pre-studying a course (Discrete Mathematics) that I will be taking come fall quarter this October. We are using the textbook Invitation to Discrete Mathematics and I am having trouble starting to ...