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

4
votes
3answers
46 views

In every set of $14$ integers there are two that their difference is divisible by $13$

Prove that in every set of $14$ integers there are two that their difference is divisible by $13$ The proof goes like this, there are $13$ remainders by dividing by $13$, there are $14$ numbers ...
1
vote
0answers
17 views

Finding the supremum and infimum of subsets of $\mathbb{R}$

For the following subsets of $\mathbb{R}$, give their supremum, maximum, infimum, and minimum, if they exist. Otherwise, indicate that they do not exist. ...
2
votes
3answers
55 views

How to prove $\sum\limits_{i=0}^n (-1)^i \binom{n}{i} \binom{n-i}{k}=0$

I would like to prove that: \begin{equation*} \sum\limits_{i=0}^n (-1)^i \binom{n}{i} \binom{n-i}{k}=0;~k\geq0 ; n\geq1. \end{equation*} Can any one help me how to do that? Thanks
-1
votes
0answers
10 views

How to prove that this system of boolean functions is functionally complete? [on hold]

How to prove that this system of boolean functions is functionally complete using other systems of boolean functions. Express operators from a functionally complete set with functions from my set: ...
0
votes
1answer
14 views

Counting using modulo (discrete problem)

I am having trouble with my discrete h/w. I (kinda) understand the problem but I am stuck on how to write/format the solution. Please help! 16. a) To each integer $n$ we assign an ordered pair ...
1
vote
1answer
38 views

covering subsets

Let $A=\left\{ {1, 2, \ldots, n}\right\}$. Let $B$ be the set of all size $m$ subsets of $A$. $B=\left\{{B_1,B_2, \ldots , B_{\binom{n}{m}} } \right\}$, $ |B_i|=m$ then we want to find $k$ subsets ...
-4
votes
0answers
34 views

Proving that 2 intervals have the same cardinality [on hold]

How can I Prove that the invervals [0, 1) and (0, 2] have the same cardinality by finding a bijection between them? And how can I Prove that the intervals (0, 1) and [0, 1] have the same cardinality ...
0
votes
3answers
56 views

Prove that if $A \mathbin{\triangle} C = B \mathbin{\triangle} C$, then $A = B$ [duplicate]

I know what I'm supposed to do. Since $A \mathbin{\triangle} C = B \mathbin{\triangle} C \Longrightarrow (A-C) \cup (C - A) = (B- C) \cup (C - B)$ Prove $A$ is a subset of $B$: Let $x$ be an ...
0
votes
1answer
19 views

Gaussian elimination problem

$$x_1 + 10x_2 − 3x_3 = 8$$ $$x_1 + 10x_2 + 2x_3 = 13$$ $$x_1 + 4x_2 + 2x_3 = 7$$ when making 2nd and 3rd 1st columns 0 using Gaussian elimination, the second row second column also becomes zero, so ...
1
vote
0answers
18 views

Translation of English statements to logical expression using nested quantifier and predicates.

I have come across few doubts solving Exercise of Propositional logic and predicates. Here are they, Doubt 1 ...
2
votes
3answers
60 views

Evaluate $7^{8^9}\mod 100$

I'm preparing myself for discrete math exam and here's one of the preparation problems: Evaluate $$7^{8^9}\mod 100$$ Here's my solution: $7^2\equiv49 \mod 100\implies (7^2)^2\equiv49^2=2401\equiv ...
-5
votes
0answers
15 views

discrete mathematics matrix relation proof [on hold]

Show that if MR is the matrix representing the relation R, then M[n] R is the matrix representing the relation Rn.
-1
votes
2answers
20 views

Reflexive, Symmetric, Anti Symmetric and Transitive

I am really struggling with these concepts. I understand the basic principle, but cannot really find a situation where something is not reflexive, symmetric or transitive. (Clearly I don't understand ...
-3
votes
0answers
35 views

SimRank Example? [on hold]

By using Similarity in SimRank as shown by this formula $$ s(u,v)= \left(\frac{C}{|I(u)||I(v)|}\right). \sum_{x\in I(u) } \sum_{y\in I(v) }s(x,y) $$ How can we find SimRank between 5,4 ? or s(5,4), ...
1
vote
3answers
89 views

Prove $\frac{1}{n} =\frac{1}{n+1}+\frac{1}{n(n+1)}$ for all integers $n\in\Bbb Z$

I'm pretty sure that we need induction, since it's the format I had to use for previous problems similar to this (it isn't specified that it HAS to be an inductive proof, either, if there is another ...
0
votes
1answer
60 views

Proving set identities

I am attempting to work on some proofs for my math assignment, but I'll be honest in that I am really struggling to understand them. I read through the power point given by my teacher; however, even ...
0
votes
0answers
16 views

How to solve asymptotic recurrence without using Master Theorem

I am working on the following problem. Consider the function $B:\mathbb{N}\to\mathbb{R}$ defined by: $$B(n) = \begin{cases} 1 & \text{if $n\leq 2$,}\\ 3\cdot B(\lceil n/\log_2 n\rceil) + n & ...
-5
votes
1answer
46 views

Discrete math halp!? [on hold]

Define the relation $\rho$ on $\mathbb{R}$ by the rule: $\forall x, y \in \mathbb{R},~ x \rho y$ if and only if $\exists n \in \mathbb{Z}$ such that $y = x + n\pi$. In other words, $x ρ y$ if and only ...
1
vote
1answer
37 views

Find new generating function, given an arbitrary generating function

In a discrete mathematics past paper, I am asked to find the generating function for the sequence $$\langle a_0, 0, a_2, 0, a_4, 0, \ldots \rangle,$$ given that $A(x)$ is the generating function for ...
5
votes
2answers
53 views

Find the generating function of this sequence

I need to find the generating function of the sequence $c_n = (a_0, a_1, a_2, \ldots)$, where: $$a_n = \begin{cases} 2^{n/2} & \text{if $n$ is even,} \\ 1 & \text{if $n$ is odd.} ...
0
votes
1answer
11 views

Maximization of a statistical property of a subset of random numbers

I have encountered a maximization problem which could be formulated as a discrete mathematics problem arising from statistics, but I don't know where to start or which techniques could be applied to ...
2
votes
1answer
31 views

Counting the functions with f(i) ≤ f(i+1) for all i=1,..,n-1

How can I determine how many functions are weakly monotone increasing from $[n]\equiv \{1,..,n\}$ to itself: $$ f:[n] \to [n] \text{ so that } f(i) \leq f(i+1) \; \forall i\in[n-1]$$ Thank you for ...
-1
votes
0answers
18 views

Stirling numbers: $S(n,k)=\sum_\limits{m=k}^n k^{n-m}S(m-1,k-1)$ [on hold]

How can I show $S(n,k)=\sum_\limits{m=k}^n k^{n-m}S(m-1,k-1)$ holds for the Stirling numbers, $n\geq m \geq k \geq 2$.
0
votes
1answer
34 views

find the number of one-to-one function $[\pm n] \rightarrow [\pm n]$

the permutaion of $[\pm n]$ is a bijective (one-to-one) function $\pi:[\pm n] \rightarrow [\pm n]$ so that $\pi (-i) = -\pi(i)$ . $[\pm n]:=\{1, \dots, n-1, \dots, -n\}$. i have to find and determine ...
-1
votes
0answers
32 views

Significant Figures calculation [on hold]

$$400 \times 185=74\,000$$ I need to get this in least amount of Sig figs. Can someone please explain the rules of calculating the needed amount of significant figures?
0
votes
0answers
12 views

Prove Ackermann's function by induction

I have to prove the following property $$A(x,y)>x$$ of Ackermann's function. Do we do the following? We will show that $$A(x, y) \geq A(0, x+y)$$ by induction on $k=x+y$. Base case: For $k=0$ ...
2
votes
2answers
36 views

How can I determine the sequence which has this generating function?

In a discrete mathematics past paper, I must find the first eight terms of the sequence whose generating function is $$\frac{x^2}{(1-x)(1-2x)}.$$ I have looked at both of the following posts: How ...
0
votes
1answer
30 views

Sum of $n$ numbers dividable by $n$ from $(n-1)^2-1$ numbers.

I'm trying to solve some problem in the past few days(by the way, my first question here is some sort of a direction for solution - or maybe not). Problem: Suppose that we have a list of $(n-1)^2-1$ ...
0
votes
2answers
32 views

Closed form formula for discrete sums [on hold]

Is there a general way to obtain a closed form formula for any discrete sum of the form: $\sum_{a}^{b}f(n)$ with certain restrictions on the form of $f(n)$, much like how we can find closed form ...
1
vote
1answer
58 views

how many squence $a_1, \dots ,a_n$ there are so that the product of $a_1 \cdot a_2 \cdot \dots \cdot a_n$ divisible by 10?

i have to provide how many squences $a_1, \dots ,a_n$ with $a_i\in \{1,\dots,9\}$ so that the product of $a_1 \cdot a_2 \cdot \dots \cdot a_n$ divisible by 10? how can i begin with this problem?
2
votes
1answer
23 views

Multiplying a floor function to a number

Is it correct to write: $\cfrac{\left\lfloor{\cfrac{\pi y^2}{3\sqrt{3}x^2}}\right\rfloor}{n} \times\sqrt{3}x =\left\lfloor\cfrac{\pi y^2}{3xn}\right\rfloor$ ?
0
votes
0answers
19 views

Write the following statements in symbols [closed]

(a) Every integer x has a paired integer y such that the difference between x and y is exactly 2. (b) There exists a real number z such that the product of z and any other real number is 0.
0
votes
1answer
28 views

q-binomial Identity

Unfortunately I am not able to solve the following problem: I tried finding a bijection similar to the prove of this binomial identity: $$\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$$ ...
3
votes
2answers
32 views

proving a function as surjective

How can I prove a function is surjective? In the function $f: \Bbb{R}\to \Bbb{R}$, $$f(x) = 4x+7$$ we take $x = y-\frac{7}{4}$ and show that $f(x)=y$. How can this method prove that this function is ...
0
votes
1answer
21 views

what is differences between digraph and subgraph

what is the difference between digraph and subgraph in discrete-mathematics. Any one explain the example of these graphs.
5
votes
1answer
33 views

Sets raised to exponents

"Find two non-empty sets $A$ and $B$ for which $A^B$ and $B^A$ are not the same size." I'm really not sure what this means or how to even go about attempting this... Can anyone provide an example of ...
0
votes
1answer
40 views

Inductive step in Proof of Induction

Prove by induction: $1^2 + 3^2 + 5^2 + · · · + (2n − 1)^2 =\frac n3 (2n − 1)(2n + 1)$ So first I proved the base case ($n = 1$) which holds true. Tried doing the Inductive step where $n = n + ...
1
vote
1answer
35 views

Proving by Contradiction

Prove by Contradiction Suppose $a, b \in Z$. If $4|(a^2 + b^2)$, then $a$ and $b$ are not both odd. So the contradiction: Assume $4|(a^2 + b^2)$, where $a$ and $b$ are both odd. Then $a=2k+1$, ...
0
votes
1answer
14 views

Correctness of a set with respect to another set.

Is there a specific measure for correctness of a Set w.r.t another set? e.g. Consider there's a base set A, and a set B whose correctness needs to be measured w.r.t set A. Now B might contain some ...
0
votes
1answer
23 views

How many ways there are to arrange a boolean $2\times5$ matrix such that there won't be two zeros one above the other

How many ways there are to arrange a boolean $2\times5$ matrix such that there won't be two zeros one above the other. For example, this is not allowed ...
-2
votes
2answers
29 views

One-to-one and binary strings [closed]

Assume $T$ be the set of binary strings of length $30$ with $10$ $1$’s and $20$ $0$’s. Let $X$ be the set of the first $30$ positive integers $\{1,2,3,…,30\}$. Let $Y$ be the set of all subsets of $X$ ...
-4
votes
0answers
21 views

Gauss elimination [closed]

Why we change row in matrix ? a=2 0 1, 0 22 1, 0 -3 -23, this is matrix. ~ a=2 0 1, 0 -3 -23, 0 22 1 Here, in first matrix , why we change second row to third row .
1
vote
2answers
69 views

How to prove that $C\cdot\aleph_0=C$

How can I prove that $C\cdot\aleph_0=C$? I tried this: Given that $k\cdot 1=k$ and $C\cdot C=C$ if $C\cdot C = C \wedge C\cdot 1 = C \wedge C>|\mathbb N|>1$ then $C\cdot |\mathbb N|= C$ c is ...
0
votes
1answer
38 views

Prove by either direct proof or contraposition

I have a question like this: By direct proof or by contraposition: Let $a \in Z$, if $a \equiv 1 \pmod{5}$, then $a^2 \equiv 1 \pmod{5}$. Hypothesis: $a \in Z,~a \equiv 1 \pmod{5}$ Conclusion: $a^2 ...
1
vote
3answers
36 views

Trouble understanding One-One and Onto function.

So I have a question like this: Let $g$ be a function $g : \mathbb{Z} → \mathbb{Z} \times \mathbb{Z}$ such that $g(n) = (2n, n + 3)$. And I want to find if this is onto and one-one. But I'm ...
4
votes
2answers
417 views

What is meant by the delta equivalent sign?

What is the meaning of the delta equivalent ($\overset{\Delta}{=}$) sign? I met this in a communication theory text. It said, signaling rate: $r\overset{\Delta}{=} 1/D$ symbols/s or also called ...
-1
votes
2answers
79 views

How many ways can a woman polish her nails if she uses one of two colors on each nail?

A woman is preparing to go to a party and would like to have her nails polished. Suppose she wants to use either the light pink or red nail polish on each nail, how many ways can shepolish her nails? ...
0
votes
1answer
35 views

How to calculate the shielding time and determine the time step

The problem is illustrated as follows. A shielding plate scans over a target plate at a constant speed $v_{scan}$ and dynamically shadows the target plate to adjust the exposure time of the light ...
0
votes
0answers
30 views

Example of nonempty partially ordered set (S, R)

When asked a question like this: Give an example of a nonempty partially ordered set (S, R) that does not have incomparable elements. Draw the Hasse diagram for this partially ordered set would this ...
-1
votes
1answer
51 views

Binary strings and discrete math

Question: Let $S$ be the set of binary strings of length $30$ with $10$ $1$’s and $20$ $0$’s. Let $A$ be the set of the first $30$ positive integers $\{1,2,3,\dots,30\}$. Let $B$ be the set of all ...