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

0
votes
3answers
53 views

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

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
18 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
16 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
59 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
19 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
34 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
41 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
57 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 [on hold]

(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
39 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 [on hold]

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
413 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
72 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
34 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 ...
4
votes
1answer
78 views

Bit String Bijection

I am searching for a bijection between two types of bit strings (strings of 0's and 1's) both of even length (2n). The restriction on the first type of bit string is that they must have the same ...
2
votes
1answer
26 views

Apply Hall's theorem to a problem

I have only seen Hall's theorem applied on the marriage problem. For the problem below I have to use this theorem I guess. For me it's still difficult to apply this to a problem. Problem: Consider ...
-1
votes
2answers
29 views

Preimage of the set of $x$-values

What is the preimage of the set of $x$-values between $0$ and $1$? i.e. $f^{−1}(\{x\mid 0<x<1\})$? Explain. I get that we have to find the inverse image $f^{-1}(S) = \{a\in A \mid f(a) ...
0
votes
1answer
30 views

cardinals proves - bigger or equal than [closed]

Let $k_1, k_2, m_1, m_2$ be cardinals. Prove that if $k_1 \leq k_2$ and $m_1 \leq m_2 \implies k_1m_1 \leq k_2m_2$. I dont know where to start from. Any help will be appriciated.
0
votes
1answer
25 views

Floor fuctions question as it relates to image

What is the image of x values between 0 and 1? i.e. 𝑓({𝑥|0<𝑥<1}? Explain. I do not want the answer i just want to understand how to get the answer. While my professor has explained this in a ...
0
votes
1answer
48 views

Problem with Recurrence Relations

A particle P executes a random walk on the line above such that when it is at point $n$ ($1 \leq n \leq 9$, $n$ a non-negative integer), it has a probability of $0.4$ of moving to $n+1$ and a ...
0
votes
1answer
23 views

Another Venn problem

We are to create a Venn Diagram for $B \cap A = A$. I have created this, I do not think this is correct. Can anyone shed some light on this?