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

Prove there exists a 2x2 entirely black or white square.

Given a 200x200 board containing black and white squares prove there exists a 2x2 sub square that is entirely black or entirely white. The total # of squares is 40000, there are 199x199 squares of ...
1
vote
0answers
9 views

Mean Preserving Spread and concavity of the discrete function

Could someone help me with the understanding of the following thing? Consider a discrete distribution with pmf $p_k$ and its mean preserving spread (MPS) $p_k'$. Also let the set $a_1, \ldots, a_n$ be ...
1
vote
1answer
31 views

Steps to solve this recurrence relation?

I have the following question: I am aware that I have to find the characteristic polynomial of this equation but I do not understand how to deal with $64 . 3^{n-4}$ so could anyone explain how to ...
-4
votes
1answer
35 views

Is the difference between two odd integers (or an odd and an even one) odd? [on hold]

I am trying to prove or disprove The difference of any two odd integers is odd. An odd integer minus an even integer is odd.
-3
votes
1answer
30 views

How many recursive calls are made when quicksort is size n [on hold]

How many recursive calls are necessary when quickSort sorts an array of size n if you use median-of-three pivot selection? I thought the answer is n times because isnt this the best case?
0
votes
0answers
6 views

Find a recurrence relation for the number of different messages that can be sent in n microseconds

Question A :Find a recurrence relation for the number of ways to climb n stairs if the person climbing the stairs can take one stair or two stairs at a time. Question B:Messages are transmitted over ...
1
vote
3answers
30 views

Help with discrete math proof

I'm having trouble with the following: $\ a_1=1$ and $a_n=1+\sum_{i=1}^{n-1} a_i$ for $n>1$ How should I go about proving the below? Any hints? $a_n = 2^{n-1}$
3
votes
3answers
71 views

Proving if $x^3$ is even, then $x$ is even.

Theorem: If $x$ is a positive integer and $x^3$ is even, then $x$ is even. My Proof by Contrapositive: I. Assuming that $x$ is odd, then I will show that $x^3$ is odd. II. $x$ is odd, so $x$ ...
0
votes
2answers
27 views

Can someone explain how to find the number of equivalence classes and elements?

I am struggling so much with this topic. Trying to do some practice questions but I don't seem to get it. What I'm working on is Let $A = \{ 1, 2, 3, \dots, 2014 \} = \{ x \mid 1 \le x \le ...
4
votes
1answer
32 views

“congruence modulo 7” is an equivalence relation on Z. Find three elements in the equivalence class [3].

“congruence modulo $7$” is an equivalence relation on $\mathbb Z.$ Find three elements in the equivalence class $[3].$ so $3$ is congruent to $mod\ 7$.. My attempt: a = bq + r = 7(1) + 3 = 10 , ...
2
votes
1answer
24 views

Questions concerning elements in $F = \big\{f: \{1, 2, 3\} \to \{1, 2, 3, 4, 5\}\big\}$.

a) Find and simplify the number of functions $f \in F$ so that $f(1) = 4$. My attempt: there is $1$ choice for $f(1)$, and $5$ choices for $f(2)$ and $5$ choices for $f(3)$, thus $1\cdot 5\cdot 5 = ...
1
vote
4answers
91 views

Bob starts with \$20. Bob flips a coin. Heads = Win +\$1 Tails = Lose -\$1. Stops if he has \$0 or \$100. Probability he ends up with \$0?

I'm working on the extra credit for my Discrete Structures homework, but so far I have been unable to get a handle on the problem, even with help from 3rd parties, so I've decided to turn to you guys. ...
-2
votes
1answer
17 views

show that $\neg(p_1 \vee p_2 \vee… \vee p_n)$ is equivalent to $\neg p_1 \wedge \neg p_2 \wedge… \wedge \neg p_n$ by induction

Use mathematical induction to show that $\neg(p_1 \vee p_2 \vee... \vee p_n)$ is equivalent to $\neg p_1 \wedge \neg p_2 \wedge... \wedge \neg p_n$ whenever $p_1,p_2,...,p_n$ are propositions. So ...
3
votes
3answers
89 views

Whats the difference between Antisymmetric and reflexive? (Set Theory/Discrete math)

Antisymmetric: $\forall x\forall y[ ((x,y)\in R\land (y, x) \in R) \to x= y]$ reflexive: $\forall x[x∈A\to (x, x)\in R]$ What really is the difference between the two? Wouldn't all antisymmetric ...
1
vote
1answer
54 views

What are the components of binary strings?

$C_{9}$ is the graph with vertices representing all binary strings of length nine. Two strings are adjacent if and only if they differ in exactly three positions. How can I compute how many components ...
0
votes
1answer
24 views

How to formulate the product of two generating functions without their final terms?

I know that if we have two generating functions like so: $A(z) = \sum_{n=0}^\infty a_nz^n$ and $B(z) = \sum_{n=0}^\infty b_nz^n$ Then we can write $A(z)B(z) = \sum_{n=0}^\infty(a_0b_n + a_1b_{n-1} ...
-2
votes
0answers
21 views

Selection of distinct (positive factors) of 50 [on hold]

The selection of how many distinct (positive) factors of 50 will guarantee that at least two of them have a product of 50? Explain.
0
votes
1answer
20 views

Is my solution consider as a proof of inclusion-exclusion for $k=3$

This is my solution but I don't know if I can consider it as proof??? Here let $A$ , $B$ , and $C$ are sets
0
votes
1answer
27 views

Find $c$ in modular mathematics [on hold]

Suppose that $a$ and $b$ are integers, $a\equiv 11(\mod19)$ and $b\equiv3(\mod19)$ . Find the integer $c$ with following properties. $0\le c\le18$ $c\equiv 7a+3b(\mod19)$ $c\equiv2a^2 ...
0
votes
1answer
29 views

Can the function y=5 be injective or surjective for all x ∈ integers?

I have a practice exam and I get kind of confused about: Is the constant function y = 5 , ∀ x ∈ Z [All integers] Is this function Injective or Surjective?
1
vote
2answers
67 views

Proving $n^a-n^b$ is divisible by 10

Let $n$ be positive integer. Prove that there exists positive integers $a$ and $b$, with $a \neq b$, such that $n^a-n^b$ is divisible by $10$. I have tried using mathematical induction and logs but I ...
1
vote
1answer
17 views

Use induction to figure out the number of handshakes in a party

Every arriving guest shakes hand with everybody else at a party. If there are n guests in the party, how many handshakes were there? Proof by using induction. My approach to this problem was to write ...
1
vote
2answers
36 views

How would you go through this combination/ permutation problem

A market has 30 different pants and 12 different hats. You want to to get 3 different pants and 2 different hats. How many ways can you make this purchase? I assume this is a combination, but stuck ...
0
votes
0answers
24 views

Turning a recurrence relation into a characteristic equation

I have the following recurrence to solve: bn = 13bn-1 - 22bn-2 , n > 1            Subject to b0 = 3 , b1 = 51 I've figured it out until b4: b2 = ...
2
votes
0answers
25 views

computing characteristic polynomial of hyperplane arrangement

The following problem comes from Richard Stanley's $\textit{Enumerative Combinatorics}$ vol. 1, 2nd ed. It is problem 114 (c) in Chapter 3. Let $\mathcal{A}$ be a hyperplane arrangement in ...
0
votes
3answers
23 views

determining which graphs are bitpartite/2-colorable and which are not

I am having trouble understanding bipartite/$2$-colorable graphs. I was hoping someone can guide me through this question. For the graphs given above, either prove that they are bipartite by showing ...
0
votes
1answer
9 views

Is this relation P an equivalence relation or a partial order relation?

I am having trouble with partial order and equivalence relations. I was wondering if someone can guide me through this problem. Let $Σ$ be the set of letters {$a, b, . . . z$}. Let $Σ^∗$ be the set ...
1
vote
2answers
30 views

Prove that the sum of two positive real numbers is equal or greater than the square root of their product.

Trying to prove this: A and B are positive real numbers. A + B ≥ √ AB  This is what I wrote: Proof by Contradiction A + B < √ AB  (A + B)2 < AB A2 + AB ...
-2
votes
1answer
45 views

Can anybody help me for this counting question? [on hold]

Peter has $12$ pairs of socks and $6$ pairs of gloves in different colors. His socks are in green, yellow, black, and grey ($3$ pairs each). Peter's gloves are either blue, black, or red ($2$ pairs ...
-3
votes
0answers
21 views

How to determine whether injective or surjective over this functions [duplicate]

G : N×N given by G = 2x+5 ∀x ϵ N H : Z×Z given by H = 10 ∀x ϵ Z I got an idea whether injective or surjective but don't know how to go through. And finally, are these functions? I think they are ...
-1
votes
1answer
21 views

How to go towards this functions and defining whether injective or surjective

G(x) : N×N given by G(x) = 2x+5 ∀x ϵ N H(x) : Z×Z given by H(x) = 10 ∀x ϵ Z I am not familiar with this notations. However, I got an idea whether injective or surjective. And finally, are ...
2
votes
2answers
37 views

Probability of a pair of red and a pair of white socks among five chosen

In the box are $7$ white socks, $5$ red socks and $3$ black socks. $2$ socks are considered a pair if they have the same color. $5$ arbitrary socks are selected at random from the box. ...
0
votes
0answers
28 views

proof that some expected value equal to $\theta (\log n - \log k)$

So here is the problem - Given the following equation: $(c_2\cdot \log n) - (c_1\cdot \log k)\le E(X)\le 1+ (c_1\cdot \log n) - (c_2\cdot \log k)$ When $c_2,c_1\gt0$ and also $c_1\gt c_2$ In ...
0
votes
1answer
24 views

How can I draw a Hasse Diagram divisibility?

We just started learning graphs and I wanted to know how can I draw the Hasse diagram for divisibility on the sets: {$6, 10, 14, 15, 21, 22, 26, 33, 35, 39, 55, 65, 77, 91, 143$} In class we ...
0
votes
0answers
15 views

How to find a specific SLOPE at a point [on hold]

The question is to find a slope of 1;0;-2 in f(x) = x^2 the point doesn't matter You can also discard the function and use variables so I can do it for all exercices like this. Thanks in advance
-3
votes
0answers
68 views

Puzzle to puzzle you:image [on hold]

Suppose 3 1D Signals x(t), y1(t) and y2(t) are given as x(t)=sin(40*pi*t); y1(t)=.5*sin(40*pi*t) and y2(t)=x(t)+y1(t). Left side =Right side Here,values of x(t)and y1(t)i.e.(Right side) are given ...
0
votes
1answer
27 views

Determining a relation if reflexive, symmetric, and transitive

I just get stuck in this relation and need to find if this relation is Reflexive/ Irreflexive or Neither, Symmetric/ Antisymmetric or Neither, Transitive or Not. $$W_1 = \{(a , b) \in \mathbb ...
3
votes
2answers
88 views

What is the probability of a randomly chosen bit string of length 8 does not contain 2 consecutive 0's?

Just what the title says, I'm trying to determine the probability of a randomly chosen bit string of length $8$, not containing $2$ consecutive $0$'s. I've determined the total number of possible bit ...
2
votes
2answers
53 views

How to find a function that is the upper bound of this sum?

The Problem Consider the recurrence $ T(n) = \begin{cases} c & \text{if $n$ is 1} \\ T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4)\rfloor) + 4n, & \text{if $n$ is > 1} \end{cases}$ A. Express ...
-1
votes
1answer
45 views

What does this $TS \models P$ mean in relation to set theory. [on hold]

In set theory, what does it mean when you have $TS \models P$ Rationale: when dealing with Linear Temporal properties for transition system, you can have a safety property $P$ and a transition ...
2
votes
1answer
22 views

Combinatorics/Probability unordered lists

I don't really understand these unordered lists problems such as... Q: John goes to a store and buys 10 pieces of fruit from the selection of apples, bananas,peaches and pears at random. What is the ...
2
votes
1answer
15 views

number of weak compositions modulo prime $p$

For $n\in \mathbb{N}$ and some prime $p$, consider $(\mathbb{F}_p)^n$. Is it known how many weak compositions $$x_1+x_2+\ldots +x_n\equiv 0 \pmod p$$ in $\mathbb{F}_p$ there are, where $(x_1, \ldots, ...
3
votes
4answers
96 views

Solve the recurrence of the alternating sum $R_n=R_{n-1}+(-1)^{n}(n+1)^{2}$

I have been trying to solve this recurrence for a few hours, but I haven't been able to find the solution yet: $R_0=1$ $R_n=R_{n-1}+(-1)^{n}*(n+1)^{2}$. I have been trying to substitute ...
0
votes
1answer
26 views

Induction Mathematics and Factorials

\usepackage{amsmath} Evaluate the sum $\sum_{k=1}^{n} {k\over (k+1)!}$ $\sum_{k=1}^{1} {1\over (1+1)!} = {1\over 2}$ $\sum_{k=1}^{2} {2\over (2+1)!} = {5\over 6}$ $\sum_{k=1}^{3} {3\over (3+1)!} ...
0
votes
1answer
32 views

Which discrete mathematics book do you think is better between Epp's and Rosen's for a clueless self-learner?

I am a programmer, and I want to become a machine learning researcher and a good software engineer. I dabbled with calculus, linear algebra, and real analysis for a few months when I was enrolled in a ...
0
votes
2answers
33 views

Proofing Induction Mathematics

I have just started to cover induction mathematics in my Discrete Mathematics class and I'm a little confused as to where to go with this problem. Am I on the right track? Prove that 9 divides (n^3 ...
2
votes
1answer
34 views

How to show that recurrence $T(n) \in \Omega(n^{0.5})$ using proof by induction?

This is recurrence $T(n)$ $ T(n) = \begin{cases} c, & \text{if $n$ is 1} \\ 2T(\lfloor(n/4)\rfloor) + 16, & \text{if $n$ is > 1} \end{cases}$ This is my attempt to show that $T(n) \in ...
0
votes
2answers
21 views

Does this recurrence relation run in $ \Theta(n) $?

This is the recurrence relation I am trying to solve: \begin{align} T(n) & = 2 \cdot T \left( \frac{n}{4} \right) + 16, \\ T(1) & = c. \end{align} I broke this down (i.e., solved this ...
0
votes
0answers
6 views

what is the total number of ways Company can advertise meeting its minimum cost strategy

There are exactly N advertising boards on the highway. Now a company want to advertise on some of these advertising boards (each advertising board costs some money). Company strategy is that, they ...
-1
votes
1answer
28 views

Covering relation over functions

F is a group that includes all functions from N to N K is relation over F. For f,g ∈ F: (f,g) ∈ K iff ∀ n∈N, f(n)≤g(n). Obviously K is Partially ordered set and not Total Order. My problem is with ...