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

Cantor-Bernstein Theorem proof help? [duplicate]

I know this problem has something to do with the Cantor-Bernstein Theorem, but how do I show that the set of natural numbers $\mathbb N = \{0,1,2,3,\dotsc\}$ has the same cardinality as the set of ...
2
votes
1answer
49 views

Infinite Pigeonhole Proof?

Suppose we arrange finitely many pigeons in infinitely many pigeon holes. How do I use the Infinite Pigeonhole Principle to prove that there are infinitely many pigeonholes that contain no pigeons.
2
votes
2answers
34 views

Recurrence relations help please? [closed]

How do I solve this recurrence relation? $$ a_k = a_{k-1} + k $$ when $a_0 = 2$.
0
votes
1answer
23 views

How do I simplify this expression a $4\times 2^{k-1}$?

I know this can be very simple for many of you, I know the answer is $2^{k+1}$ but I don't know how that's the answer. and where can I see the rules for simplifying this kind of expressions.
3
votes
2answers
97 views

Solve the following recurrence relation: $S(1) = 2$; $S(n) = 2S(n-1)+n2^n, n \ge 2$

Solve the following recurrence relation: $$\begin{align} S(1) &= 2 \\ S(n) &= 2S(n-1) + n 2^n, n \ge 2 \end{align}$$ I tried expanding the relation, but could not figure out what the closed ...
1
vote
3answers
67 views

How to find the solution of $T(n,m) = T((n-1),m) + T(n,(m-1))$ in terms of big $O$ notation?

I would like to solve the recurrence $T(n,m) = T((n-1),m) + T(n,(m-1))$. I think the solution is $$O(2^{n+m})$$ because in every step you can reduce either $n$ or $m$ by one or not, but I can not ...
2
votes
1answer
33 views

Find number of circular arrangements possible

If 20 persons were invited for a party, in how many ways will two particular persons be seated on either side of the host in a circular arrangement? According to me the answer should be $17!.2!$. But ...
1
vote
3answers
36 views

For $x,y \in \mathbb R - {2}$, $x * y = xy - 2x -2y + 6$. Find the identity element.

I'm struggling to answer these kind of questions. In general, the way I set up these kind of problems is $a * e = a$, apply the particular operation to $a$ and $e$ and see if I can arrive at value for ...
3
votes
2answers
171 views

What is a good book for reviewing high school math, and preparing for university?

I'm signing up for University soon (Compsci program) as a mature student. It's been a long time since I've done any math, and I went as far as grade 11 in high school. So, I'm looking for a book that ...
4
votes
4answers
1k views

Prove that the graph is connected

I was wondering if someone can help me understand how prove that this graph is connected. Given a graph with n vertices, prove that if the degree of each vertex is at least $(n − 1)/2$ then the graph ...
0
votes
1answer
119 views

How to find out transient response of z-transform (discrete)

Given z-transform transfer function $H(z) = \frac{Y(z)}{X(z)}$, with the corresponding linear ODE, how does one find out transient response of such a transfer function given a certain input?
0
votes
4answers
70 views

if $f:X \to Y$ is 1-1 and $|X| = |Y|$, does that imply $f$ is onto?

Similarly, if $f$ is onto and both sets have the same cardinality, does that imply $f$ is 1-1? I'm pretty sure both statements are true but I'd rather not assume. Thank you for your time.
2
votes
1answer
62 views

How do I find nine messages which are unchanged by RSA encryption using the public key $(3869, 3)$.

I understand how RSA crytosystem works, however I am not sure how to apply it to answer these questions. Can someone explain please? Let $N=3869$ and be the product of two distinct unknown odd prime ...
0
votes
0answers
61 views

How to use mobius-inversion to solve this problem?

Currently, I'm trying to solve this problem using mobius-inversion. the function f(d) means the number of (i, j, k) equals d, and function g(d) means the numbers that satisfying: d | (i, j, k). Then ...
4
votes
6answers
210 views

(14^2014)^2014 mod 60 without a calculator

Calculate without a calculator: $\left (14^{2014} \right )^{2014} \mod 60$ I was trying to solve this with Euler's Theorem, but it turned out that the gcd of a and m wasn't 1. This was my ...
1
vote
1answer
13 views

When can you not do a mapping composition?

Suppose I have $\alpha:\mathbb R^3 \to \mathbb R$ and $\beta:\mathbb R \to \mathbb R^+$. Looking over my notes, it says $\alpha \circ \beta$ can not be done but $\beta \circ \alpha$ can. What is the ...
1
vote
2answers
31 views

Are they using Vandermonde's Identity here?

Consider a set of $5$ men and $7$ women. Then there are $\binom 53 \binom 72$ groups consisting of $3$ men and $2$ women. What they are doing looks very much like this identity: $\binom {m + n}{k} = ...
0
votes
1answer
16 views

Find $x$ for $[809x] = [214]$ in $\mathbb Z_n$ where $n= 5124$ s.t $0 \le x < 5124$.

The following is dealing with equal classes under congruence modulo $n$. I was told to use my answer for $[809x] = [1]$ in $\mathbb Z_n$ where $n=5124$ s.t $0 \le x < 5124$, so basically it's ...
0
votes
1answer
8 views

Choosing subsets out of a set by using lists

Suppose we need to choose sets of size $2$ out of $\{A, B, C\}.$ The answer is given by $\frac {n!}{ (n - k)! k!}$. So, $n! = \{\text {ABC ACB BCA BAC CAB CBA}\}.$ What lists do $(n - k)!$ and $k!$ ...
-1
votes
3answers
111 views

Use mathematical induction to prove a statement [closed]

Use mathematical induction to prove that: $$A\cap\left(\bigcup_{i=1}^nB_i\right) = \bigcup_{i=1}^n\left(A\cap B_i\right)$$
1
vote
1answer
17 views

proving property of polynomial that is composite

Show that $a^m+1$ is composite if $a$ and $m$ are integers greater than 1 and $m$ is odd. [$Hint:$ Show that $x+1$ is a factor of the polynomial $x^m+1$] So I tried doing it and got a result which ...
0
votes
2answers
67 views

Prove by induction that for a natural number a there exists integers $x, y$ where $a = 7x + 2y?$

I am trying to get my head around induction at the moment and found this problem in a textbook. I think that I should be doing induction on $a$, but I can't even see where to start the proof.
3
votes
5answers
65 views

Sets $A,B,C$ with $B\subseteq C$, prove that $(A-B)-C=A-C$

Ran across this and couldn't figure out how you would give a formal proof. It seems intuitive, in that $(A-B)-C$ is the elements in $A$ but not in $B$, and then also remove the elements from $(A-B)$ ...
0
votes
2answers
307 views

Find the probability that an integer selected between 1 and 5000 is divisible by at least one of 3, 5 and 7

I'm having a hard time finding the solution. I can find integers that are divisible by only one of them, but there are many that are divisible by two of them. That's the problem. Find the probability ...
2
votes
0answers
47 views

Hasse Diagram Correct?

I've had to make Hasse Diagrams before, but they've always been, for lack of a better word, pretty. The lines haven't had any complicated back and forth or the like. The jump that 4 and 6 have to do ...
6
votes
1answer
52 views

Generalized way to solve $x_1 + x_2 + x_3 = c$ with the constraint $x_1 > x_2 > x_3$?

On my example final exam, we are given the following problem: ...
3
votes
1answer
59 views

Number of hairs of inhabitants and the population of a city

There is a town T where the population is greater than the number of hairs of each inhabitant. That is, if we count the number of hairs on the head of any inhabitant of the town, the amount will be ...
1
vote
2answers
27 views

Are Cartesian Product and Multiplication (kind of) equivalent?

Example(not trying to prove anything): $|\{X, Y, Z\}| \times |\{A, B\}| = |\{XA, XB, YA, YB, ZA, ZB\}| = 3 \cdot 2 = 6.$
2
votes
1answer
62 views

Discrete Mathematics

I am having great difficulty trying to understand a question I have found and am keen to finding the solution and would appreciate any help. "Suppose that ten computer programs have been submitted ...
0
votes
1answer
38 views

Discrete Mathematics Sets Help

Hi i'm having difficulties working this question out I found, any help would be appreciated :) Let $A = \{1,2,4\}$ and $B = \{1,2,3\}$. Define the function $f: A\to B$ by the rule. What is the ...
0
votes
1answer
12 views

Bijection between lists and sets

Multiplication Principle as given in my textbook: Consider two element lists for which there are $n$ choices for the first element, and for each choice of the first element there are $m$ choices ...
3
votes
2answers
123 views

Combinatorial proof $n {2n \choose n} = (n+1) {2n \choose n+1}$

I want to prove combinatorially that $n {2n \choose n} = (n+1) {2n \choose n+1} $. I have noticed that ${2n \choose n}$ is the number of ways walking only north or east in a square from a corner to ...
0
votes
1answer
37 views

Cardinality multiplication in counting problems

Multiplying things seems to be my weakest point, so I am trying to understand as much as possible. Consider $\sum^k_{j = 0} \binom mj \binom n{k - j}$. It's the answer to the question: "from a class ...
2
votes
2answers
128 views

Experiment: Roll three 6-sided dice.

Are the following probabilities correct? I'm not very confident with probabilities and would just like these double checked please. Thank you. Experiment: Roll three 6-sided dice. a) Find the ...
0
votes
2answers
21 views

Lattice orders and number of elements in a set

My discrete mathematics lecture notes give the following definition of a lattice order: A 'Partial order R is a lattice order if the set of lower bounds for any two elements $x, y ∈ X$ has the ...
1
vote
3answers
40 views

Suppose $k$ is even and $4 \nmid k$, please explain why $k/2$ is odd

Assume integer $k$ is even and $k>2$. In order for $k/2$ to be odd, $k$ cannot be divisible by $4$. Can someone please explain why this is true, or point me in the right direction? I don't need to ...
0
votes
0answers
27 views

Find minimum number of uniformely colored rectangles in a colored grid

I have an MxN grid. In each square of the grid there is color taken from a set of color C. I can describe the whole grid with MxN statements that say something like: the square (Mi,Nj) has the color ...
6
votes
4answers
133 views

Inductive Proof that $k!<k^k$, for $k\geq 2$.

Call $P(k): k!<k^k$, for $k\geq 2$ Test it out with 2, and it's true ($2<4$). Assume that $P(k)$ is true for some $k\geq2$. Then show that $P(k+1)$ is true. $P(k+1): (k+1)!<(k+1)^{k+1}$ ...
3
votes
2answers
69 views

14 pencils handed out to 6 people. Each person has at least 1 pencil. Person 6 no more than 3 pencils.

We have 14 indistinguishable pencils and we want to hand out all of the pencils to 6 people and we want everyone to get at least one pencil. However, we do not want person 6 to get more than 3 ...
1
vote
2answers
70 views

How many different ways can 14 pencils be passed out to 6 different people? Some people are allowed no pencils.

There are 2 questions that are very similar and I have the same answer to both but I don't think that's correct. Can you help me see the difference between the 2 questions. We have 14 ...
3
votes
4answers
525 views

Four 6-sided dice are rolled. What is the probability that at least two dice show the same number?

Am I doing this right? I split the problem up into the cases of 2 same, 3 same, 4 same, but I feel like something special has to be done for 2 of the same, because what if there are 2 pairs (like two ...
2
votes
2answers
34 views

Equivalence Classes Output

I understand that an equivalence relation is a set that is reflexsive, symmetric, and transitive. I don't quite understand equivalence classes though. For example: What would the equivalence class be ...
-3
votes
1answer
79 views

Prove by induction $\frac{a_{1} + a_{2} + a_{3} +…+ a_{n}}{n} \geq \sqrt[n]{a_1 \cdot a_2 \cdot a_3 \cdot …a_n}$. [duplicate]

Let $a_1$ $a_2$,..., $a_n$ be positive numbers. Prove that $\frac{a_{1} + a_{2} + a_{3} +...+ a_{n}}{n} \geq \sqrt[n]{a_1 \cdot a_2 \cdot a_3 \cdot ....a_n}$. Mine is about trying to understand how ...
0
votes
0answers
37 views

Proof by induction [duplicate]

$\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} +\cdots+\frac{1}{n^2} < 2 - \frac{1}{n}$. Proof: Let $p(n)$ be a proposition. $$p(n):\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} ...
1
vote
2answers
28 views

Making sense of a combinatorial answer

$\frac {\sum^n_{k= 0}k\binom nk}{2^n}$ is the average size of a subset of $\{1, 2, \ldots, n\}$. We add up the sizes of all subsets and divide by the total number of subsets. Why is the $i$th term ...
3
votes
1answer
313 views

Euler's theorem: [3]^2014^2014 mod 98

Calculate without a calculator: $$\left [ 3 \right ]^{2014^{2014}}\mod 98$$ I know I have to use Euler's Theorem. As a hint it says I might need to use the Chinese Remainder theorem too. I know ...
0
votes
2answers
32 views

How to create a moment generating function for $Y$?

Consider a discrete random variable defined as follows: When $X=0$, $P(X=x) = .25$. When $X=1, P(X=x) =.4$. When $X=2, P(X=x) = .35$. The moment generating function for $X$ will be: $$Mx(t) = .25 + ...
0
votes
1answer
86 views

Permutation and combination.

I have started learning permutation and combination. I am looking at the question below. It has given the answers also but I didn't understand how? I have looked at many examples online it just made ...
3
votes
3answers
133 views

Proof verification for proving $\forall n \ge 2, 1 + \frac1{2^2} + \frac1{3^2} + \cdots + \frac1{n^2} < 2 − \frac1n$ by induction [duplicate]

Prove by mathematical induction: $\forall n \ge 2, 1 + \frac1{2^2} + \frac1{3^2} + \cdots + \frac1{n^2} < 2 − \frac1n$ Basis Step: (We want to show, $P(2)$, which is 1 + ...
0
votes
1answer
82 views

Computing the Value of a minimax tree

I am asked to compute the value of a minimax tree, which each node labeled with its initial value. I am just unsure how to do it. I know that it is a minimax tree if: the root is a min node, the ...