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

Discrete Math: Implication

If $\neg(P) \to \neg(Q) = Q \to P$ works as a Rule, then why doesn't $\neg(P) \to \neg(Q) = P \to Q$ work as a rule.
1
vote
1answer
53 views

Graphing digraphs with the following vertex set

Just want to make sure I did this correctly.. I think I did part a) correctly? Here is my solution for part a) Not sure how to do b) and c) though. Any advice would be great. Thanks in advance
1
vote
1answer
37 views

Proof of cardinalities sets

Prove that the cardinality of set $A^{B+C}$ is equal to the cardinality of $A^{B}\times A^{C}$. I think I need to make functions from $B+C$ to $A$ and one from $B$ to $A$ and one from $A$ to $C$. I ...
0
votes
0answers
71 views

Does the graph exist with these degrees?

$(11,2,2,2,2,2,2,2,1)$ Is it possible that a degree of a vertex can be 11 ? However, there are only 9 vertices. Does the graph exist?
0
votes
2answers
104 views

Prove the inclusion-exclusion formula

We just touched upon the inclusion-exclusion formula and I am confused on how to prove this: $|A ∪ B ∪ C| =|A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|$ We are given this hint: To do ...
0
votes
1answer
50 views

context-free languages operation closure

The following operation is defined on formal languages. $ operation1(L) = \lbrace w \ | \ wxy \in L, \ \forall x \forall y \ (|x|=|w|) \ \wedge (|y| = |w| ) \rbrace $ Prove that context-free ...
0
votes
1answer
82 views

Discrete Mathematics Fibonacci Sequence

I am studying for the final exam in my Discrete Mathematics class and came upon the following problem on the study guide we were given. Given the following algorithm: If $n = 0$, then $f(n) = 0$ ...
0
votes
1answer
75 views

General solution to discrete dynamical system.

I am trying to find the general solution to the following discrete dynamical system: $$H(n+1) = 0.89H(n) + 30$$ $$E(n+1) = 0.64E(n) + 0.11H(n)$$ $$o(n+1) = 0.88o(n) + 0.36E(n) + 30$$ $H(0) = 3500$ ...
0
votes
1answer
121 views

What is the walk of this graph?

A walk that is not a trail from vertex 1 to vertex 3; A trail that is not a path from vertex 1 to vertex 3; A path from vertex 1 to vertex 3. How can I describe these walks?
0
votes
3answers
69 views

Proof By Induction $2^n \ge n^2$ for $n\ge4$

I am trying to prove the following, and here is what I have done: Can somebody help to complete this? $2^n \ge n^2$ for $n\ge 4$ $n=4$, LHS: $2^4 = 16$, RHS: $4^2=16$, $16=16$ Therefore TRUE Assume ...
0
votes
1answer
20 views

Solving Through The Use Of Handshakes.

Let $G$ be a graph. Use the Handshake Theorem to prove that $\delta(G)\nu(G) \le 2\varepsilon(G) \le \Delta(G)\nu(G)$. So the first step to solve this I know is that you need to know what ...
1
vote
2answers
47 views

Proof DES is injective - is this a valid argument

Without going too much into detail into the crpytography of the matter since not every mathematician is interested or knowledgable in the field, there is an encryption process called DES (data ...
-1
votes
1answer
105 views

Prove multivariable function is surjective?

I am a little confused on how to prove a multivariable function is surjective(onto). The function is $f: \mathbb N^2 \to \mathbb N$ such that $f(a,b) = a^b$ I tried thinking of a counter example but ...
0
votes
0answers
44 views

about complement of a graph

Let $G$ be a $k-$regular graph on $n$ vertices. we know that if $k\geq n/2$, then $G$ is a connected graph. Now, if we take complement of graph $G$ and denote it as $\bar G$ then $\bar G$ will be ...
2
votes
2answers
44 views

Proof By Induction $n^2 > 3n$ where $n\ge 4$

I am trying to prove the following example, however I seem to be getting a little stuck: For $n\in\mathbb N$, $n\ge 4, n^2>3n$ What I have Done: Base Case:$ n=4$, LHS: $4^2 = 16$, RHS: $3\cdot 4 ...
0
votes
1answer
53 views

Fast Fourier Transform Splitting Algorithm

I'm trying to figure out how the FFT splitting algorithm works. I've pretty much understood the general idea, but when I try to compute it, I get something completely different than what I expect $ ...
2
votes
1answer
62 views

Proving a property about modulus

I seem to be having a lot of trouble finding a place to start in proving that $$(a \cdot b) \mod m = ((a \mod m) \cdot (b \mod m)) \mod m$$ Any ideas on how I should go about doing this? I've been ...
0
votes
1answer
92 views

I am trying to use proof of sequence correctly to make valid

Here I am trying to use a proof sequence so that the argument is valid (hint: the last A’ has to be inferred). (A → C) ∧ (C → B') ∧ B → A' Here are my steps I tried but not sure if this is correct ...
0
votes
0answers
207 views

Trying to justify each step correctly in proof sequence

I am trying Justify each step in the proof sequence below for correctly with [A → (B ∨ C)] ∧ B' ∧ C' → A' So I justified my steps here but I am not sure at 1 to 3 if I did it correctly. A → (B ∨ ...
1
vote
1answer
74 views

Symbol clarification

Okay, so I've read a few different meanings for the exclamation point in a statement. For example: $$!\exists x \in O \ni 2x < 5$$ The only question I have is about the Exclamation point in front ...
1
vote
1answer
45 views

What would the expected number of swaps in a merge sort be?

If I were given a list of random numbers say x1, x2, .........., xn and these numbers are sorted according to the merge sort algorithm. What would be the number of expected swaps/exchanges which would ...
1
vote
1answer
68 views

solving a recurrence without initial conditions

I have been working on this problem for two days... I can only get as the characteristic part of the recurrence, I just can't figure out a proper guess for the particular solution. ...
1
vote
1answer
71 views

Approach to determining if a graph is planar by inspection/kuratowski's theorem

I'm taking an intro discrete math course and am having trouble determining if a graph is planar or not. When proving a graph is planar, if Euler's formula doesn't apply I just randomly redraw the ...
1
vote
1answer
32 views

Possible configurations on the subset problem

Let $A=\left\{ a_{i}\right\} $ be a sequence of $n$ positive numbers such that $\sum a_{i}=1$. We define $C\left(A\right)=\left\{ \left\{ b_{i}\right\} \subset\left\{ 1,2..,n\right\} :\sum ...
1
vote
2answers
61 views

Complex infinity ($1/0$) [duplicate]

I've learned that $$1/0$$ is postive and negative infinity, but if I ask wolfram mathematica to calculate $$1/0$$ it gives me: 'complex infinity' but how can we proof that that is true?
2
votes
3answers
972 views

What is the easiest way to determine the accepted language of a deterministic finite automaton (DFA)?

I'm new to automata theory and I'm currently working on some exercises on determining the accepted language of DFAs. I was wondering whether there exists some clever strategy to determine the accepted ...
1
vote
2answers
37 views

Is transitive closure defined uniquely?

I'm encountering questions where I'm required to find a transitive closure (and the questions seem to suggest that there is only one), but I probably don't understand something in the definition, ...
1
vote
2answers
379 views

What is the formula to find the number of one-one functions from $A$ to $B$?

Let $p$ be the number or elements in $A$. Let $q$ be the number of elements in $B$. If the number of functions from $A$ to $B$ is equal to $q^p$, then: What is the formula to find the number of ...
0
votes
1answer
61 views

non-homogenous linear recurrence relation general questions

what happens if you have both repeated and non-repeated roots? i know there are different forms for both, so if given roots say $5, -3, -3, -3$ would it then be $A(5)^n + B(-3)^n + Cn(-3)^n + Dn^2 ...
0
votes
2answers
46 views

Help Showing a Relation is/isn't a Partial Order

Define the relation $\le$, as $(a,b)\le(c,d)$ if and only if $a+b\le c+d$ and $a\le c$. Is this a partial order? I know it's definitely not if we remove the $a\le c$ (because then it's not ...
1
vote
1answer
114 views

Is a total order compatible with a partial order?

I was given the following multipart problem. Part 1: Consider the poset ({2,4,6,9,12,18,27,36,48,60,72},|), with the indicated integers and the divides relation. Find the following, if they exist; ...
0
votes
2answers
31 views

Is there a term for an “unbounded simplex”?

Is there a general term for regions like $\{(x,y):x>y\}$ and $\{(x,y,z): x>y>z\}$, i.e., regions which are simplexes with one open?
0
votes
1answer
89 views

4 cards are shuffled and placed face down. Hidden faces display 4 elements: earth, wind, fire, water. You turn over cards until win or lose.

Question: 4 cards are shuffled and placed face down in front of you. Their hidden faces display 4 elements: water, earth, wind, fire. You turn over cards until win or lose. You win if you turn over ...
0
votes
0answers
106 views

Partial Ordering and Hasse Diagram.

Draw the Hasse diagram for the partial ordering “x is a factor of y” on the following sets: S = {2, 3, 5, 7, 21, 42, 105, 210} I don't know how to find the partial ordering of this set. I know that ...
4
votes
4answers
72 views

Proving $2^n -1 = \sum_{i=0} ^{n-1} 2^i$ for all $n\geq 1$ by induction

I'm practicing proofs by induction, and equalities seem to be the toughest for me. Can somebody please help to prove that for all integers $n \geq 1$: $$ 2^n -1 = \sum \limits _{i=0} ^{n-1} 2^i\;? $$ ...
4
votes
5answers
151 views

Proving $6^n - 1$ is always divisible by $5$ by induction

I'm trying to prove the following, but can't seem to understand it. Can somebody help? Prove $6^n - 1$ is always divisible by $5$ for $n \geq 1$. What I've done: Base Case: $n = 1$: $6^1 - 1 = ...
0
votes
4answers
89 views

Proof by Induction $3^n > n^3$

I am trying to prove the following, however I'm stuck at the Induction hypothesis Prove by induction that, for all integers $n$, if $n\geq 5$, then $3^n>n^3$ What I have Done: Base Case: $n ...
-1
votes
1answer
42 views

Is this Event Mutally Exclusive?

I am trying to calculate the following, however I'm unsure on whether this event would be Mutally Exclusive or Independent. Can someone help with finding the probability of the Intersection? P(A) ...
2
votes
1answer
84 views

Find generating functions for the Perrin and Padovan sequences

The Perrin sequence is defined by $a_0 = 3, a_1 = 0, a_2 = 2$ and $a_k = a_{k-2}+a_{k-3}$ for $k \ge 3$. The Padovan sequence is defined by $b_0 = 0, b_1=1, b_2=1$ and $b_k=b_{k-2}+b_{k-3}$ for ...
3
votes
2answers
180 views

Find the coefficient of $x^4$ in the expansion of $(1 + 3x + 2x^3)^{12}$?

I have not learnt the multinomial theorem yet, and was trying to approach this using the binomial theorem. I divided the terms as $a$ being $(1+3x)$ and $b$ being $2x^3$. I then used $${12\choose ...
1
vote
2answers
51 views

Summation Proof Dealing With 3s Multiples [duplicate]

So the problem is as follows: Prove that if the sum of digits of a decimal $n$ is three's multiple, then n is three's multiple by direct proof. For example, $11234567$ is 3's multiple because ...
3
votes
2answers
55 views

Multiple part problem concerning the proof that $\sum_{k=1}^n k^3=\left(\frac{n(n+1)}{2}\right)^2$ by induction

So I'm having trouble with $c,d$ and $e$. For $c$ so far I have: Inductive Hypothesis: $(\frac{n(n+1)}{2})^2 = (\frac{(k+1)(k+2)}{2})^2$ is that correct?
1
vote
1answer
71 views

Derive an exact formula (solve the recurrence definition) for the following recursive sequence:

Derive an exact formula (solve the recurrence definition) for the following recursive sequence: $s_n = 2_{s_n-1} - s_{n-2}$ where $n \ge 2$, and $s_0 = 4$, $s_1 = 1$. So I saw someone solving this by ...
1
vote
2answers
47 views

Proving $10^n \equiv 1 \pmod 3$ for all $n\geq 1$ by induction

Prove that $10^n \equiv 1 \pmod 3$ for all positive integers $n$ by mathematical induction. Can someone please help me in solving this problem and explain what's going on? Any guidance would be ...
2
votes
1answer
69 views

Combinatorics Question VS CS solution!

I was wondering for some conceptual understanding to a question of this form: In how many ways may we choose three distinct integers from [1, 2, ..., 80] so that one of them is the average of the ...
1
vote
2answers
29 views

Verify that $\alpha(a)\neq2$ for all $a$ where $\alpha(x): (2x + 1)/(x + 2)$

If $A= \mathbb{R} \setminus \{-2\}$ and $B = \mathbb{R} \setminus \{2\}$, let $\alpha: A \to B$ by $\alpha(x): (2x + 1)/(x + 2)$. Verify that $\alpha(a)\neq2$ for all $a \in A$. As a hint, I was ...
4
votes
3answers
70 views

You are making cookies and add N chips to dough randomly, and split it into 100 equal cookies, again at random. How many chips should go into dough?

Question: You are making chocolate chip cookies. You add N chips randomly to the dough and you randomly split the dough into 100 equal cookies. How many chips should go into the dough to give a ...
-5
votes
3answers
86 views

Proving that $2^n+1\leq 3^n$ by induction [closed]

I need to prove the following using mathematical induction: $$2^n+1\leq 3^n\qquad\forall n\in\Bbb{Z^+}$$ Been working on this problem for a while and cannot figure it out. Any guidance or help would ...
0
votes
2answers
64 views

How do you compute a 90% and 95% confidence interval for a guesstimation problem?

Question: How would you estimate the weight of Mount Everest? Give a 90% and 95% confidence interval. I would define what Mount Everest is. Including its boundaries (length, width) and estimate the ...
3
votes
2answers
19 views

A linear non homogeneus recurrence relation

Im using the minimax algorithm for a very simple game and when counting the tree nodes found the recurrence $T(n)=T(n-1)+T(n-2)+1$, with $0$ and $1$ as initial values. I tried generating functions: ...