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

How do I find a common solution of this recurrence equation?

Find a common solution of this recurrence equation: $y_{n+2} - 2 y_{n+1} - 8 y_n = \sin (n+1)$ Consider the homogeneous equation $y_{n+2} - 2 y_{n+1} - 8 y_n = 0$. It has a common solution $y_n = c_1 ...
2
votes
2answers
25 views

Establishing the validity of an argument.

I've been trying to determine the validity of a particular argument for some time now and I've had no luck in figuring it out. The argument in question goes as follows: \begin{align} & p \wedge q ...
1
vote
6answers
53 views

Discrete Mathematics: $mn + 2m + 2n + 2 = n$ proof of uniqueness of $m$, $\forall n \in \mathbb{Z}$

Prove: There exists a unique integer $m$ such that for every integer $n$: $$mn + 2m + 2n + 2 = n$$ However I am not sure if my proof is correct. How do I prove uniqueness of $m$? I prove it by ...
1
vote
3answers
27 views

Is there a 5-regular graph of order 7?

How can I decide if there is a 5-regular graph of order 7? Some hints or tips would be appreciated. This question arises in studying for a graph theory course.
0
votes
0answers
8 views

Uniform distribution find CRLB/UMVUE [on hold]

X_1,….,X_n be iid U(0,θ) ,θ>0 how can I find UMVUE of g(θ) find I(θ) show that 1/I(θ) >Var(θ ̂ ) why the CRLB are fail I know need to show unbiased estimator and complete of g(θ),but don^' ...
1
vote
1answer
95 views

I want to learn math from zero

I finished high school 2 years ago and now I'm stuck in a university in Turkey. I am interested in learning precalculus, discrete mathematics, physics and chemistry. Question: I need to learn math ...
0
votes
3answers
52 views

Induction proof for natural numbers

I am unable to proceed with the below claim. $$2^{m} \times 2^{n} = 2^{m+n}$$ Could anyone let me know how to prove the above claim using induction proof? I was able to derive proof for odd natural ...
1
vote
2answers
25 views

components of a vector

If I have the angle between two vectors and , I have the components (x,y,z) of the first vector ( xi + yj + zk) how can I know the components (x,y,z) of of the second vector ?
0
votes
2answers
38 views

Calculating interaction beween 100 objects with each other.

The other day I was thinking about how many interactions 100 objects would have with each other. By that I mean if we are using a computer to draw the scene with 100 point lights, the total result ...
1
vote
1answer
50 views

Proving this equivalence relation

If $X,Y$ are reflexive, symmetric, and transitive, then $X \times Y$ is an equivalence relation where ${(a,b):a\in X, b\in Y}$. I am trying to self learn these topics. I do know what an ...
5
votes
4answers
224 views

For every positive integer $n, n^2 + 4n + 3$ is not a prime

Prove: For every positive integer $n, n^2 + 4n + 3$ is not a prime. I tried to disprove the statement, which I could not using several number examples with constructive proof. However I am not sure ...
0
votes
3answers
51 views

Combinatorics Question (discrete math) [on hold]

In how many ways can one mark 6 blocks on a grid of 5 columns and 3 rows such that in every row at least one block will be marked? An explanation will be appreciated! Thanks a lot
1
vote
2answers
34 views

methods of proof, discrete mathematics

"Disprove: For all integers $r, m,$ and $n$, if $r$ divides $mn$ then either $r$ divides $m$ or $r$ divides $n$." I am not sure if I am on the right track To disprove I try the negation of a ...
0
votes
0answers
21 views

Evaluate the sum $n$ of geometric random variables

Let $X_i\sim G\left (1-\frac{1-i}{n}\right)$. Evaluate $ \sum_{n=1}^n X_i$ My Try: $$ \sum_{i=1}^n X_i = \sum_{i=1}^n \sum_{k=1}^\infty \left(\frac {i-1}{n}\right)^{k-1}\left( 1 - ...
0
votes
0answers
35 views

Find the finite sequence that minimizes the value of $T_5(P)$

Given a finite sequence $P(a_1,b_1),(a_2,b_2),...,(a_n,b_n)$, define $T_1(P):=a_1+b_1$, $\forall 2\leq k\leq n$, $T_k(P)=b_k+\max\{T_{k-1}(P),a_1+a_2+...+a_k\}$. Let $m=\min\{a,b,c,d\}$. ...
2
votes
1answer
54 views

Maximization problem related to set of common representatives

We are given set $\{1, \dots n\}$ and requested to construct $A = \{A_1 \dots A_s\}$, where $|A_i|=k$, $|A| = s$, $A_i \subset \{1, \dots n\}$. We say that $S$ is a minimal set of common ...
2
votes
2answers
58 views

Set theory intersections and unions

I'm in an intro to discrete mathematics course, and this is a question on my first homework. I showed what I have so far, I think the answer to the first part of the question may be right, but I'm ...
2
votes
1answer
37 views

Set of common representatives and pigeonhole principle in one problem

We are given set $\{1, \dots n\}$ and $A = \{A_1 \dots A_s\}$ such as $|A_i|=k$, $|A| = s = \binom n k$, namely $A$ contists of all possible subsets of size $k$. We say that $S$ is a set of common ...
0
votes
2answers
47 views

Exclusion-Inclusion principle.

I have this problem in discrete maths (combinatorics) which nags me. We have a computer system, where a password is of length of at least 3 signs and at most 100 signs. The premitted signs to use ...
1
vote
1answer
56 views

Basic Set Theory regarding the set $\{0\}$

For each nonnegative integer $n$, let $U_n = \left \{n,−n\right \}$. Find $U_1,\:U_2,\:\text{and}\:U_0$. $U_1 = \left \{1,−1\right \}, U_2=\left \{2,−2\right \}, U_0 = \left \{0,−0\right \} = \left ...
0
votes
2answers
31 views

Big $O$ estimate of $(n\log n+1)^2+ (\log n +1)(n^2+1)$

Give the Big $O$ estimate of $(n \log n +1)^2 + (\log n +1)(n^2+1)$ Taking big $O$ of the first function (ignoring constant and exponent), ($n\log n + 1)^2$ we get $O (n \log n)$ Taking big $O$ of ...
-7
votes
0answers
41 views

Stochastic Process random process [on hold]

Full Details please about the stochastic process ( random process)
-1
votes
1answer
66 views

Check if Sequence is Graphic: 8, 8, 7, 7, 6, 6, 4, 3, 2, 1, 1, 1 [duplicate]

This is part of my Discrete Math homework and I have no idea how to solve this. I am given this sequence: $8, 8, 7, 7, 6, 6, 4, 3, 2, 1, 1, 1 $ I have to check whether it is graphic or not. How do ...
1
vote
4answers
75 views

Help with proposition whether it's true or false [on hold]

Is this proposition true or false? $$\exists y \in \mathbb R \;\forall x \in \mathbb R\,(xy\neq x \rightarrow x=0) $$ And why?
0
votes
0answers
19 views

Closed $SL_2(\mathbb{Z})$ conjugacy class [on hold]

For what matrices $A \in SL_2(\mathbb{R})$ is the conjugacy class by $SL_2(\mathbb{Z})$ closed ?
2
votes
2answers
35 views

Determine whether each of the functions $2^{n+1}$ and $2^{2n}$ is $O(2^n)$.

Determine whether each of the functions $2^{n+1}$ and $2^{2n}$ is $O(2^n)$. Since $2^n$ < $2^{n+1}$, you can say $2^{n+1}$ is not $O(2^{n})$ Since $2^n$ is < $2^{2n}$, you can say $2^{2n}$ ...
0
votes
1answer
23 views

Verify answers to these big o notation questions

May someone look over if I did these big o notation problems correctly? Some of them were tricky. 1) $f(x) = 10 = O(10)$ 2) $f(x) = 3x + 7 = O(x) $ 3) $f(x) = x^2 + x + 1 = O(x^2) $ 4) ...
3
votes
2answers
60 views

Show that $\mathbb{Q}\times \mathbb{Q}$ is denumerable [duplicate]

I am new to functions and relations, and with some concepts I am not so familiar. I have a question in an homework: Show that $\mathbb{Q} \times\mathbb{Q}$ is denumerable. From what I ...
2
votes
3answers
104 views

How does $\log(x^2 + 1)$ become $\log(2x^2)$?

My textbook attempts to take the big O of $\log(x^2 +1)$. It proceeds by saying $x^2 + 1 \le 2x^2$ when $x \ge 1$. But I don't know how it came up with this idea. Question: Why set $x^2+1$ to a ...
15
votes
1answer
55 views

Find all $A\subseteq\mathbb{N}$ such that $A=\{|a-b|:a,b\in A\}$.

For a set $A$ of real numbers, denote $$A^\ast:=\{|a-b|:a,b\in A\}.$$ Question: Find all finite subsets $A\subseteq\mathbb{N}$ of the natural numbers such that $$A^*=A.$$ Attempt: The empty ...
1
vote
0answers
14 views

Estimating the discrete laplacian to prove recurrence of simple random walk for d=2

Given a function $f : \mathbb Z\times \mathbb Z \rightarrow \mathbb{R}$ we define the discrete laplacian of $f$, $\triangle_df$, by the following rule $\triangle_df(x,y)= \dfrac{f(x + 1, y)+f(x, y + ...
0
votes
0answers
36 views

Finding $2^{2^n}$ mod $m$

Is there any special technique for finding $2^{2^n} \pmod m$? Taking $n$ and $m$ to be very high. Approx till $10^4$
-1
votes
1answer
18 views

Relation Proofs on finite set [duplicate]

I have this problem I can't figure out how to do it Suppose A and B are finite sets and $f : A → B$ is surjective. Is it true that the relation $“|A| < |B|”$ is a sufficient condition for claming ...
-2
votes
1answer
32 views

Infinite Set Proof (Countable and Uncountable ) [on hold]

I can't figure out this problem, I have to prove that $\mathbb Q \times \mathbb Q$ is enumerable, but I have no idea how to do it. Thanks
3
votes
1answer
42 views

What is the discrete log used for?

Perusing Wikipedia, I stumbled on the discrete logarithm. I looks interesting that we'd be able have a function that could solve $b^k=g$ for integers $b,k,$ and $g$. However, Wikipedia says "No ...
-3
votes
1answer
30 views

Show that $a$ is minimum [duplicate]

If $(A,<)$ totally ordered, show that if $a$ is a minimal element of $A$ then $a$ is minimum. Could you give me a hint how we could do this? Definitions: Let $(A, \leq)$ be an ordered set. We say ...
0
votes
1answer
27 views

Reachability relation set

How can i define reachable relation set of R for a given di-graph below?
1
vote
1answer
27 views

Combinations - no repetition for mirrors?

My question is, if there is a simple explanation as to why mirrors aren't counted twice with binomials such as it is in the case it's not a mirror? Here is an example: Consider the elements {1, 4}. ...
1
vote
1answer
17 views

Find #committee of 8 from 3 freshmen, 4 sophomores, 4 juniors, and 5 seniors contain at least one of each class

The question: A student council consists of three freshmen, four sophomores, four juniors, and five seniors. How many committees of eight members of the council contain at least one member from ...
2
votes
2answers
39 views

Maximum number of relations?

The question is that we have to prove that if $A$ has $m$ elements and $B$ has $n$ elements, then there are $2^{mn}$ different relations from A to B. Now I know that a relation $R$ from $A$ to $B$ is ...
3
votes
0answers
39 views

Number of functions from domain to codomain

Let A and B be finite sets. Let a be the size of A. Let b be the size of B. Assume 0 < a < b. (a) How many functions are there with domain A and co-domain B? (b) How many one-to-one functions ...
2
votes
2answers
67 views

Probability for having consecutive success in an experiment

A friend asked me the following question: "In an experiment, we are tossing a fair coin 200 times. We say that a coin flip was a success if it's heads. What is the chance for having at least 6 ...
-1
votes
1answer
53 views

Hasse diagram question about relations

I have the following Hasse diagram below, the question is given specific generalised quantifiers I have to list the subsets of {a,b,c,d} which the quantifier corresponds to. I have completed the ...
2
votes
1answer
33 views

Derivatives defined on a discrete state space

Ive been looking at certain economic papers, and optimal control papers. They define a state variable, $\omega$, which follows a discrete time Markov Chain. Then they define a utility function ...
0
votes
2answers
61 views

Probability that n people collectively occupy all 365 birthdays

The problem is quite simple to formulate. If you have a large group of people (n > 365), and their birthdays are uniformly distributed over the year (365 days), what's the probability that every day ...
1
vote
1answer
54 views

How does the function work? [closed]

Could you explain me the function of the following two algorithms? ...
0
votes
1answer
10 views

Is there a closed form expression for the Taylor series of (1- a X - b Y - c XY )^ (-1)?

Is there a closed form expression for the Taylor series of f(X , Y ) = (1- a X - b Y - c XY )^ (-1) ? a, b and c are constants X and Y are thank you
1
vote
2answers
101 views

An exercise from Knuth's book - Proving a formula by induction

I would like to find a formula for this sum: $$ \frac{1^3}{1^4+4} - \frac{3^3}{3^4+4} + \frac{5^3}{5^4+4} - ... + \frac{(-1)^n(2n+1)^3}{(2n+1)^4+4} $$ The answer given (Knuth's book, The Art of ...
0
votes
1answer
27 views

Creating equation for a given recurrence relation

I'm studying discrete math in the university, and we are given questions and answers for some problems, and I dont understand most of them. So I need help understanding one of them... Appreciate the ...