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

How to prove the divisors of 15 form a Boolean algebra

This from Exercise 3.1 in "A Beginner's Guide to Discrete Mathematics" Let B be the set of all positive integer divisors of 15, that is B = {1, 3, 5, 15}. Prove that B forms a Boolean algebra with ...
1
vote
0answers
38 views

Transitive relations.

"A relation R on a set A is transitive if whenever aRb and bRc then aRc, that is, if whenever (a,b), (b,c) is an element of R then (a,c) is an element of R. Thus R is not transitive if there exist ...
0
votes
2answers
52 views

Recurrence Relationship Questions

Consider the recurrence defined by: $$G_0 = 0\\ G_n = G_{n-1} + 2n - 1$$ Determine what Gn is for several values of n to determine a formula for Gn. $2n$ $n$ $2n-1$ $n^2$ *I believe this one is ...
0
votes
2answers
85 views

Proof that 2 and 3 are the only siamese twins that exist!

Let us say that two prime number p and q are siamese twins if |p-q|=1. List all the siamese twins that exist, and prove your list is complete. Proof: 2 and 3 are prime numbers and 3-2=1. Therefore 2 ...
0
votes
1answer
10 views

Does each element in domain need result for onto functions?

For onto functions, do all the elements in the domain have to give a result from the range? I know that for one-to-one, every single $x$ must give a result, and one that is a unique $y$. For onto ...
1
vote
1answer
48 views

Simple Recurrence Questions [closed]

$r$ is a real number, define a recurrence relationship for $A_n$ $$A_0 = 1\\ A_n = r\cdot A_{n-1}$$ Question: What is the value of $A_4$ $4(A{n-1})$ $r^4$ $1$ $4r$ I've pretty much eliminated ...
0
votes
1answer
45 views

Compute the following sum

I am to compute the following sum and my professor wrote this on the board. Although I can see what he is doing here and how to use the S and 2S I can't figure out the steps that are highlighted in ...
3
votes
1answer
357 views

The product of any three consecutive natural numbers is divisible by 9.prove or find a counterexample

can anyone give me feedback on my solution false counterexample: n(n+1)(n+2) let n= 1 1(2)(3) =6 is not divisible by 9 is this correct?
1
vote
1answer
49 views

How to prove a set must have a specific number of elements?

Trying to understand sets but having a hard time. Could someone help me through this one? Let A be a set of six positive integers each of which is less than 13. Show that there must be two distinct ...
1
vote
1answer
91 views

Help with identity functions in discrete mathematics

I have trouble with trying to solve the following problem: For nonempty sets $A$ and $B$ and functions $f:A\rightarrow B$ and $g:B\rightarrow A$ suppose that $g\circ f=i_A$, the identity function on ...
0
votes
3answers
239 views

Proving functions are injective and surjective

I am having trouble with the following problem: For nonempty sets $A$ and $B$ and functions $f:A \rightarrow B$ and $g:B \rightarrow A$ suppose that $g\circ f=i_A$, the identity function of $A$. ...
0
votes
2answers
39 views

I'm not quite sure I understand my book's reasoning for the answer

I have the following homework problem: Does there exist a graph, $G$, with 28 edges and 12 vertices, each of degree 3 or 4? First, my solution. $$ \sum deg(v_i) = 2 \cdot |E| \\ |E| = 28 ...
0
votes
3answers
84 views

Injective and Surjective Function Examples

I am having trouble with this problem: Give an example of a function $f:Z \rightarrow N$ that is a. surjective but not injective b. injective but not surjective Work: I came up with examples such ...
0
votes
1answer
19 views

Solve for all posible triangles that satisfy the conditions

Solve for all possible triangles that satisfy the conditions How do I know if there is 2 or more triangles/ $a=30,$ $c =40,$ $m\angle A=37$ so angle $C$ I believe is $53.36$, so then angle $b ...
0
votes
1answer
34 views

Proving Integer Modulo is Well-Defined

I have trouble figuring out this problem: $h: Z_4 \rightarrow Z_6$ by $h([a])=[3a]$ for each $a\in Z$. Prove that h is well-defined thus it is a function and that h is neither injective nor ...
3
votes
2answers
112 views

$K$ events that are $(K-1)$-wise Independent but not Mutually/Fully Independent

I had the following question: Construct a probability space $(\Omega,P)$ and $k$ events, each with probability $\frac12$, that are $(k-1)$-wise, but not fully independent. Make the sample space as ...
1
vote
1answer
53 views

Proving the harmonic number

For $n \in \mathbb N^{+}, H_n = \sum_{i=1}^n \frac{1}{i}$ is called the $n$-th harmonic number. (a) Prove: $$\forall{n \in \mathbb N}: 1+ \frac n2 \le H_{2^n} $$ This is one of my homework questions ...
0
votes
1answer
36 views

How's my proof?

Prove that not every boolean function is equal to a boolean function constructed by only using $∧$ and $∨$. If p,q = (0,1) (p$∧$q)$∨$q = (0$∧$1)$∨$1 = 1 (p$∧$q)$∨$~q = (0$∧$1)$∨$~1 = 0 Therefore ...
1
vote
1answer
35 views

Solving a poset for less than equal?

I don't completely understand posets yet, so I'm confused on how to do this particular problem. Here is the question: Let S be the set of all real numbers. Prove that the less than or equal to ...
1
vote
1answer
67 views

Boolean function proving contradiction ,tautology or neither

Determine whether $((p \Rightarrow q) \Rightarrow r)\Leftrightarrow (p \Rightarrow(q \Rightarrow r))$ is a tautology, a contradiction, or neither. $$\begin{array}{cccc} ...
0
votes
1answer
24 views

Find a sequence $a$ so that $a_n = s \Delta a_n $.

Let $s$ be a real number $ s \ne 0 $. Find a sequence $a$ so that $a_n = s \Delta a_n $ and $a_0 = 1$. Any help with this question will be great. This is my first time doing recurrence relations ...
0
votes
2answers
48 views

Two sequences $a$ and $b$ for which $\Delta a_n = \Delta b _n$

Find two different sequences $a$ and $b$ for which $\Delta a_n = \Delta b_n$ for all of $n$. This is my first time doing recurrence relations, so if anyone could provide some thorough and clear ...
1
vote
3answers
76 views

P white balls, Q black balls, N boxes

First of all sorry if this has been asked before, I could find "similiar" questions which seem to be harder but not quite this specific question. You are given P white balls and Q black balls, how ...
0
votes
1answer
103 views

Roll 2 dice adding and rolling one die, probability of being equal

Roll two dice, add the results, call the number x. Roll one die call that number y. What is the probability that x and y are equal? Help please.
1
vote
1answer
19 views

Prove the claim

Prove the following Claim: "Claim: Suppose sets $A$ and $B$ are finite subsets of a finite set $U$ Then $|A| \cap |B| \ge |A| + |B| - |U|$" By subtracting $|A| \cap |B|$ from both sides and adding ...
0
votes
2answers
50 views

Induction and proof , proofing a sequence

How do you prove this by induction? I'm used to proofing simple geometric series by induction but this one is very complicated. How can I approach this, or maybe give me an answer and show me how you ...
1
vote
0answers
88 views

Proof of the Catalan number formula using Dyck walks

In our notes we were given the formula $$C(n)=\frac{1}{n+1}\binom{2n}{n}$$ It was proved by counting the number of paths above the line $y=0$ from $(0,0)$ to $(2n,0)$ using $n(1,1)$ up arrows and ...
0
votes
1answer
53 views

How many surjective functions? [duplicate]

Let $A$ and $B$ be sets with cardinalities m and n respectively where $m \ge n$ how many surjective functions are there from $A$ to $B$? Support your answer I have no idea how to go about this one. ...
0
votes
1answer
27 views

Finding a formula for a series INDUCTION

How does this relate from proofing this by induction and making a formula. Confused how you would find the formula. How can I approach this, or maybe give me an answer and show me how you did this ...
-1
votes
1answer
43 views

Proof in induction geometric series [duplicate]

I would like to prove this by induction. How can I approach this, or maybe give me an answer and show me how you did this in detail? I'm struggling with using induction and would like to expand my ...
0
votes
2answers
53 views

Induction proof of $\sum_{i=1}^n i^3 = \frac{n^2(n+1)^2}{4}$

$$\sum_{i=1}^n i^3 = \frac{n^2(n+1)^2}{4}$$ How do you prove this by induction? How can I approach this, or maybe give me an answer and show me how you did this in detail? Would really appreciate ...
1
vote
2answers
62 views

Coefficients of this generating function

For the first part of a problem, I solved the generating function to be $F(x) = \frac{x^3}{(1-x)^2}$ Now it's the easy part that has me a little confused. What would the coefficients be in this case? ...
0
votes
1answer
34 views

Find the number of the quadruplets

Let $X$ a set with $n \in \mathbb{N}$ elements.Find the number of the quadruplets $(A,B,C,D)$,where $A,B,C,D$ are subsets of $X$,that satisfy the conditions: $A \subseteq B, C \subseteq D, B \cap D= ...
3
votes
1answer
304 views

Generators of Special Linear Groups

Linear algebra and special-linear group experts please help: I learn that in principle one can generate this $M$ matrix form the $B_1$ and $B_2$ matrix below. Here $$ M=\begin{pmatrix} 0& 1& ...
1
vote
2answers
45 views

Cardinality proof

Suppose sets $A$ and $B$ are finite subsets of a finite set $U$. Prove that $$|A \cap B | \ge | A | + | B | - | U |$$ Any advice as to how I should approach this problem? Thanks in advance!
0
votes
0answers
86 views

Alternating permutation exponential generating function

A permutation pi is alternating if pi_1 > pi_2 < pi_3 > pi_4 <….Let a(n) be the number of alternating permutations of size n. (a) Find a recurrence relation for a(n). (b) Evaluate the ...
5
votes
0answers
79 views

Maximal hamming distance

Here is a combinatorial problem : let $\Sigma=\{\alpha_1,\ldots,\alpha_n\}$ be an alphabet and we consider any words over $\Sigma$ of length $n$. We also define over the set of such words the Hamming ...
0
votes
1answer
59 views

How do I construct a minimum spanning forest?

I realize that a minimum spanning forest in a weighted graph is a spanning forest with minimal weight. Does this mean that I construct it by turning all of the trees into spanning trees?
0
votes
2answers
38 views

Prove $\displaystyle\sum_{i=1}^{n}i(i!)=(n+1)!-1$ by induction

Consider the equality $$ \sum_{i=1}^{n}i(i!)=(n+1)!-1. $$ How do you prove this by induction? I have no idea how to start this. How can I approach this, or maybe give me an answer and show me how you ...
0
votes
2answers
46 views

Inductions and proofs

Let $(h_n)$ be a sequence defined by $h_0 =1 , h_1 = 2, h_2 =3$ and $h_n = h_{n-1} + h_{n-2} + h_{n-3}$, for all $n\ge 3$. Prove that $h_n\le 2^n$ , for all $n\ge 0$ Not sure how to go with this ...
0
votes
1answer
27 views

Countability of all finite strings over an alphabet

Is the set of all finite strings over the alphabet $\{01,2,3,4,5,6,7,8,9,/\}$ countable? If it is, wouldn't the set of positive rationals also be countable? Why is the above set countable?
1
vote
1answer
125 views

What is the difference between a forest and a spanning forest?

If a graph is labelled as a forest it does not contain any cycles, meaning it consists of all trees, which I realize can even be a single node (since that is technically a tree). If a graph is ...
0
votes
1answer
97 views

Round table exponential generating function

Let $r(n)$ be the number of different ways to seat $n$ people around a round table. Find the exponential generating function for $r$. I believe $r(n)$ is just equal to $n!/n = (n-1)!$. So then I ...
1
vote
1answer
76 views

How do you know how many coins to start off with on each side of a “find the counterfeit coin using a 2-pan weigh scale” problem?

The fake coin is defined by either having a lesser or greater weight than all of the other coins in the problem. Say there are 12 coins, 1 out of the 11 which is the fake coin. How does everyone know ...
1
vote
2answers
142 views

How should i prove every finite lattice is bounded?

I want to know the outline to how to prove every finite lattice is bounded?
0
votes
1answer
28 views

(L1* ∩ L2*) = (L1 ∩ L2)* for all languages L1 and L2 over the alpabet Σ={A,B} Is it true or false and why?

plz answer me Determine whether each of the following statements is true or false. If a statement is false, give a counterexample..... 1- $(L_{1}^{*} \cap L_{2}^{*}) = (L_{1} \cap L_{2})^{*}$ for ...
1
vote
1answer
31 views

Discrete Math Induction: $\sum^n_{i=1} \frac1{i(i+1)}$ [duplicate]

For $\sum^n_{i=1} \frac1{i(i+1)}$ Find a formula and proofs that it holds for all n ≥ 1. How would I find the formula for this one that can hold for all n ≥ 1?
-1
votes
2answers
73 views

Discrete Math On Induction proof: $\sum_{i=1}^n n2^n = (n-1)2^{n+1} + 2$ [duplicate]

Show by induction that the following formulas hold. $\sum_{i=1}^n n2ⁿ = (n-1)2^{n+1} + 2$ What did a similar problem to this but this one is a little different. I think is because this one has a ...
-1
votes
1answer
177 views

Prove Matrix Power for 2x2 matrix using mathematical induction

Using mathematical induction, prove that for any diagonal $2\times 2$ matrix $A$, that $$A^n = \begin{bmatrix} a^n & 0 \\ 0 & b^n \end{bmatrix}$$
-1
votes
1answer
48 views

Discrete Math on Induction proofs

Show by induction that the following formulas hold for $$ \sum_{i=1}^n i^3 = \frac{n^2(n+1)^2}{4} $$ Not sure how to go about this problem. Can someone help please? Thanks