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

learn more… | top users | synonyms

1
vote
1answer
473 views

Probability and Counting

I have just picked up a text on discrete math and its been ages since I have done this so if anyone can show me with steps to correct my fault, that would be so great. Repair facility has 25 failed ...
2
votes
2answers
6k views

Proof by induction: $2^n > n^2$ for all integer $n$ greater than $4$ [duplicate]

I am a CS undergrad and I'm studying for the finals in college and I saw this question in an exercise list: Prove, using mathematical induction, that $2^n > n^2$ for all integer n greater than ...
1
vote
1answer
75 views

Counting Problem: Baseball problem

I am self studying statistics and having hard time with figuring this one out. In a baseball team, there are 15 players on its roster. How many ways are there to select 9 players for the starting ...
1
vote
1answer
48 views

Sets, Total Functions, Equality

Suppose you have finite Sets $A$, $B$, $C$. The function from $X \to_\text{total}Y$ represents a set of all of the total functions from set $X$ to set $Y$. Ex: Suppose $X$ is the set ...
3
votes
1answer
73 views

Proving $R$ is a Equivalence Relation?

The Relation: $\left\{R = ((m, n) |\ mn \geq 0\ \right\} on \ \mathbb{Z}$ apparently has an equivalence class. I can't really see it, I can see that reflexive does not fail. From the looks for it, ...
0
votes
2answers
99 views

Closed form for a summation with 3 factors in the summand fraction denominator

I'm studying for a Discrete Math exam and I'm preparing myself with an (unsolved) exam from a previous year. One of those exams had two exercises in a section of the Exam. The first exercise - that ...
1
vote
2answers
155 views

Prove that Hamming cube has a Hamiltonian cycle

How would one prove that all Hamming cubes with 2 or greater dimensions have a Hamiltonian cycle.
1
vote
1answer
89 views

Proof of a combinatorial identity$\binom{4n}{2}-4\binom{n}{2}=\binom{4}{2}n^2$ [closed]

I struggle to prove the combinatorial identity: $$\binom{4n}{2}-4\binom{n}{2}=\binom{4}{2}n^2.$$ The proof needs to be combinatorial, not algebraic.
0
votes
1answer
57 views

meaning of $C_4$ tree in graph theory

I was reading a paper. There a term was defined as $C_4$ tree. It was written that a graph is $C_n$ tree if it can b constructed from $C_n$ by a finite number of applications of the following theorem ...
0
votes
3answers
41 views

Random variable $X$ inducing a distribution on $V$

I have been learning about discrete probability and found a somehow confusing (to me) definition of distribution of a random variable $X$ on a set $V$. The definition of a Random variable $X$: $$ ...
0
votes
4answers
72 views

Divisibility for natural numbers

Prove that $(\forall n \in \Bbb N)(4 \mid 5^n-1 )$ I only know that if $ a \mid b \implies b =a \times q $ with $a,b,q \in \Bbb Z$ So(...) $4\mid5^n-1 \implies 5^n-1 = 4 \times q$ But I can't ...
26
votes
8answers
2k views

What is $\gcd(0,0)$?

What is the greatest common divisor of $0$ and $0$? On the one hand, Wolfram Alpha says that it is $0$; on the other hand, it also claims that $100$ divides $0$, so $100$ should be a greater common ...
3
votes
4answers
174 views

Why if $x^2$ is divisible by two then $x$ is divisible by $2$?

In the proof for "$\sqrt2$ is irrational" one of the steps goes like this: $a^2 = 2b^2$ From this we conclude that $a^2 \equiv 0 \mod 2 $ We don't stop here and infer that $a \equiv 0 \mod 2$ ...
1
vote
2answers
135 views

Equation for determining a car's fuel consumption as well as cost

Purchase price: 24000 Avg km/year: 40000 L/100 km: 5.3 Price of gas (per L):1.30 I was wondering what the formula is to find out how much litres of gas the car would consume as well as the cost of ...
1
vote
1answer
31 views

Relations properties

Let $\mathrm M = \Bbb R; \mathrm R = \{(x,y)\mid x = y\}$ Investigate wheter the relation is reflexive, transitive, symemtric, antisymmetric. Reflexivity $\rightarrow (\forall x \in \mathrm ...
3
votes
2answers
116 views

“Upper summation” binomial identity: different version from “Concrete Mathematics”

The book "Concrete Mathematics: A Foundation for Computer Science", 2nd Edition - authored by Ronald L. Graham, Donald E. Knuth, Oren Patashnik - has, in its page 174, a table called: "Table 174 The ...
0
votes
2answers
49 views

Justify a relation

let $\mathrm A = \Bbb Z \text{ and } R = \{(a,b) \in \mathrm A\times \mathrm A | a \lt b \}$ investigate whether the relationship is symmetric or antisymmetric. So (...) Symetric [...
2
votes
4answers
305 views

Proper subsets of $\{a,b,c,d\}$.

List the members of $\mathcal P\left(\{a, b, c, d\}\right)$ which are proper subsets of $\{a, b, c, d\}$. Sorry, I know this is basic, but I'm knew to this. I think the answer is just $\{a\}, \{b\}, ...
2
votes
1answer
56 views

Find $A_1,A_2, A_3, A_4$ such that $\lvert A_i \cap A_j\lvert = \lvert i-j \lvert$

Give example of four sets $A_1,A_2, A_3, A_4$ such that $\lvert A_i \cap A_j\lvert = \lvert i-j \lvert$ for every two integers $i$ and $j$ with $1\leq i < j \leq 4$. I was able to solve this ...
1
vote
3answers
135 views

Set Theory question

I have some exercises to prove different laws of set theory but my study guide does not provide any answers for the exercise. I have completed one of the exercises and just want to make sure I am ...
2
votes
1answer
141 views

approximation of sum of gaussian-like function?

Let: $g(u; x,s) = \dfrac{1}{s\sqrt{2\pi}} \exp\left(-\dfrac{1}{2} \left(\dfrac{x-u}{s}\right)^2\right)$ Where $x,s$ are parameters I'm looking for a closed-form solution or approximation of: ...
0
votes
1answer
252 views

Intro to proofs in real analysis 3

Prove that for real numbers $x,y$ with $x< y$, there is a rational and an irrational between $x$ and $y$ in the following cases: a) when $x< 0< y$; b) when $x< y \le 0$. For a) this is ...
1
vote
2answers
180 views

what to do next recurrence relation when solving exponential function?

find gernal solution of :$a_n = 5a_{n– 1} – 6a_{n –2} + 7^n$ Homogeneous solution: $a_n -5a_{n– 1} + 6a_{n –2} = 7^n$ put $a_n=b^n$ $b^n -5b^{n– 1} + 6b^{n –2} =0$ $b^{n-2} (b^2-5b^{} + 6b) =0$ ...
1
vote
1answer
52 views

Find generating function of given problem?

please help me to find the generating function of this problem $a_k = ( k + 1) for  k=0,1,2,3,...$
-1
votes
2answers
1k views

solve recurrence relation using mathematical induction?

solve recurrence relation $a_n = 6 a_{n–1} – 9 a_{n–2}$, where $a_0 = 1$ and $a_1 = 6$ and Verify, using Principle of Mathematical Induction, that $a_n = 3^n + n 3^n$. ans: i have done so far... put ...
-4
votes
3answers
196 views

In how many ways can $16 be divided among 4 people? [closed]

In how many ways can $16 be divided among 4 people, assuming that each person has to get something and there are 5 cent coins and up
3
votes
1answer
53 views

A bipartite graph question

Is there a bipartite graph with degrees $3,3,3,3,3,3,3,3,3,5,6,6$? I've been stuck attempting to draw this graph but keep getting lost. I think it is no, but I am not concrete about it. Is it no?
2
votes
2answers
65 views

A combinatorics problem

Given $A = \{a_0, a_1,...,a_m\}$ such that it's a subset of $\{1,2,...,n\}$ where $m>n/2$, and $a_0$ is the smallest number in $A$. Show that $A$ contains two numbers $b$ and $c$ such that ...
1
vote
1answer
129 views

Negating Logical Statement

I need help negating the following statement please, or if anyone could help putting it into words: $$\forall \epsilon > 0 (\exists _d>0(\forall x_0 (\forall x(|x - x_0| < d \implies |f(x) - ...
2
votes
1answer
65 views

How to derive a generating function for the following series

Given an integer n how would derive a function fn that is without conditional statements, does not use ...
2
votes
2answers
56 views

Need help with a pigeonhole problem

Let $X = \{x_0, x_1,...,x_m\}$ be a subset of $\{1,2,...,n\}$ where $m>n/2$, and $x_0$ is the smallest number in $X$. Use the pigeonhole principle to show that $X$ contains two numbers $b$ and $c$ ...
0
votes
1answer
957 views

how many symmetric relations are there on a set with 5 elements

I know that on a set with $n$ elements there are $2^{\frac12(n^2+n)}$ symmetric relations, but is it different on sets with specific number of elements?
1
vote
1answer
98 views

Calculating cardinal numbers of subsets in $\mathbb R\times\mathbb R$

Calculate the cardinal numbers of the following subsets of $\mathbb R\times\mathbb R$ : a.$X=\left\{ (a,b)\in\mathbb{R}\times\mathbb{R}\mid a+b\in\mathbb{Q}\right\} $ b.$Y=\left\{ ...
1
vote
1answer
104 views

Recursive and closed form solution for choosing $n$ pairs/triplets.. of $kn$ elements.

I stumbled apon an interesting question: How many ways are there to arrenge $kn$ elements into $n$ sets, $k$ elements each? There should be a recursive and closed form solution for $g_k(n)$. For ...
0
votes
1answer
99 views

How does one prove this equation?

How does one prove the following equation , I am getting confused about this, I can't seem to find any proving technique, I tried plugging in the Stirling's formula for factorials but to no avail - ...
1
vote
2answers
72 views

Propositional logic problem

Show that [ (p ∨ q) ∧ (p → r) ∧ (q → r) ] → r is a tautology (without a truth table). I am new to this, so I am not quite sure of how some rules can be used. Here is what I have so far: ...
3
votes
5answers
195 views

Question about set: When will $A = (A\setminus B) \cup B$?

Today , my professor has written a set formula which I don't fully understand: $$ A = (A\setminus B) \cup B $$ Please help me to fill in the missing details for the above, and its proof. My notes are ...
1
vote
2answers
120 views

Prove combinatoric inequality: ${n \choose {j+k}}\le {n \choose j}{{n-j}\choose k}$

How can one prove the following combinatoric inequality? $${n \choose {j+k}}\le {n \choose j}{{n-j}\choose k}$$ My line of thought was: $n$ people applied for an interview for a company. (And the ...
0
votes
1answer
43 views

Diffusion on a weighted graph

I have a weighted graph and want to apply a diffusion step to it. I read this paper, where they formulate such a diffusion step for unweighted graphs: $Z_i(t+1)=Z_i(t)+\alpha\sum_j ...
1
vote
2answers
415 views

Algebraic proof of $\sum_{i=0}^k{{n \choose i}{m \choose {k-i}}}= {{m+n}\choose k}$

I can't figure out an algebraic proof for the following identity: $$\sum_{i=0}^k{{n \choose i}{m \choose {k-i}}}= {{m+n}\choose k}$$ Combinatorical solution: We can see that as choosing some from ...
2
votes
2answers
133 views

Combinatorical proof $\sum_{k=0}^n{{2n+1}\choose k}=2^{2n}$

How to prove the following combinatorical identity using a combinatorical proof? $$\sum_{k=0}^n{{2n+1}\choose k}=2^{2n}$$ I solved it with an algebric proof with Newton's binomial and the symmetry ...
0
votes
1answer
110 views

Discrete mathematics poset

I have to prove this if and only if statement and I cant get anything written down.. Let le(X,≼) denote the number of linear extensions of a partially ordered set (X,≼). Prove le(X,≼)=1 if and only if ...
2
votes
1answer
245 views

Choosing numbers without consecutive numbers.

In how many ways can we choose $r$ numbers from $\{1,2,3,...,n\}$, In a way where we have no consecutive numbers in the set? (like $1,2$)
1
vote
2answers
150 views

Nine digit sequences with exactly one zero, two ones, three twos

I'm working on a problem where I am to find the number of nine digit sequences when there are exactly one zero, two ones and three twos. I worked up a solution, but is it correct? Here's my line of ...
0
votes
1answer
137 views

Defining bijective function $f:\mathbb{N}\times\mathbb N\to\mathbb N$ [duplicate]

I want to prove that $\mathbb N\times \mathbb N$ is countable set using cantor first diagonal method: where every-time we count the elemnts on the digonal with the direction of the arrow ...
1
vote
2answers
208 views

Cartesian product subset

Given a set X = {$\varnothing$, {a, b}, {a} }, what is Cartesian product of X $\times$ X ? I think X $\times$ X should be {$\varnothing$, ({a,b},{a,b}) , ({a,b},{a}) , ({a},{a,b}) ,({a},{a}) }. Is ...
1
vote
1answer
420 views

Well ordering principle vs induction proof

I was asked to recast an induction proof to a proof by well ordering princple. How are the 2 different? From my understanding the two are equivalent, so how will the proof be different? Thanks!
0
votes
1answer
44 views

Converting symbols to English: $(\forall x)D(x)$, $(\exists x)D(x)$, $\lnot (\exists x)D(x)$, $(\exists x)\lnot (Dx)$

The domain is all penguins. D(x) = "x is dangerous" $(\forall x)D(x)$ All penguins are dangerous $(\exists x)D(x)$ Some penguins are dangerous $\lnot (\exists x)D(x)$ There is not a penguin ...
-1
votes
1answer
110 views

Using “n is odd if n=2k+1” , explain why 2n+7 is an odd integer.

Using "n is odd if n=2k+1", explain why 2n+7 is an odd integer. I don't know if this is what is asked for, I would just say because 1 is an odd integer and 7 is an odd integer, 2n+7 has to be an odd ...
0
votes
1answer
41 views

Proof that if $a \mid b \Rightarrow |a| \le |b| $

$\text{let } a,b, c \in \Bbb Z \text{ such that } |a| > |b| \land a\mid b \text{ then, by definition, } a \mid b \Rightarrow b = ac \Rightarrow |b| = |ac| \text{ but } |a| > |b| \Rightarrow |ac| ...