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
59 views

Discrete Mathematics Proof,

I have a problem where I need to prove the following: So far what I did was: take the contrapositive of this statement. Which becomes: $a|b \land a|(b+1) \implies a\leq2$ Using a fact of ...
1
vote
2answers
220 views

Upper bound of Euclidean norm on vectors in $\mathbb{R}^n$

Show that for any vectors $v_1,\ldots,v_n \in \{-1,1\}^n \subset \mathbb{R}^n$, there exist $\epsilon_1,\ldots,\epsilon_n \in \{-1,1\}$ such that the Euclidean norm of $v=\sum_{i=1}^n \epsilon_i v_i$ ...
1
vote
2answers
57 views

Ways to select three-man teams

In a competition there are 18 competitors. Answer the following: A) During the first day they're competing in three-man teams (total of 6 teams). How many ways are there to select the teams? B) If ...
0
votes
2answers
23 views

Question about functions and input/output

So I am given a formula $f(x) = {1\over(x^2-2)}$. I need to determine if it is a function for f: $\mathbb{R} \to\mathbb{R}$ and if it is a function for f: $\mathbb{Z}\to\mathbb{R}$ For the first ...
0
votes
1answer
41 views

Discrete math three fundamental principles

Suppose that there are 15 identical copies of The Great Gastby and 12 distinct biographies on a bookshelf. (a) How many different selections of 12 books are possible? (b) How many different ...
0
votes
2answers
76 views

How do you solve for the cardinality of a power set of some complex set? (i.e. $|\mathcal P(A^n)|$ , $|\mathcal P(A\cup B)|$ )

Suppose $A$ is some set such that $A = \{a_1,a_2,\dotsb,a_n\}$. We know that $|A|=n$. We know that $\mathcal P(A)= 2^n$. Now let $A^n$ denote the cartesian product of a set A with itself n times. ...
1
vote
0answers
26 views

How to find a function that can approximate another blackbox function programmaticly?

This question has been posted on http://stackoverflow.com/questions/21758016/how-to-find-a-function-that-can-approximate-another-blackbox-function-programmat I was suggested to post it here. I ...
2
votes
1answer
49 views

Three Fundamental Principles

How many different pizzas can be ordered if a pizza can be selected with any combination of the following ingredients: anchovies, ham, mushrooms, olives, onion, pepperoni, and sausage? Can someone ...
2
votes
2answers
107 views

Equality with floor function and logarithm

Prove that if n is odd then $\lfloor(\log_2(n))\rfloor=\lfloor(\log_2(n-1))\rfloor$. I tried to substitute $n=2k+1$ but it didn't help me in any way.
1
vote
2answers
125 views

Strong Induction: Finding the Inductive Hypothesis

Consider this claim: Every positive integer greater than 29 can be written as a sum of a non-negative multiple of 8 and a non-negative multiple of 5. Assume you are in the inductive step and trying ...
1
vote
1answer
34 views

Why is a statement such as, “It's 5 o'clock” excluded from propositions?

From MIT notes: A proposition excludes statements whose truth varies with circumstance such as, “It’s five o’clock”. And: A predicate is a proposition whose truth depends on the value of ...
1
vote
1answer
92 views

Homework question about Ramsey numbers

Consider a group of nine people. We know that at least one person, say Adam, knows an even number of people and does not know an even number of people. Show that either Adam and two other people all ...
1
vote
1answer
73 views
1
vote
1answer
63 views

The Mysterious Discrete Math Operator

I am working on some discrete mathematics and came across this strange operator on two sets. $R \circ S$ I have only seen this circle operator with function compositions, so is this "Set ...
0
votes
1answer
549 views

Prove -n^2 diverges to negative infinity

Prove directly that the following sequence diverges to negative infinity $a_n = -n^2$ I understand that the sequence will diverge to negative infinity. I know that I must somehow integrate an $n$ ...
0
votes
1answer
30 views

Prove the following statements about a graph G [closed]

G is connected diam(G) $\leq$ 10 G is bipartite G is vertex transitive So I don't need to prove these statements (since not enough information is given about the graph G) But if I did have enough ...
0
votes
1answer
68 views

The clique number ($\omega $) of a graph G is the largest integer k such that K_k is a subgraph of G

Prove that if G $\cong$ H then $\omega(G)=\omega(H)$. So this makes sense. But how do I go about proving it? I understand if two graphs are isomorphic then they are essentially the same and that ...
2
votes
1answer
59 views

Let G be a connected graph not having P_4 or C_3 as an induced subgraph. Prove that G is a complete bipartite graph

I understand what a complete bipartite graph is but am not sure how to relate that to a P_4 graph
0
votes
1answer
178 views

Prove that if G is connected then v $\in$ V(G) has a neighbor in every component of G-v

I understand what the question is asking but am not sure how to begin the proof. G-v is the set of vertices and edges which are in G but not v
2
votes
1answer
53 views

Graphs: Prove that $\operatorname{diam}(G \cdot H) \leq \operatorname{diam}(G)+\operatorname{diam}(H)$.

Let $G$ and $H$ be graphs. Prove that $\operatorname{diam}(G \cdot H) \leq \operatorname{diam}(G)+\operatorname{diam}(H)$. So I understand cross product of graphs but I am not sure where to start on ...
0
votes
1answer
223 views

Book on discrete mathematics for self study

I am searching for book on discrete mathematics which is suitable for self study. This mean I want it to have exercises with answers (It would be ideal if it had solutions). I have already read ...
0
votes
1answer
105 views

Max(x,y) and argmax(x,y)

I am writing my report and I got confused on this simple maths concept. What I need is: I have 2 values i.e x and y and I want to use the maximum of either x or y as my length. So which statement is ...
0
votes
2answers
1k views

A fair dice is rolled five times. What is the probability of getting at least 2 sixes and at least 2 fives? [closed]

A fair dice is rolled five times. What is the probability of getting at least 2 sixes and at least two fives?
3
votes
1answer
86 views

Solve difference equation

Fix a real number $a\not=0$. How to solve recursive equation $a_{n+1}+(2-na)a_n+a_{n-1}=0$. Even a solution for a prescribed value of $a$ should be fine.
0
votes
1answer
40 views

$if An \subseteq A $ for all $n \in \mathbb{N}, $ then $ \bigcup_{n=1}^\infty An \subseteq A $

I was given this as an exercise in my discrete math class and I have been having a lot of trouble, I am not really sure how to approach a problem like this. Any help is appreciated!Thank you! (this is ...
1
vote
1answer
69 views

Combinatorial Question using ramsey's theory or pigeonhole principle??

We are currently going over pigeonhole principle, ramsey's theorem (graphs and such). Stuck on this particular question: Within a group of an odd number of people, show that at least one person knows ...
1
vote
1answer
59 views

Help mathematical induction

Prove by mathematical induction. I was hoping if someone could give me a hint on how to solve this problem. $$\frac{1}{1^2}+ \frac {1}{2^2} + ....+ \frac{1}{n^2} < 2 - \frac {1}{n} $$ for all ...
1
vote
1answer
24 views

Prove for any $n \geq 1$…Recursion?

I am practicing review problems to practice from what what we last learnt in lecture, and I admit I am very lost. I have no idea how to start these sort of problems Prove for any $n \geq 1: F_1 + ...
1
vote
1answer
30 views

Proof using sets and infinimums

Let $S$ and $T$ be nonempty sets of real numbers, bounded below. Prove that $$\inf(S\cup T) = \min \{\inf S,\inf T \} $$ So the answer almost seems obvious here, I get that obviously the inf of the ...
0
votes
1answer
36 views

Solving a Recurrence Relation

In my research, I encountered the following recurrence relation: \begin{align} g(t) &= (\beta-1) \; g(t-1) + \beta \; f(t)\\ f(t) &=\min\{f(t-1)+g(t-1), \, c \cdot \lambda^t \} \end{align} ...
0
votes
1answer
38 views

Applications discrete math

A racketeer is allowed to bring no more than 3 of the 7 lawyers representing him to a Senate hearing. How many choices does he have? This is what I have done but the correct answer is 64. I'm not ...
1
vote
1answer
92 views

Prove $A $ \ $B $ = $A \cap B^c $

I see the use of $A $ \ $B $ = $A \cap B^c $ being used in bigger problems but how do you prove this? Is the proof as simple as: $A $ \ $B $ $\iff$ $ x \in (A \setminus B) \iff x\in A \cap ...
0
votes
3answers
73 views

I am trying to prove this as a tautology , contradiction without using a truth table.

Is the statement form $((\lnot p \wedge q)\wedge (q \vee r))\wedge (\lnot q \wedge r)$ a tautology, contradiction or neither? I know it's simple just can't get started.
2
votes
2answers
59 views

Prove $(A^c)^c = A$

Hey guys I know this is a super easy example but, this is my first day doing this stuff and i really need to get the basics down. Is this how to go about proving $(A^c)^c = A$ $$ \begin{align} ...
1
vote
2answers
187 views

combination and permutation !!!!

I have 3 questions that i had a try to do but i didn't understand them could anybody please help me to solve these questions. For Q1 i know how to use the multiplication counting procedures for a) i ...
0
votes
2answers
260 views

List of calculation rules for asymptotic notation?

Background: I am working my way through CLR/CLRS's proof of the master theorem (section 4.4 in the 1st and 2nd editions of Introduction to Algorithms), and I'm doing my own write-up of this proof1 ...
4
votes
2answers
256 views

A die is thrown five times, what is the probability that you get 20 as the sum of the values

This is supposed to be a Inclusion-Exclusion problem. We have $6^5=7776$ different results. Now, with the Inclusion-Exclusion principle i resolve the number of solutions for the equation: ...
1
vote
0answers
37 views

Showing an inequality relating two Poisson tail-probabilities

In my research, I've discovered that a property that I am interested in is equivalent to an inequality involving two tail-probabilities of the Poisson distribution. I belive this inequality to be ...
2
votes
1answer
27 views

Question with nonempty bounds and sets

Let $A$ and $B$ be nonempty sets of real numbers, bounded above and below. Prove that if $A\cap B$ is also nonempty, then $infB\leq supA$. So my train of thought goes like this: I'm picturing that ...
0
votes
1answer
533 views

Discrete Math - Proving/Disproving set identities

I understand that this means that (A and B) or C = A and (B or C), but how would you prove or disprove these set identities. Any help would be appreciated, Thanks
0
votes
2answers
61 views

Reflexive relation on set of $n$ elements [duplicate]

How many reflexive relations are there on a set of $n$ elements? I did the problem and I got the answer $2 ^ {n ^ 2}$. Is it correct? Thanks for the help..!!
2
votes
3answers
126 views

Elevator Problem (Sample Space)

Carefully describe the events $A$, $B$, $A\cup B$, and $A\cap B$ in the following sample space: Six people enter the elevator in the basement of a building with 6 floors. Each states where they will ...
1
vote
1answer
43 views

Proving $n^2$ is even whenever $n$ is even via contradiction?

I'm trying to understand the basis of contradiction and I feel like I have understood the ground rules of it. For example: Show that the square of an even number is an even number using a ...
0
votes
1answer
53 views

True or False: $A_i$ Set Theory

$\displaystyle \bigcap_{i=1}^nA_i\subseteq \bigcap_{i=1}^{m+n}A_i\ $ and $m>0$ I have to describe whether or not this statement is true. From my understanding it is False, but I'm not sure if my ...
-5
votes
2answers
182 views

Induction of $A_i$ [duplicate]

The base case $n=1$: $B\cup\left(\bigcap_{i=1}^1A_i\right)=B\cup A_1$ and $\bigcap_{i=1}^1(B\cup A_i)=B\cup A_1$. Now, suppose inductively that ...
1
vote
1answer
110 views

Is proving both sides of iff necessary?

I have always been taught to prove both ways of an "if and only if" statement in a formal proof, but if the opposite way is very similar to the proof of the first way. Can you just leave a note and ...
0
votes
2answers
85 views

Sample Space & Random Experiment (Hat Check)

The hatcheck experiment with n = 4 hats. (In this experiment, n people check their hats. When someone comes to claim his/her hat, they are given one of the unclaimed hats, not necessarily their own. ...
-1
votes
2answers
55 views

Discrete Math: Ways to Prove Induction

The point of mathematical induction is to prove $\forall x\geq b[P(x)]$ by instead proving $P(b)\wedge \forall x\geq b[P(x)\rightarrow P(x+1)]$ ($b$ is often, but not always, $0$ or $1$). However, ...
0
votes
1answer
39 views

Empirical formula of coverage probability

Can someone explain me how this formula calculates the coverage probability. Suppose I have a time series of size $n$. Then I can fit a model to this series and get its one-step ahead forecast and ...
1
vote
2answers
148 views

How can I find the number of solutions to integer inequalities with multiple unknowns?

I've just learned how to find the number of integer solutions of this kind of inequations, $$x_1 + x_2 + \dots + x_k = n, \qquad(x_i\geq0)$$ which is $\binom{n+k-1}{k-1}$. But I have no idea about ...