Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

0
votes
2answers
31 views

Finding paths in a graph with n vertices

Let n ≥ 2 be a natural number. Consider the graph G = (V, E) where V ={0,1,2,...,n} and E=({0,1},{0,2},...,{0,n}) ∪ ({1,2},...,{n−1,n}) ∪ ({n,1}) For paths, it's a sequence of (non-repeating) ...
0
votes
0answers
19 views

Bijective functions

Find a pair (I,J) such that f (I,J) is bijective and its range is the range of f. What is then the inverse of f (I,J) ? If my function is F(x) = 1/x, how am I supposed to plug two values into the ...
1
vote
2answers
22 views

Help with Discrete Math Functions and Bijections

I have trouble with the following problem: Prove that the function $f(x)=x^2-2x+3$, with domain $x\in (-\infty, 0)$, is a bijection from $(-\infty, 0)$ to its range. Work: I tried to first prove ...
1
vote
1answer
11 views

Determine the set $A$ = {$m\in Z|mR52$} and give its cardinality $|A|$.

Given a relation R on $Z^+$ defined as: $mRn$ if and only if $m|n$, I need to determine the set $A$ = {$m\in Z|mR52$} and give its cardinality $|A|$. I know that $mR52$ = $m|52$ and that $52 = mk$ ...
0
votes
1answer
27 views

Help with Functions in Discrete Mathematics

I am having trouble solving this problem: let $p$ be a positive prime number and let $f:Z_p -> Z_p$ be defined as $f([x])=[x^2]$. Show that $f$ is a function. Give examples of how it is not ...
1
vote
2answers
51 views

Algebraic proof for the following identity

Give an algebraic proof that $\binom{n+1}{m+1} = \sum_{k=m}^{n} \binom{k}{m}$. I've tried using Pascal's rule and looking for a telescopic sum, but I can't find one. Any help is appreciated.
0
votes
2answers
22 views

Misere NIM game

I am having difficulty trying to attempt this question. Any help would much be appreciated. Thank you. In (9,2,31)−Misère NIM, the game begins with a pile of N stones. On their turn, a player can ...
0
votes
0answers
11 views

Help with Integer Modulo Proof

I am stuck on this problem for a while and need some help: Prove that for any prime $p$, if $[a]*[b]=[0]$, does it follow that $[a]=[0]$ or $[b]=[0]$? Work: I do not know where to start. I was ...
0
votes
0answers
17 views

probability of linear expectation with random variables. [duplicate]

I really I have no idea where to start with this question. If anyone could help me out that would be awesome. Let X1,X2,...,Xn be a sequence of mutually independent random variables. For each i with ...
0
votes
0answers
23 views

Miller-Rabin primality test and testing one

I'm learning about Miller-Rabin primality test but in all the problems I see in the notes of a person I got them from, I see that even if he expressed the number as $2^1 \cdot something$, he still ...
1
vote
3answers
46 views

Understanding Set Theory and Proving $A \cap(B\cup A) = A$

I am trying to wrap my head around discrete mathematics in order to help my understanding of self taught programming. I am now trying to understand Set Theory, more specifically proving certain ...
0
votes
0answers
23 views

Taking the modulus of the power?

So I'm learning about Euler's theorem for reducing large powers modulo $n$ and what I'm wondering about is: can we simply take the modulus of a power of a number the same way we take it of the number ...
-6
votes
1answer
45 views

Discrete Math on Graphs [closed]

Can someone explain to me that how would I show that Is it possible for a simple graph with 6 vertices to have 42 edges?
-3
votes
1answer
38 views

Discrete Math On proving Graph Degree Sequence

Can someone please explain that how would I show or Prove that there is no graph with degree sequence (1, 1, 2, 3, 4, 4, 5, 7). Thanks
0
votes
1answer
27 views

Discrete Math on Functions as bijection

Can Someone help me on how to Prove that $f: \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z} \times \mathbb{Z}$ defined by $f(a, b) = (−b, a)$ is a well-defined bijection.
0
votes
1answer
31 views

Equivalence Relation on R (real numbers)

Let R be the relation on R(real numbers) defined by: For all x, y (that belong) to R(real numbers), x relates y <=> x-y (that belongs) to Z. (a) Is R an equivalence relation? Prove your answer. ...
0
votes
2answers
19 views

Let $A_1, A_2, \ldots, A_n$ be sets (where $n \ge 2$). Suppose for any two sets $A_i$ and $A_j$ either $A_i \subseteq A_j$ or $A_j \subseteq A_i$

Let $A_1, A_2, \ldots, A_n$ be sets (where $n \ge 2$). Suppose for any two sets $A_i$ and $A_j$ either $A_i \subseteq A_j$ or $A_j \subseteq A_i$. Prove by induction that one of these $n$sets is a ...
1
vote
1answer
38 views

How do I find the probability of specified events from a permutation of the 26 english letters?

I found a similar problem here, but I don't really understand the explanation to their solution and can't apply it. Question: What is the probability of the following even when we randomly select a ...
0
votes
0answers
16 views

Am I calculating probability correctly?

I am working on some discrete math problems and would like to make sure I'm doing them correctly and what not. Instead of typing it all out in latex, I took a picture of the questions/my work. I hope ...
1
vote
2answers
61 views

Prove by induction $1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{2^n} \ge 1 + \frac {n}{2}$

Prove by induction $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots + \frac{1}{2^n} \ge 1 + \frac {n}{2}$ I can't explain in words how the left hand side of the equation is achieved soI shall ...
0
votes
2answers
37 views

Discrete Math question - cookies

Simple math question: How many ways are there to choose $12$ cookies if there are $5$ varieties? It was wrong in my homework after I tried $5^{12}$.
1
vote
0answers
51 views

Pancake and increasing order

Determine the number of 5 pancake stacks that requires exactly 2 flips to put into the increasing order, i.e., 1,2,3,4,5. (Example: 3,4,2,1,5 is one of them.)
0
votes
0answers
28 views

Proving a set is equal to another set

For all sets $A$ and $B,(B-A)=B\cap A^C$. I would like to know if this proof is correct or if I am on the right track. Here it is: Let $b \in B$ such that $b \notin A$ than $b \in B$ and $b \in ...
0
votes
1answer
16 views

Everywhere defined functions

Suppose A has 4 elements and B has 3 elements. (a) How many everywhere defined functions are there from A to B? I tried the Pigeonhole principle but I got fraction. Please assist.
1
vote
2answers
33 views

How to Prove this Set Question? [closed]

For both sets C and D, provide a proof that C ∪ (D − /C) = C "/C" is a set's complement of C
0
votes
2answers
30 views

Help with proof by induction?

Prove $\frac{2(n-c)}{n+1} < 2$ where c is any natural So we assume $\frac{2(n-c)}{n+1} < 2$ is true, and so far I have $\frac{2(n+1-c)}{n+2} = \frac{2n-2c+2}{n+2} = \frac{2(n-c)}{n+2} + ...
2
votes
2answers
56 views

Learning Mathematics through Programming.

I am about to embark on a 'comprehensive' and thorough study of undergraduate mathematics. In the interests of efficiency and a desire to improve my programming skills, I ask: In oppose to the pen ...
-1
votes
2answers
107 views

Give a Bijection that is in-between 2 intervals and use a formal proof to show that it is a bijection. [duplicate]

∀w,x,y,z ∈ R, w < x and y < z. Given that information, supply a bijection between the two intervals. (w,x) and (y,z) Then after you find the bijection, provide a formal proof that what you found ...
-3
votes
1answer
53 views

Number of ways of choosing three fruits [closed]

You are allowed to choose three fruits from a tray containing two identical apples, two identical oranges, a pear, a banana, and a plum. In how many ways can you choose?
0
votes
2answers
46 views

how many integers are there between 10 000 and 99 999…

how many integers are there between 10 000 and 99 999 a) whose digits are are each odd? b) with no repeated digits? c) with no repeated digits and whose digits are each odd? I know there are 90 ...
0
votes
2answers
59 views

Interesting a Fibonacci quesiton. Need help.

Alice claims that she knows another formula for the Fibonacci numbers: Fn = $e^{n/2−1}$ for $n = 1,2,\cdots$ (where $e = 2.718281828$... is, naturally, the base of the natural logarithm). Is she ...
0
votes
2answers
49 views

Recurrency is ok but if part is complicated

How many subsets does the set {1,2,...,n} have that contain no two consecutive integers if 1 and n also count as consecutive?
0
votes
1answer
26 views

Probability of resulting in odd numbered die roll and red suited card?

Roll a die and pick one card from a standard deck. What is the probability that this procedure will result in an odd numbered die roll and a red-suited card? I am guessing 1/4? because odd + black, ...
0
votes
1answer
40 views

Chessboard by dominoes in Discrete Math [duplicate]

The question looks like obvious but I could not find the answer. In how many ways can you cover a 2×n chessboard by dominoes?
0
votes
5answers
39 views

Recurrence problem for $a_5$

Assume that the sequence $\{a_0,a_1,a_2,\ldots\}$ satisfies the recurrence $a_{n+1} = a_n + 2a_{n−1}$. We know that $a_0 = 4$ and $a_2 = 13$. What is $a_5$?
0
votes
2answers
20 views

proof multiplying combinations - algebra struggles

I don't have to write a proof I just have to show that $(^{n}_{k})(^k_m)=(^n_m)(^{n-m}_{k-m})$ But I am struggling to expand this. $$\frac{n!}{k!(n-k)!}*\frac{k!}{m!(k-m)!}$$ Once I get it to this ...
0
votes
2answers
19 views

combinations proof - stuck on the algebra

prove that $k(^{n}_{k})= n(^{n-1}_{k-1})$ What I have so far: I'm trying to use pascals rule and the definition of combinations to expand this algebraically but I keep getting tied up in the algebra. ...
0
votes
4answers
45 views

direct proof of combination

Prove that $(^{n}_{2}) = 1+2+3+...+(n-1)=\sum^{n-1}_{k=1}k$ for $n \ge 2$ After some time flipping through notes I think I should use the sum of the 1st n natural is ...
1
vote
4answers
44 views

proof by induction: sum of binomial coefficients

Question: Prove that the sum of the binomial coefficients for the nth power of $(x + y)$ is $2^n$. i.e. the sum of the numbers in the $(n + 1)^{st}$ row of Pascal’s Triangle is $2^n$ i.e. prove ...
0
votes
1answer
32 views

How many integers in between 1 and $10^7$ are divisible by 3, 5 or 7?

How many integers in between 1 and $10^7$ are divisible by 3, 5 or 7? I try with that the number of integers between 1 and $10^7$, inclusive, which are relatively prime to 63: $$(10^7)/3=3333333$$ ...
0
votes
2answers
30 views

inductive proof

How would you proof this inductively? I know this logically makes sense and I have different ways of doing. Would you be able to tell me how and explain the reasoning behind it? Its just a simple ...
1
vote
3answers
41 views

the binomial theorem

the Question: Prove the critical Lemma we need to complete the proof of the Binomial Theorem: i.e. prove $(^{n}_{k})=(^{n-1}_{k-1})+(^{n-1}_{k})$ for $0\lt k\lt n$ (this formula is known as Pascal’s ...
2
votes
0answers
24 views

Is there a cipher that yields two separate but valid results depending on the key?

Suppose the following. Someone wishes to encrypt a message so it is not intercepted. With traditional ciphers, if the key is guessed correctly, the message is revealed. This cipher is similar– ...
2
votes
1answer
38 views

How many ways can six of the letters of the word ALGORITHM be selected and written in a row if the first letter must be A?

As the title states, the question is: "How many ways can six of the letters of the word ALGORITHM be selected and written in a row if the first letter must be A?" I don't really get what the problem ...
0
votes
3answers
26 views

Describing Equivalence Classes using set builder notation

How would you describe all the equivalence classes for the relation: $congruence$ $modulo$ $5$ over $Z$, using set builder notation?
0
votes
1answer
16 views

Wording a proof for proving sets

How do you prove this? Isn't that A U B will equal to B regardless because by definition, union of set A and B can either elements of A or B? And B will equal to the union of A or B because B is B ...
0
votes
2answers
45 views

Obtaining a linear recurrence from differential equation

I need some guidance with the following problem. I have a sequence $L_0,L_1,\ldots$ whose ordinary generating series satisfies $$L(x) = \sum_{n=0}^{\infty} L_n \frac{x^n}{n!} = \frac{1}{2-e^x}.$$ ...
1
vote
1answer
51 views

Let A = {1,2,3,4} Let F be the set of all functions from A to A. (check the parts)

Let $\operatorname{S}$ be a relation on $F$ defined by: $\forall f, g \in F, f\,\operatorname{S}\,g \iff f(i) = g(i), \exists i \in A$. (a) Recall that the identity function $I_A : A \mapsto A$ is ...
0
votes
1answer
62 views

how to show all the siamese twins with diference 1 in discrete mathematics

two prime numbers p and q are siamese twins if |p-q|= 1. List all the siamese twins that exist, and prove your list is complete. i have found a siamese twin, 2 and 3 but how do i prove it is the ...
1
vote
1answer
29 views

Proving modulo equation with x-power

I'm trying to prove following equation: $$ (g^{y} \mod n)^x \mod = g^{xy} \mod n $$ I tried many multiple approaches, all of them failed, and there is waaay too much of them to write them here, so I ...