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

Complex infinity ($1/0$)

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
0answers
30 views

PROVE : $y∈\mathbb{N}$ and $\sqrt{y} ∈ \mathbb{Q}$ then $\sqrt{y} ∈ \mathbb{Z}$

$ y∈\mathbb{N}$ and $\sqrt{y} ∈ \mathbb{Q}$ then $\sqrt{y} ∈ \mathbb{Z}$ Prove that, if $n$ is a natural number and $n$ has a rational square root then, the square root on $n$ is an integer.
1
vote
3answers
18 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
18 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, ...
-2
votes
3answers
37 views

Proving $6\mid A$ when $(x^3 +y) - (y^3 +x) = A$ [on hold]

Given that $x,y\in\mathbb{Z}$, prove that the difference between the expressions $(x^3 +y)$ and $(y^3 +x)$ is a multiple of $6$.
0
votes
0answers
11 views

Prove multivariable function is injective?

I am a little confused on how to prove a multivariable function is injective(one to one). I know the process for single variables but got stuck sadly. The function f: N -> N such that f((a,b)) = a^b ...
1
vote
2answers
23 views

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

let p = number or elements in A let q = number of elements in B if the number of functions from A to B is equal to q^p.... is their formula to find the number of one-one functions from A to B? how ...
1
vote
1answer
24 views

transitive closure and number of elements in relation?

I see an example as follows: in relation $R=\{(a,b), (b,c), (b,d), (c,e), (d,e), (c,f), (e,a) \}$, on set $\{a,b,c,d,e,f\}$. we have $30$ elements in the transitive closure of $R$. How number of ...
0
votes
0answers
27 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 ...
1
vote
2answers
29 views

How to prove this recurrence [on hold]

Been stuck on this problem for a good while. Not sure how to approach it any help would be great! It is problem 12.
0
votes
1answer
18 views

Is it possible to reconstruct signal using phase only or magnitude only?

I am studying Fourier Transform and it's inverse. We get phase and magnitude from Fourier transform and reconstruct it back from both together My question is that is it possible to reconstruct given ...
0
votes
2answers
27 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
votes
0answers
12 views

p = X^2 and X = {a,b,c,d} [on hold]

Which ordered pairs need to be added to the universal relation p = X^2 on the set X = {a,b,c,d} to create the equivalence relation p* generated by p?
1
vote
0answers
16 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
22 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
0answers
25 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
18 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 ...
3
votes
5answers
52 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
95 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 = ...
-1
votes
0answers
24 views
0
votes
4answers
64 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
31 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
0answers
35 views

question asks when is the birthday??? [duplicate]

Question asks how to find out Cheryl's birthday??
2
votes
1answer
26 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 ...
2
votes
2answers
45 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
41 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
39 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
votes
0answers
27 views

Combinatorics: Password consisting of 13 characters. Must contain at least one odd digit, and at most two even digits. How many passwords?

I'm really trying here. I just need help where to go next. Each character is one of the 10 digits 0, 1, 2, ... , 9 What I have so far is that there are 10^13 possible passwords. I'd have to subtract ...
-2
votes
0answers
47 views

Summation Direct Proof Help [on hold]

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 1+1+2+3+4+5+6+7=24, and in fact, 11234567 ...
1
vote
1answer
22 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
36 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
49 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
28 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 ...
3
votes
3answers
38 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 ...
-4
votes
3answers
74 views

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

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
27 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
15 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: ...
1
vote
2answers
60 views

Proving $A$ is a subset of $B$

I'm trying to understand the proof behind showing a set is a subset of another set, but I'm struggle to do so. Can some one help using this example to show: $A \subseteq B$? Here $A = \{x | x = 4n ...
2
votes
1answer
45 views

Proving $(p\to q)\land(p\to r) \equiv p\to(q\land r)$ using logic laws — short cut or incorrect?

Working through this problem: Using logic laws, show that the following are logically equivalent: $$(p\to q)\land(p\to r)\qquad\text{and}\qquad p\to(q\land r).$$ The way I did the problem is ...
2
votes
1answer
19 views

How many subsets of $S$ are there that contain $x$ but do not contain $y$?

Let $S$ be a set of size $37$, and let $x$ and $y$ be two distinct elements of $S$. How many subsets of $S$ are there that contain $x$ but do not contain $y$? This question is on a practice exam ...
-4
votes
2answers
51 views

Power Set Of a Complement of an Infinite Set?

In order to find a Power Set of (B \ A), an infinite Set, would you keep finding elements until both sets have one in common? For example: $$\begin{align} A &= \{x \mid x = 2n, n \in \mathbb ...
2
votes
2answers
50 views

Calculate Intersection with a Non Finite Set?

What is the best way to answer Intersection or Union based questions with a set that is not finite? such as this: Calculate: $A \cap B$ $$\begin{align} A&=\{x\mid x=n+9, n\in\mathbb N\}\\ ...
0
votes
0answers
11 views

Hasse diagram of cartesian product?

I have been looking at how to draw Hasse diagrams, and I have found examples of divisibility. I understand these and how to construct them, but is it possible to draw a Hasse diagram for a cartesian ...
0
votes
1answer
58 views

Proving 'All multiples of 10 are even numbers'

I made 2 equations: $A = \{n:n=10k \text{ for some } k∈N\}$ $B = \{n:n=2j \text{ for some } j∈N\}$ I solved for the equation if it is possible, so I wrote: $2j = 10k$ I used an arbitrary value ...
2
votes
1answer
39 views

Prove that any group of 14 people must contain either 5 mutual friends or 3 mutual strangers.

So I think I have the answer to this problem, but there's something about it that's bothering me: Suppose we choose a fixed point with $13$ edges coming out of it. There must be at least $a)$ $9$ ...
-1
votes
2answers
48 views

How do I simplify just using 2 logic operations?

I need simplify the following proposition to 2 logic operations using the laws of the algebra of propositions. Write each step on a separate line with the algebra law you used as a justification. ...
2
votes
0answers
25 views

Determine the possible grouping

Consider I have a set of $3$ object $1,2 $ and $ 3.$ What is the possible grouping? I'll have either $\{(1,2,3)\}$ or $\{(1),(2),(3)\}$ or $\{(1,2),(3)\}$ or $\{1,(2,3)\}$ or $\{(2,(1,3)\}.$ So, I'll ...
-1
votes
2answers
55 views

Expected values of a dice game with a 30-sided die and a 20-sided die.

Two people, $A$ and $B$, have a $30$-sided and $20$-sided die, respectively. Each rolls their die, and the person with the highest roll wins. ($B$ also wins in the event of a tie.) The loser pays ...
2
votes
1answer
21 views

Possibilities of license plates with special rules

I have looked all over the web for some additional information on this matter with no results. Lets say a new form of license plate have 4 letters followed by 3 digits and all sequences are possible. ...
1
vote
2answers
42 views

Probability that every player is dealt a heart

We've got a standard, 52-card deck. We're playing Bridge with 4 players, so every player is dealt 13 cards. There are $\frac{52!}{13!13!13!13!}$ ways to deal the cards to the four players. (Intuition ...