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

Show that each of these conditional statements is a tautology. Please show each step and the laws you use.

This is what I have so far, any suggestion?? a) ¬p→(p→q) ≡¬ p∨(¬p∨q) ≡¬ p∨¬(¬p∨q) ≡¬ p∨(p∧¬q) ≡(¬p∨p)∧(¬p∨¬q)
0
votes
1answer
38 views

Using rule of inference to deduce conclusion

(a) ~q (b) (p v r) --> q (c) ~p (d) ~r --> (m v b) (e) b --> ~f (f) f (g) (~p ^ m) --> n (h) (~p ^ b) --> k ...
0
votes
2answers
24 views

Simplifying question regarding sigma and permutation

http://i.stack.imgur.com/wEiqF.png $$\frac{1}{n!}\sum_{i=0}^n (-1)^i {n\choose i}.$$ How can THIS be simplified to 0 when n is positive?
0
votes
0answers
40 views

Finding an acceptable set of permutations from a given contingency table

I have the following data set of a human population. The data set captures households and relationships of the persons living in those households. My problem is how to group the individuals into ...
0
votes
0answers
61 views

Having some difficulty that involves the order of nested qualifiers.

I have a question that states. Let Q(x, y) be the statement “x has sent an e-mail message to y,” where the domain for both x and y consists of all students in your class. Express each of these ...
-1
votes
1answer
59 views

Can a false implications converse ever be true?

I have tried wrapping my head around this, and i cant seem to find a false implication whose converse is true. I dont think it is possible. In other words a false implication would be if not p, ...
-1
votes
1answer
39 views

Permutations: Show that the sign of a 2-cycle is -1

I'm supposed to show that the sign of a 2-cycle is -1, and I'm not allowed to use the formula: $\text{sign}(f) = (-1)^l$ (where $l$ describes the number of 2-cycles that compose the permutation $f$) ...
0
votes
3answers
49 views

Absolute value counter example

Give a counterexample, if possible, to this universally quantified statements, where the domain for all variables consists of all integers. $∀x(|x|>0)$. I think the counterexample is as simple as ...
2
votes
2answers
39 views

How do I change ∃x, ∀y, P(x, y) into ∃y, ∃x, P(x, y)?

I'm very confused as to how to even begin, any explanation or help would be really appreciated. I understand Universal and Existential Quantifiers but the actual process of proving it is what confuses ...
0
votes
1answer
33 views

Checking if a statement is a Taututology

I have this question As per http://web.stanford.edu/class/cs103/tools/truth-table-tool/ This statment is not a tautuology.So is the question wrong?
0
votes
0answers
27 views

Perron vector of the distance matrix of a tree

Increasing properties of perron vector of distance matrix from the vertex corresponding to which row sum is minimum
2
votes
2answers
152 views

Writing a Closed form expression Discrete maths

$$∑_{i=1}^n a_i=n^2-n$$ Write a closed form expression for $$∑_{i=1}^{n-1} a_i$$ in terms of n and then simplify. Hello, Just asking this question to see if this answer is right. I'm still not 100% ...
0
votes
1answer
48 views

Summation change of index and limits

My brain isn't working today (I thought this would be simple) but I can't figure out how to change from this summation equation $ \sum _{n=1}^N a^n$ to this one $ \sum _{j=1}^? [a^{2j-1} + a^{2j}] ...
1
vote
2answers
34 views

Show that if $T$ is a subset of $S$ having more than $16$ elements then $T$ contains two elements whose distance is at most $2$.

Let $S = \{0000000, 0000001, ... , 1111111 \}$ be the set of all binary sequences of length $7$. The distance of two elements $s_1 ,s_2 \in S$ is the number of places in which $s_1$ and $s_2$ ...
2
votes
0answers
36 views

Find an explicit formula for $ψ(α,β;s)$ using the floor and ceiling functions

Suppose $0 ≤ s ≤ 1$, $α,β > 0$ and $⌊α⌋ > ⌊β⌋$. Let $ψ(α,β;s)$ be the least positive integer $n$ such that $⌊nα+s⌋ ≠ ⌊nβ+s⌋$. Find an explicit formula for $ψ(α,β;s)$ using the floor and ...
0
votes
1answer
180 views

Checking Validity of Arguments using Rules of Inference

Im trying to understand how a theorem or statement is proved using Rules of Inference.I have this example I really don't understand how they say.Now p->q may be true with p being false.Then ...
4
votes
1answer
52 views

Show that all solutions of this map tends toward infinity

Let $r≥4$ be a positive intger. Let us consider the difference non-autonomous equation: $$u_{n+1}=(1+r^{2n+1})u_{n}-r^{2n-1}u_{n-1}+2 \tag{*}$$ All solutions of $(*)$ have the form: ...
5
votes
4answers
81 views

Why would Inclusion-Exclusion be used here?

I'm trying to do some discrete mathematics work and I am told I need to use Inclusion-exclusion, but I really don't see why the exclusion would be needed? The question: What is the number of ways ...
0
votes
2answers
25 views

Scope of De Morgan's law?

Suppose I have a statement like this: (~p ^ ~q) V (p ^ q) If I understand this correctly, I can apply the law to both sides separately while leaving the OR in the middle intact. Leaving this: (p V ...
4
votes
1answer
410 views

How many positive integers less than 1000 have distinct digits and are even?

I am not looking for an answer on this. Just need to clarify why my approach is failing - N1 + N2 + N3 i.e. single digit, double digit, 3 digit single = 2, 4, 6, 8 i.e 4 double = X non-zero = 8*4 = ...
1
vote
2answers
39 views

Sets: Unions and Intersections.

Let $A$ and $B$ be sets with $|A|=10$ and $|B|=7$. What can we say about $|A \cup B|$? In particular, find two numbers $x$ and $y$ for which we can be sure that $x \le |A \cup B|\le y$ and then find ...
0
votes
2answers
48 views

discrete- mathematical proof to support the statement

lets assume i have three children , tim,jack and juliet. currently tim is 14 years old , jack is 10 years and juliet is 6 years old. next year => tim:15, jack=11, juliet=7 and so on.... Is it ...
0
votes
0answers
21 views

How to assign weights based on predefined rules?

I have a set of values "V" and a set of rules "R". Based on the rules, I have to come up with a set of weights "W" such that if R says that v1 has highest priority then w1*v1 > wj*vj for all values of ...
1
vote
1answer
228 views

How do I write a closed form expression for $\sum _{i=0}^{n-1}$ in terms of n?

I am given this:$$\sum _{i=1}^n a_i = n^2-n,a_0=4$$ How do I write a closed form expression for $$\sum _{i=0}^{n-1}$$in terms of n? I know that for $$\sum _{i=1}^{n-1}$$ the expression would be ...
1
vote
2answers
23 views

What is the union and intersection of these sets?

What is $\bigcup_{n=1}^\infty[n,n+1]$? What is $\bigcup_{n=1}^\infty(n,n+2)$? What is $\bigcup_{n=1}^\infty(n,n+1)$? What is $\bigcup_{n=1}^\infty(1/n,1]$? (Original image here.) I don't ...
1
vote
1answer
67 views

Discrete math: how to start a problem to determine reflexive, symmetric, antisymmetric, or transitive binary relations

I need to determine if the following relation is reflexive, symmetric, antisymmetric, and/or transitive. I have been reading a lot of similar posts about these topics on here, but I am still stumped. ...
0
votes
1answer
35 views

Help calculating intersection and unions of sets

Let $N \ge 0$ be a natural number. What is $\bigcup_{n=1}^N [-n,n]$? What is $\bigcap_{n=1}^N [-n,n]$? For the Union, is it just all the sets [-1, 1], [-2, 2] ... [-N, N]? and for the ...
0
votes
1answer
61 views

Proof involving $R^n$ and the transitivity of a relation

I want to prove: R is the relation on the set A. If R is transitive, then $R^n$⊆$R^{n-1}$ for n = 2, 3, 4,... I'm having trouble approaching this proof, I've started my proof by induction in ...
6
votes
1answer
75 views

With how many ways can we place 20 cars in 30 spots.

So we have 4 white cars, 6 black cars, 6 blue cars and 4 silver cars. We want to place them in a 30 spot parking. We choose to place the cars with the following order white cars first, then silver ...
2
votes
1answer
47 views

Balls in boxes: a variation

We have $n_1$ indistinguishable balls of type $1$, $n_2$ of type $2$, $n_i$ of type $i$ ($i=1, \ldots, m$) to distribute among $k$ distinct boxes. No box can be left empty or contain balls of more ...
2
votes
1answer
73 views

How to convert to disjunctive normal form?

The formula is: $\lnot((s \lor \lnot p) \land (q \land r))$ and what I've done so far is this: $\lnot(s\lor\lnot p) \lor\lnot(q\land r) $ $(\lnot s\land p) \lor (\lnot q\lor\lnot r)$ After this ...
0
votes
1answer
29 views

How to convert floating point base X to base Y, where X < Y

What is the process to convert between two floating point numbers. An answer that explains this process for arbitrary bases is preferred. Specifically, I would like to convert from a smaller base to ...
3
votes
1answer
24 views

Prove that among the 43 difference $d_i = a_{i+1}+a_i$, $i=1,…,43$ some value must occur at least 10 times

Let $a_1<a_2<...<a_{43}<a_{44}$ be positive integers not exceeding $125$. Prove that among the $43$ differences $d_i = a_{i+1}-a_i$, $i=1,...,43$ some value must occur at least $10$ times. ...
1
vote
1answer
13 views

Assumption about the form of solutions to a recurrence relation

Basically, when solving such recurrence relations, we try to find solutions of the form $a_n = r_n$, where $r$ is a constant. $a_n = r^n$ is a solution of the recurrence relation $a_n = c_1a_{n-1} + ...
3
votes
1answer
104 views

Triangulation of Lattice Polygons

What's a neat proof that every lattice polygon can be split into elementary triangles? By a lattice polygon I mean a polygon with vertices on some equidistant grid; by an elementary triangle I mean a ...
1
vote
1answer
64 views

Draw Venn diagram for this situation

This year 120 students receive gold star, 180 students receive certificates and 80 students receive blue ribbon. Of these, 40 students receive gold star with no other award, 50 students receive ...
0
votes
1answer
43 views

Number of Delannoy paths that never go below the line $y = x$

How would I go about calculating $D(a,b)$ the number of such paths for some a,b. Say $a,b<=4$ and then express $D(a,b)$ in terms of another delannoy number? I have calculated $D(a,b)$ using a ...
2
votes
1answer
53 views

How do I disprove a set is not a subset of another set?

Given that $T=\{3t|t \in\mathbb Z\}$, $Q=\{5q|q \in\mathbb Z\}$, $R=\{6r|r \in\mathbb Z\}$ and $S=\{T,Q,R\}$. How can I disprove that Q $\subseteq$ R? I tried the following: Let $q=2, Q={10}$ ...
0
votes
2answers
45 views

Math induction problem. [duplicate]

How to prove the following with induction? $$\sum_{k=1}^{2n} \frac{1}{k(k+1)} = \frac{2n}{2n+1}$$ I have difficulty solving this example. I got past base part where I prove that $L(1) = P(1)$ but I ...
1
vote
1answer
72 views

When to use brackets in symbolic logic?

I'm a little confused on when to use brackets in symbolic logic. My initial knowledge was that it was to reduce ambiguity. I've seen that p ^ (q v r) does not ...
1
vote
3answers
70 views

Prove that $1^2 - 2^2 + 3^2 - 4^2 + \cdots + (-1)^{n-1}n^2 = \frac12(-1)^{n-1} n (n + 1)$, where $n $ is a positive integer

Prove that $1^2 - 2^2 + 3^2 - 4^2 + \cdots + (-1)^{n-1}n^2 = \frac12(-1)^{n-1} n (n + 1)$, where $n $ is a positive integer How do I prove the above expression using mathematical induction? So ...
1
vote
1answer
81 views

Recurrence relation and deriving generating function

Let the sequence an be given by the recurrence relation $$a_n = −2a_{n−1} + 8a_{n−2}$$ $$a_0 = 1, a_1 = 5$$ (a) Calculate $a_2, a_3$ and $a_4$. (b) Derive an exact expression for the generating ...
0
votes
2answers
98 views

what will be the strategy that detects the fake coin? [duplicate]

I am facing problem on understanding this problem--- You have 12 coins and a balance scale, one of which is fake. All the real coins weigh the same, but the fake coin weighs less than the rest. All ...
-2
votes
1answer
42 views

Simplifying a 4-term equation using boolean algebra

1432928 So, I have a logical expression: $(\lnot A\land B\land C\land \lnot D)\lor (\lnot A\land B\land C\land D)\lor (A\land \lnot B\land \lnot C\land D)\lor (A\land \lnot B\land C\land D)\lor ...
3
votes
3answers
65 views

Arranging marbles in a row so that every red marble is adjacent to a green marble.

Suppose we have $m$ red marbles and $n$ green marbles, where marbles of the same color are identical. I would like to find out how many ways the marbles can be arranged in a row so that every red ...
3
votes
0answers
27 views

Trouble at translating natural language to propositional logic and proving conclusion from it.

Given this set of premises: Something in the forest I hadn't observed was not the dark ruler Something which had been noted means worth to be remembered Something I had seen in the forest not ...
0
votes
1answer
19 views

Fast Fourier transform with a different product function

Problem Given 2 N degree polynomials as $$a_0 + a_1x+a_2x^2+...+a_Nx^N $$ and $$b_0 + b_1x+a_2x^2+...+b_Nx^N $$ Assume no 2 coefficient are same in the 2 polynomials. Find the product of the ...
-2
votes
1answer
59 views

Prove that every positive integer n can be expressed as… Proof please. [closed]

Prove that every positive integer $n$ can be expressed as $$n=c(k)2^k+c(k-1)2^{k-1}+\ldots+c(2)\cdot 2^2+c(1)\cdot 2+c(0)$$ where the coefficents $c(i), i=0,\ldots,k$ can only be $0$ and $1$.
-2
votes
1answer
45 views

Inequality involving Fibonacci numbers [closed]

If $F(n)$ are Fibonacci's numbers then prove that $$1< \frac{F(n+1)}{F(n)}<2$$ for all $n>2$
0
votes
1answer
48 views

A combinatorial proof of identities

I need to prove combinatorial identities following: $$ S(n,k) = \sum\limits_{i=1}^n (S(n - i, k - 1)\cdot k^i) $$ $$ S(n,k) = k\cdot S(n - 1, k) + k\cdot S(n - 1, k - 1) $$ where $S(n,k)$ is ...