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
1answer
19 views

Combinations from prime number of elements

Let $p$ be a prime and let $k$ be a natural number: Prove that for $k < p$, $\binom{p}{k}$ is divisible by $p$. My proof: The formula for $p$ choose $k$ is: $$\frac{p!}{k!(p-k)!}$$ Since the ...
0
votes
2answers
11 views

Combinatorics identity proof by induction

Prove the formula by induction on n and fixed r: $\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \ldots + \binom{n}{r} = \binom{n+1}{r+1}$ What I tried: Base: we take $n=r$ so $\binom{r}{r} = ...
1
vote
2answers
17 views

Anti-Symmetric Matrix

Relation R is given by a matrix $$\begin{bmatrix} 1& 0& 0& 0\\ 1& 1& 0& 0 \\ 1& 0& 1& 0 \\ 1& 1& 1& 1 \end{bmatrix} $$ Is it anti-symmetric? I'm ...
0
votes
2answers
14 views

Proving Greatest Common Divisors

I have two questions I'm struggling with 1) Suppose that gcd(a, y) = 1 and gcd(b, y) = d. Prove that gcd(a · b, y) = d I have 1 = ua + vy and d = sb + ty, and I use linear combination to get d*1 = ...
1
vote
1answer
11 views

Zero divisors and inverstible elements

I have learned about $X_n = \mathbb{Z} / n\mathbb{Z}$. I understand that a zero divisor is an element $x\neq 0$ in $X_n$ such that $xy = 0$ for some $y\neq 0$. I understand that an element $x$ in ...
0
votes
2answers
22 views

how does $(p\to q)\lor r \lor s$ effect $(p\leftrightarrow q) \lor r \oplus s$

If we know that $\lnot p \lor q \lor r \lor s=\top$, then what is the value of: $(\lnot p \land \lnot q) \lor (p \land q) \lor(r \land \lnot s) \lor (\lnot r \land s)$ I tried doing it with a truth ...
1
vote
3answers
54 views

Finding all the values of n, such that $ \varphi (n) = 12 $ [duplicate]

I have not broken this down very far. I have come to the conclusion that there are infinitely many values for n where there exists 12 coprimes to n. Since there are infinitely many primes, and primes ...
1
vote
1answer
13 views

When to use Binomial or Neg Binomial?

I have a problem that I'm not sure which distribution to use: 12 Toll employees were let go for taking more than 25,000 dollars in tolls. Lets say that one of the people let go on one day collected ...
1
vote
2answers
30 views

Trouble understanding algebra in induction proof

I'm on hour 20 of studying for the discrete math midterm tomorrow, and I've got to be honest I'm a little panicked. In particular I'm having trouble with induction proofs, not because I don't ...
0
votes
2answers
42 views

What does the constant mean in Big O notation?

I have a big issue in understanding the real meaning of Big O notation. Classical definition: $f(x) = O(g(x))$ as $x\rightarrow k$ if there exist $\delta, C > 0$ such that $f(x) \leq Cg(x)$ ...
3
votes
1answer
18 views

Find maximum number of nodes in a regular graph of degree 4 and diameter 2

In $n$ nodes directed graph, every vertex has in-degree and out-degree equal to $4$. If every vertex is reachable from every other vertex directed by a path of length at most $2$. How can we find ...
0
votes
0answers
15 views

Construction proof Chinese remainder theorem?

Use the construction in the proof of the Chinese remainder theorem to find all solutions to the system of congruence's x is equivalent to 2 (mod 3), x is equivalent to (mod 4), and x is equivalent to ...
1
vote
2answers
29 views

For any integer a, if $6|(3−a)$, then $3| (a−2)$.

Prove: For any integer a, if $6|(3−a)$, then $3| (a−2)$. I've been trying to work this problem for a while, but missed a day of class and can't seem to work it out.
1
vote
2answers
36 views

Number of particles at time $t$

A following problem appears in my text book under the section of induction: At time $0$, a particle resides at the point $0$ on the real line. Within $1$ second, it divides into $2$ particles that ...
1
vote
1answer
64 views

Consider strings of length n taken from the restricted alphabet {a, b, c}.

Consider strings of length n taken from the restricted alphabet {a, b, c}. (a) How many such strings are there? (b) How many such strings are there with exactly two as? (c) How many such strings are ...
2
votes
2answers
23 views

Number of Symmetric Relations on a set A

I'm having trouble understanding their explanation. I follow everything up to "The Set $A_2$ contains $(1/2)(n^2 - n)$ subsets..." could someone please help explain this to me? Source: Discrete and ...
1
vote
1answer
44 views

Proving that all numbers between two numbers are composite

I am having trouble with this problem: Assume $p_1, p_2 \ldots p_{n+1}$ be the first $n+1$ primes in order. Prove that every number between $(p_1\cdot p_2 \cdot \ldots \cdot p_{n}) + 1$ (exclusive) ...
-2
votes
0answers
35 views

i need help with identifying if this relation is a order or not… [on hold]

hello guys i have a quick question about the matrix and order im given matrix of $$\left[\begin{array}{cccc} 1&0&0&0\\ 1&1&0&0\\ 1&0&1&0\\ 1&1&1&1 ...
2
votes
3answers
27 views

Determining number of solutions to equation (Discrete math)

I was given this homework problem: How many solutions are there to the equation: x1 + x2 + x3 + x4 + x5 + x6 = 29 Where xi, i = 1,2,3,4,5,6, is a nonnegative integer such that xi > 1. I also have ...
1
vote
1answer
27 views

Is this proof correct (Cartesian Products and Subsets)?

I am trying to prove that if $A \times B$ is a subset of $A \times C$ then $B$ is a subset of $C$ given that $A$ is not empty. I've looked at this question on here and I'm aware it's been asked. My ...
-2
votes
1answer
22 views

Is this relation reflexive, symmetric, transitive, anti-symmetric? [on hold]

Determine if $\rho$ is reflexive, symmetric, transitive, anti-symmetric. In each case, if $\rho$ is an equivalence relation, describe the equivalence classes. $$\begin{align}& A = \mathbb Z × ...
-1
votes
1answer
22 views

finding reflexive, symmetric, transitive, anti-symmetric and equivalence classes

For each relation $p$ described below, determine if $p$ is reflexive, symmetric, transitive, anti-symmetric. In each case, if $p$ is an equivalence relation, describe the equivalence classes. a) $A = ...
-1
votes
0answers
16 views

solve discrete math qs [on hold]

determine if ρ is reflexive, symmetric, transitive, anti-symmetric. In each case, if ρ is an equivalence relation, describe the equivalence classes. Two sequences of real numbers (an) and (bn) are ...
1
vote
1answer
30 views

attack on RSA (factoring when knowing e and d)

This is the problem, I have to explain how works the algorithm on the image with modular arithmetic for a discrete math class., I tried to explain it, but I couldn´t. In the class, I have seen this ...
-1
votes
0answers
21 views

discrete math: properties of a relation [on hold]

determine if ρ is reflexive, symmetric, transitive, anti-symmetric. In each case, if ρ is an equivalence relation, describe the equivalence classes. A = P(Z) (the power set of Z). Let X ⊆ Z be a ...
-1
votes
3answers
28 views

Prove the implication $[\exists\,x\;(\,p(x) \land q(x))] \implies[(\exists\,x\;p(x)) \land (\exists\,x\;q(x))]$ is a tautology. [on hold]

Prove the implication $[\exists\,x\;(\,p(x) \land q(x))] \implies[(\exists\,x\;p(x)) \land (\exists\,x\;q(x))]$ is a tautology. Show that the converse implication $[(\exists\,x\;p(x)) \land ...
0
votes
1answer
25 views

Numbers of the form $n^k-1$

I know that numbers of the form $2^k-1$ are called Mersenne numbers. But are there other special numbers which are one less than a power of an integer (for instance, does $3^k-1$ have some special ...
2
votes
3answers
96 views

Proof involving quantifiers

Prove or disprove: $(\forall x \in \mathbb Z) (\exists y \in \mathbb Z)(\forall z \in \mathbb N)(x + y \lt z)$ I am unsure on how to 'read' this statement. I would say take y = (z - x) - 1, then x + ...
1
vote
1answer
37 views

prove weak induction implies strong induction

There is a solution from a year ago that I don't quite follow which is why I post this along with my attempt, so it is not a duplicate. Prove weak induction implies strong induction: weak ind. ...
-1
votes
0answers
22 views

solve discrete math [on hold]

if A = Z × Z, and (a, b)ρ (c, d) if and only if a + b ≥ c + d. determine if ρ is reflexive, symmetric, transitive, anti-symmetric. In each case, if ρ is an equivalence relation, describe the ...
-4
votes
1answer
36 views

discretemath question [on hold]

if $A = \mathbb{Z}$, and we define a relation $a\ \rho\ b$ if and only if $5 \mid (2a + 3b)$. Determine if $\rho$ is reflexive, symmetric, transitive, or anti-symmetric. If $\rho$ is an equivalence ...
0
votes
0answers
28 views

Proof of a formula for generalized Fibonacci numbers

I have done the verification for $$U_rU_{n−1} − U_{r−1}U_n = (−1)^{r−1}U_{n−r}$$ I realized when I was doing for $n=k+1$, the expression $U_rU_k − U_{r−1}U_{k+1}$ would not equate to ...
-4
votes
0answers
48 views

Is this relation an equivalence relation? If so, identify the equivalence classes. [on hold]

Determine if $ρ$ is reflexive, symmetric, transitive, anti-symmetric. In each case, if $ρ$ is an equivalence relation, describe the equivalence classes. $$A = \mathbb R \,\text{ and }\, aρ b \;\text{ ...
5
votes
1answer
38 views

Graph DFS, BFS and some inference

Suppose G is a connected, undirected graph with at least 3 vertexes. we know the order or visiting the vertexes in DFS and ...
1
vote
0answers
20 views

Is shunting-yard algorithm needed if there is no parenthesis?

I am trying to find a permutation (with replacement) of operators(such as addition and multiplication) that makes numbers 1 2 3 , ..., 9 result in to some numbers. My guess is to find all possible ...
0
votes
0answers
12 views

Untangle the comb of sentences…

Here I have such a problem: Mister Alex, his wife Bianca and three children Carmen, Dan and Ela, are sitting together: (a) a. If Mister Alex watches Tv, the same does his wife; b. Or Dan, or Ela, ...
-2
votes
1answer
79 views

determining reflective, symmetric, transitive, anti-symmetric properties and describing equivalence classes

The question: determine if p is reflective, symmetric, transitive and/or anti-symmetric, if p is an equivalence relation, describe the equivalence classes A = Z , and $apb$ if and only if $5 | (2 a + ...
0
votes
0answers
43 views

Discrete math equivalence relations [duplicate]

(a) Let A be a non-empty set, and ρ an equivalence relation on A. Let a, b ∈ A. Prove that[a]=[b] ⇐⇒ aρb. (b) If ρ is both an equivalence relation and (simultaneously) a partial order on A, describe ...
-1
votes
0answers
21 views

Use this y to factor N [on hold]

Now that Alice has a multiple of φ(N) let's see how she can factor N=pq. Let x be the given muliple of φ(N). Then for any g in Z*[sub N] we have g^x=1 in Z[sub N]. Alice chooses a random g in Z∗[sub ...
1
vote
1answer
59 views

Let A be a non-empty set, and p an equivalence relation on A . Let a , b be an element of A . Prove that [ a ] = [ b ] is equivalent to apb

the question: a) Let A be a non-empty set, and p an equivalence relation on A . Let a , b be an element of A . Prove that [ a ] = [ b ] is equivalent to $apb$ b) If p is both an equivalence relation ...
0
votes
1answer
40 views

If a|b and b|a, find the value of a in terms of b.

If a|b and b|a, where a and b are integers and a≠0, find the value of a in terms of b. Assume that b>0.
1
vote
2answers
38 views

O(n) algorithm for minimizing Manhattan distance between points

Given two sets points with each point either "Black" or "White", design an algorithm to find the pair of points, one that is black and another that is white, such that the Manhattan distance between ...
1
vote
1answer
24 views

Using recursion tree to solve recurence T(n) = 3(n/2)+n

I am trying to solve the recurrance of the function, T(n) = 3(n/2)+n where T(1) = 1 and show it's time complexity. n can be ...
1
vote
3answers
54 views

n! v.s. $a^{n}$ How can we know which one is faster without graphing?

n! v.s. $a^{n}$ If we are given an arbitrary number a (a>1). How can we know which one is faster as n->INFINITY without graphing?
1
vote
0answers
31 views

Big O-notation proof: show that $x^{2}+5x+11$ is $O(x^{3})$

Show that $x^{2}+5x+11$ is $O(x^{3})$ by providing the smallest value of the witness $C$ such that $|f(x)|≤C|g(x)|$ whenever $x>11$. What's the value of $C$?
3
votes
2answers
43 views

How many binary sequences of length n are there that contain exactly m occurrences of the pattern 01?

I thought there were n-1 places between the first and last digit. In these places I hypothesized there are switches that change (from 0->1 or 1->0) For ...
0
votes
1answer
22 views

Transitive Relations on a set

I am trying to study binary relations (for myself, it's not an assignment!) I have the set $\{1,2,3,4\}$, and one of the relations in the exercise is $\{(1,3),(1,4),(2,3),(2,4),(3,1),(3,4)\}$. A ...
1
vote
2answers
49 views

Solve the recurrence relation $a_n=4a_{n-1}-3a_{n-2}+2^n, a_1=1, a_2=11.$

First I solved $a_n=4a_{n-1} -3a_{n-2}$: $$x^2-4x+3=0\Rightarrow (x-3)(x-1)=0\Rightarrow a_n=k_1(1)^n +k_2(3^n)=k_1+k_2(3^n)$$ The problem is, I have no idea how to handle that part which has made ...
0
votes
1answer
34 views

Inductive proof on r

Let $r, n ∈ N$ and let $r ≤ n$. Give an inductive proof for: $$ {n+1 \choose r + 1} = ∑_{k=r}^n {k \choose r} $$ Step 1: We will prove this using induction on n. n = 1 Step 2: n = k, prove for n = ...
0
votes
1answer
21 views

Proof by induction with two variables

Giving proof by induction is normally very straight forward: $n+1$ and such. But how do you deal with two variables $m$ and $n$? Given this problem, how do I ensure that I'm proving for $n+1$ and ...