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
4answers
104 views

Show that if $p$ is a prime number $> 3$ then $24 \mid p^2-1$ [duplicate]

Hi guys can someone help me with this ?(Without using Modular arithmetic) Show that if $p$ is a prime number $>3$ then $24$ $\mid$ $p^2-1$
6
votes
3answers
86 views

Show that $9\mid a^2$ if given that $6\mid a$

Does this prove I made seem correct to show that if $6$ divides $a$ then $9$ divides $a^2$ If $6\mid a$, then $a = 6k$ (k is some integer). Then $a^2 = 36k^2 = 9(4k^2)$. Which means that $9\mid ...
0
votes
2answers
130 views

What subject in mathematics investigates the type of problems that constitute the LSAT “logic games” (example given)?

For my own curiosity, I read part of an LSAT study guide yesterday. The "logic games" section comprised questions like, An advertising executive must schedule the advertising during a particular ...
0
votes
1answer
36 views

Number of configurations in a constrained nested loops and configuration back from serial

Consider 4 counters looping the digits 0, 1, 2 to form the various "configurations", like in : ...
0
votes
0answers
24 views

closed form of a specific crazy summation?

How can I find the closed form of $f_2 + f_4 + ...+ f_{2m}$ where $\sum\limits_{m=1}^\infty f_{2m} = u_{2m-2}- u_{2m} $ where $u_{2m} = \binom{2m}{m} 2^{-(2m)}$ and $u_{2m-2} = \binom{2m-2}{m-1} ...
1
vote
1answer
56 views

Find all solutions to the Diophantine equation $2x+3y =1$.

How to find all the solutions to the Diophantine equation $2x+3y =1$. My professor didn't explain to us how to do this.
2
votes
1answer
49 views

Matrix linear algebra generators

Linear algebra and special-linear group experts please help: It is known that in principle one can generate this $C$ matrix form the $A$ and $B$ matrix below. Here $$ C=\begin{pmatrix} 0& -1& ...
1
vote
1answer
59 views

Help with composite identity functions in discrete mathematics

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 on ...
0
votes
4answers
74 views

How to reduce this series to a single equation?

Somehow, my textbook was about to reduce this series to a single equation: I know that you can use the equation $$S=\frac{n(n+1)}{2}$$ for the sum of the first n integers but I don't think this ...
2
votes
2answers
142 views

Finding $n$ such that $\phi(n)=34$ (where $\phi$ is Euler's totient)

How can I find $n$ such that $\phi(n)=34$ (where $\phi$ is Euler's totient) or prove that it does not exist? And how can I find $c$ for which $\phi(n)=c$ if $n$ does exists for $c$?
1
vote
0answers
110 views

How's the damping factor in Google PageRank algorithm calculated

I'm doing some researches about Google's PageRank algorithm for my thesis, I've found that the damping factor x (for example), where x is in : P` = x.P + (1-x)Q where P is the original ...
1
vote
1answer
79 views

Number theory, proving or finding counterexample.

Prove or find a counterexample: The product of any three consecutive natural numbers is divisible by 6. Answer True, because product of three consecutive natural numbers can be divisible by 6. Thus, ...
1
vote
2answers
101 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
39 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
246 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
114 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
89 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
314 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
87 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?