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
2answers
36 views

Prove if the following is true or provide a counterexample if it is not

For all sets A and B, |P(A × B)| $\ne$ |P(A) × P(B)| My first instinct is that it is false and I picked sets like A = {1}, B = {2} but when you write out the power set of these sets you end up with ...
0
votes
0answers
16 views

Does loops affect a graph when I'm creating a trail or path?

I have read that in order for there to be a trail, no edges must be repeated in the walk and for a path there must be no repeated vertices. However, it doesn't say anything about whether or not loops ...
0
votes
1answer
34 views

Why do (the ranges of) these sequences intersect?

Let $\{(a_n,b_n)\}$, ($1\le n\le N$) be a finite sequence and $\{(s_n,t_n)\}$ ($n\ge 1$) be an infinite sequence, both in $(\{0\}\cup \mathbb{Z}^{+})^2$. We have $a_1=0$ and $b_N=0$. Also, either ...
0
votes
1answer
44 views

Mini Tetris Winning Configuration

So here's the problem: A winning configuration in the game of Mini-Tetris is a complete tiling of a 2 x n board using only the three shapes shown in Figure 1. By allowing rotations, there can be ...
0
votes
1answer
68 views

Proving $\binom {n-1}{r-1}=\sum_{k=0}^r(-1)^k\binom r k \binom{n+r-k-1}{r-k-1}$

Prove the identity: $\displaystyle\binom {n-1}{r-1}=\sum_{k=0}^r(-1)^k\binom r k \binom{n+r-k-1}{r-k-1}$ It looks a bit similar to the "no gets their own hat back" problem or inclusion exclusion ...
1
vote
2answers
71 views

Recursively defining sets of strings discrete math

So here are the two problems: Recursively define the set of bit strings K that do not have 00 as its substring. How many bit strings of length 10 are included in the above set K? Can someone ...
0
votes
2answers
33 views

Evaluate nested summation of a function

I'm trying to relearn summation simplification, I haven't touch math in a while. I'm having trouble simplify this nested summation down and I don't even know where to start. Could anyone please give ...
0
votes
2answers
22 views

Find a recurrence relation and initial values for W(n), the number of words of length n from alphabet {a,b,c} with no adjacent a's.

Find a recurrence relation and initial values for W(n), the number of words of length n from alphabet {a,b,c} with no adjacent a's. This is a problem from How to Count: An Introduction to ...
-2
votes
0answers
23 views

Recursively defining sets of strings [duplicate]

So here are the two problems: Recursively define the set of bit strings K that do not have 00 as its substring. How many bit strings of length 10 are included in the above set $K$? For (1) I got ...
0
votes
2answers
26 views

How do I find a partition of an equivalence relation?

Say I have the function: $$x\,R\,y \iff y = 3^k$$ for some $k \in \mathbb Z$ and the set is: $$A = \{1,1/3,1/27,1/4,3,1/36 , 2,2/9,9/4, 5\}$$ So in this scenario, how do I find the partitions of the ...
0
votes
2answers
51 views

Prove or disprove: There exists a prime p > 3 such that p + 2 and p + 4 are also prime

I'm having a lot of difficulties with this proof. Can someone please solve it and explain to me what's going on at each step? Thank you!
1
vote
2answers
34 views

Proof by Elements to Show $D^{c} ⊆ A^{c}$

Use proof by elements to verify that for all nonempty sets $A$, $B$, and $D$ if $A ⊆ B$, $D^{c} ⊆ B^{c}$, then $D^{c} ⊆ A^{c}$. Here's the proof I have written so far. I have gotten feedback that ...
-1
votes
1answer
46 views

Binary strings and recurrence relations [closed]

So the problem is: How many binary strings of length n contains 111? Give a recurrence relation Tn, where Tn is the number of binary strings of length n that contains 111. How could we possibly ...
0
votes
0answers
39 views

Solving RSA cipher without calculator

I have a question: Encrypt the message UPLOAD using RSA with $n=3\cdot 31$ and $e =17$. My question is, how can I solve this with a calculator and in an efficient manner due to being in an exam ...
0
votes
0answers
28 views

how to prove that the proof by induction is true using the rules of inference?

As given in the title, how can we prove that? I tried to solve it but I don't feel that it is true? (I'm new to discrete mathematics though) Proof by induction has three steps: -1- Base case ...
1
vote
0answers
33 views

Inviting 4 friends out of 8 for a week such that each friend visits at least once

Dave is inviting 4 friends out of 8 for a week how many possibilities there are such that each friend visit at least once. Let's number the friends for brevity, 1 to 8. This is like asking how ...
1
vote
2answers
16 views

The Null Subset of a Given Defined Set

Given the set $A = \{\{$∅$\},\{2\},2\}$, determine if the following statements are false. If false, then correct the statement to be true Determine the validity of: $\{$∅$,\{$∅$\}\} ⊆ A$ ...
2
votes
1answer
73 views

If there is an injection $f: X \to Y$ with $m=n$ then $f$ is a bijection.

The Statement of the Problem: Let $X,Y$ be finite sets with $ \lvert X \rvert = m $ and $ \lvert Y \rvert = n $. Prove the following statement by induction on $ m \ge 1$: If there is an injection ...
0
votes
0answers
26 views

Proof that graph is 2-connected

Let $G=(V,E)$ be graph where $|V| \geq 3$. For any three vertices $x, y, z$ there is path from $x$ to $y$ in G that it doesn't contain vertex $z$. How can I proof that G is 2-connected in terms of ...
0
votes
1answer
19 views

How to find the order of G using the size of G and its complement

If the size of graph G is 19 and the size of its complement G-bar is 17 then find the order of G?
0
votes
1answer
49 views

Proving these are logically equivalent?

How to prove that these are logically equivalent using laws? a. $p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)$ I used the Conditional law and DeMorgan's Law and eventually arrived at $-(p ∨ q) ∧ -(p ∨ q)$ but ...
0
votes
0answers
37 views

Edge and vertex connectivity of bipartite graph

Let graph $G=(V,E)$ be bipartite graph with partite sets $X = \{x_1, \ldots, x_n\}$ and $Y = \{y_1, \ldots, y_n\}$. Vertices $x_i$ and $y_j$ are connected with edge if and only if $i \neq j$. What ...
3
votes
2answers
30 views

How to simplify expression with Fibonacci numbers

I have to simplify the expression $\sum_{n=0}^\infty \sum_{k=0}^n \frac{F_{2k}F_{n-k}}{10^n}$. I only noticed that $\sum_{n=0}^\infty \sum_{k=0}^n \frac{F_{2k}F_{n-k}}{10^n} = \sum_{n=0}^\infty ...
0
votes
1answer
37 views

Proof by Contradiction to show that if $f^{-1}$ exists, $f$ must be onto

Use proof by contradiction to prove that if $f^{-1}$ exists, then $f$ must be onto where $f:A→B$. Proof: I think the contradiction of the theorem would be: if $f$ exists then $f^{-1}$ must be ...
1
vote
2answers
63 views

Showing $(f^{-1}∘g^{-1})=(g∘f)^{-1}$

If the functions $f$ and $g$ are both bijections then the in inverse of the composition function $(f∘g)$ will exist. Show that it will be $(f^{-1}∘g^{-1})=(g∘f)^{-1}$ For the proof assume ...
0
votes
1answer
17 views

Does a statement have to be true for all conditions to be transitive,symetric,reflexive?

I'm trying to determine if the following are symmetric, reflexive, transitive, equivalence for all-natural numbers but am struggling because they aren't in set notation. Examples of confusing ...
0
votes
2answers
35 views

How to find the actual doubling time with the rule of 72.

I have a programming assignment in C# from my professor that involves the Rule of 72. He clearly says that in order to find the amount of time in years it will take for an amount to double, you have ...
4
votes
1answer
100 views

In the card came “Projective Set”, show that 7 cards do always contain a set. [duplicate]

In the game of Projective Set, it turns out that any seven cards contain a projective set. How can one prove this? And for fewer than 7 cards, how can we determine the probability that one or more ...
0
votes
1answer
25 views

What separates an axiom from a proposition?

I have read that an axiom is defined as "an obvious truth." I have also heard that an axiom is a truth so obvious that no proof could make it more clear. My question is: why is one thing considered an ...
1
vote
3answers
235 views

Solving this recursive relation

I want to solve this recursive relation: $$i_{n+1}=4i_{n}+9$$ where the $i_1=t$ that $t \in \mathbb{N}$ I tried to make like relation about Tower of Hanoi, but no good thing happened. How can I do ...
1
vote
0answers
21 views

Does bitwise-XORing substrings results in a uniform distribution?

Let's say I have an integer $k$ whose bit string representation can be exactly divided into $l$ substrings of length $\log_2(m)$. Let's call each one of these substrings $B_i(k)$, for ...
-1
votes
0answers
21 views

Is there any other way to model Seven Bridge of Königsberg? [closed]

Can we Model and solve Königsberg problem or similar problem using mathematical Programming? if the answer is yes How to write the mathematical programming model for this problem?
0
votes
1answer
22 views

Summation simplification explanation

I'm trying to understand summation for my algorithm course and it has been a while since I took discrete math. Could any body please explain how does summation simplification work from the problem ...
1
vote
2answers
33 views

Equivelence classes, how many there are, and how many elements they have.

I've been struggling to understand equivalence classes. Say I have a set T, the set of all binary strings, and the relation S on T = {(a,b) | length(a) = length(b)}. How would I write down the ...
0
votes
1answer
24 views

What is the Largest Input Size? [closed]

Suppose a machine on average takes $10^8$ seconds to execute a single algorithm step. What is the largest input size for which the machine will execute the algorithm in two seconds assuming the number ...
1
vote
2answers
46 views

Generating function for a sequence

Please provide a clue on how to solve the following problem: Find a closed form for the generating function for the sequence $\{a_n\}$, where $a_n = 1/(n+1)!$ for $n=0,1,2...$ I know this looks like ...
0
votes
4answers
117 views

If a function maps A to its PowerSet, is it Surjective?

Given an arbitrary set A, let F : A → 2^A be the function defined for all a ∈ A by f(a) = {a} If A maps to its power set, does this make F surjective? If somebody could help to prove this that ...
1
vote
0answers
23 views

The relationship between an equivalence relation, equivalence classes, and partitions?

So I'm struggling right now to understand the concepts behind equivalence relations, equivalence classes, and partitions. This is what I understand about all these topics right now: Equivalence ...
1
vote
2answers
21 views

Antisymmetric Relation: How can I use the formal definition?

So I can determine whether a certain relation is antisymmetric, by using a digraph. My understanding through a digraph is that if there is only 1 way streets and/or loops between edges, it's ...
1
vote
0answers
10 views

graph has no bridge iff a spanning subgraph of the graph is the support of a flow

A $\textit{bridge}$ of a graph $G=(V,E)$ (finite graph and we allow loops and multiple edges) is an edge $e$ whose removal disconnects $G$. Let $\mathcal{O}$ be an orientation of the edges of $G$. ...
0
votes
0answers
44 views

Prove that every connected graph whose vertices are all of even degree has no cut-vertices

I am trying to prove that every connected graph whose vertices are all of even degree has no cut-vertices. Now, I am not very good with proofs but I was thinking about proving it by contradiction, ...
0
votes
1answer
29 views

join-semilattice vs Upper-semilattice ?! definition problem ?!

In mathematics, a join-semilattice (or upper semilattice) is a partially ordered set that has a join (a least upper bound) for any nonempty finite subset. I ran into some definition challenge. I ...
-1
votes
0answers
18 views

Meaning of Square and cube of matrix of relation

Let a stand for the airport in the city of Manchester, let b stand for the airport in Boston, c stand for the Chicago airport, d for the airport in the city of Denver. $M_R$ =$\matrix{&a & b ...
0
votes
1answer
30 views

Given the following, is there equivalence relation?

Let $n$ be an integer. On the set $F$ of all integer-valued functions of a set $A$, suppose we define $f$ and $g$ to be related if $f(a)\equiv g(a)\pmod{n}$ for every $a\in A$. Is this an equivalence ...
0
votes
1answer
20 views

Complementary Relation Proof

If $R$ is reflexive, prove that $R^c$ is irreflexive. If $R$ is asymmetric, prove that $R^c$ is reflexive. Where $R^c$ = complement of $R$. I just can't figure out anything to say for the first one ...
2
votes
2answers
46 views

Power set of a subset

Proof that if $A \subseteq B$, then ${\mathscr P}(A) \subseteq {\mathscr P}(B)$. I tried using the definition of a subset: $A \subseteq B = \forall x(x \in A \to x \in B)$, but get stuck as to how to ...
1
vote
3answers
74 views

Why is $f(n)=n^2+3$, where $f\colon\mathbb{N}\to\mathbb{Z}$, not an onto function?

Question: $f_2 :\mathbb{N} \to \mathbb{Z}, f_2(n)=n^2 +3$ Using algebra, making $y=f(n)$, isolating for $n$ and plugging in the expression back, I get $n$. However, the answer key says it is not ...
0
votes
0answers
21 views

Help Representing Equivalence Classes

In the set $\mathbb{Z}$, we define two integers $x$ and $y$ to be equivalent ($x ≈ y$) if and only if $x \operatorname{div} 10 = y \operatorname{div}10$. How would one select a representative from ...
0
votes
1answer
31 views

Axiom of Induction Question

I have to use the axiom of induction to prove the summation of k^3 from 0 to n is $(n(n+1)/2)^2$. Here's what I have so far: Let P(n) be the assertion that $0^3+1^3+⋯+n^3=(n(n+1)/2)^2$ Base Case ...
0
votes
1answer
28 views

Quick Recurrences Question [closed]

$$given: T(n)=4T(n/2)+n^2 ;T(1)=1\\=4[4T(n/2^2 )+(n/2)^2 ]+n^2\\=4^2 [4T(n/2^2 )+(n/2)^2 ]+n^2+n^2\\=4^3 [4T(n/2^3 )+(n/2)^2 ]+n^2/4+n^2+n^2\\…\\=4^k T(n/2^k )+$$ Here is where I'm stuck because I'm ...