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

learn more… | top users | synonyms

2
votes
3answers
42 views

Why is the inverse of this function not a function?

Why does $F^{-1}$ need to be defined on all of $Y$? I can have this function: $g(x)=x,\quad x\ne 3$ and even though it is not defined for all $x$ in its domain, it is still a function, right?
1
vote
2answers
26 views

How do I calculate variance for sum of dice?

I'll post my work, but I'm not sure how to calculate variance. The question asks for the expected sum of 3 dice rolls and the variance. I think I got the expected sum. Any help would be awesome :) ...
0
votes
0answers
16 views

A question on linear programming

For each $Q \subset \Bbb R^n$, denote $Q^*:=\{z \in \Bbb R^n:zx \leq 1,\;\;\text{for all}\; x \in Q\}$. Let $P:=\{x \in \Bbb R^n: Ax \leq b\}$, for the matrix $A$ and the vector $b$. It is clear that ...
1
vote
1answer
51 views

Finding Truth Values Of Nested Quantifiers

I'm looking at for example, $∃x∀y,P(x≥y+1)$ I'm told in order to prove that this is true I can us the technique that follows: Find one value of $x∈X$(only needs to be one) that has the property that ...
0
votes
0answers
20 views

Proving Theorems - Discrete Math

so I'm just practicing for my test and I have absolutely no idea how to prove theorems. I've been given the following practice questions: (a) $¬(∀x∈SF)≡∃x∈S¬F$ and (b) $∀x∈SF ≡¬∃x∈S¬F$ Would ...
0
votes
3answers
56 views

Homework question. please give me hints or feedback

Prove or find a counterexample: For all real numbers x and y it holds that x + y is irrational if, and only if, both x and y are irrational
0
votes
1answer
48 views

Finding formula for a series and proving

Find a formula for $\displaystyle\sum_{i=1}^n \frac{i}{(i+1)!}$ and prove that it holds for all $n \ge 1$. How do you find an equation for this formula? Is it common sense or is there a way to find ...
1
vote
2answers
62 views

Get the Nth term of a sequence 1,2,4,7,13,24…

I have a sequence: 1,2,4,7,13,24,44,81, ... and I think it's like a Fibonacci sequence, however you add three number together and not two ("Tribonacci"?). So: $$ v_n = v_{n-1} + v_{n-2} + v_{n-3} $$ ...
0
votes
1answer
40 views

How can a function not be one to one and be a function?

My understanding of the definition of a function Given any x, there is only one y that can be paired with x My understanding of a 1 to 1 function Given any y, there is only one x that can be paired ...
0
votes
0answers
16 views

What is the general form of a finite sequence?

I originally used: $a_0,a_1,a_2,...,a_n$ where $n$ is an integer greater than or equal to 0 but I've realized that this is actually an infinite sequence because n can go to $\infty$. How can I bound ...
1
vote
1answer
38 views

Combinations and Probability Problems

I try this problem and I got $\binom{50}{20} * \binom{30}{20} * \binom{10}{10} = 1.416 * 10^{21}$ . I just want to make sure I have the right idea for this problem. In a medical experiment involving ...
1
vote
1answer
38 views

Probability and Combinations

In a family with 6 children, a. What is the probability of having three children of each sex? b. What is the probability of having four of one sex and two of the other sex? I know in this problem ...
1
vote
1answer
19 views

How to find a pattern in this recursive sequence algorithmically?

I'm trying to find the closed-form of a sequence algorithmically. Here is the recursive sequence: $$w_k=w_{k-2}+k, \forall k \in \Bbb{Z} | k \geq 3, w_1=1, w_2=2$$ which produces this sequence: ...
1
vote
3answers
55 views

Finding the limit of a sequence by diagonalising a matrix

Consider the sequence described by: $\frac11 , \frac32 , \frac75 , ... ,\frac {a_{n}}{b_{n}}$ where $ a_{n+1} = a_n +2b_n $ and $b_{n+1} = a_n+b_n$ Find a matrix $A$ such that ...
0
votes
1answer
23 views

three things question Discrete math on multipartite graph

I am wonder about these problem 1.Degree sequence of the complete Multi-partite graph $$K_{n_{1}, n_{2}, n_{3}, n_{4}, ..., n_{m}}$$ and 2.My class professor said one proposition that If graph is ...
0
votes
1answer
13 views

Discrete math on multipartite graph

I am wonder about these problem 1.The complete Multi-partite graph $$K_{n_{1}, n_{2}, n_{3}, n_{4}, ..., n_{m}}$$ 2.the number of edge of $$K_{n_{1}, n_{2}, n_{3}, n_{4}, ..., n_{m}}$$
-1
votes
1answer
28 views

How many different binary search trees can be made with three pieces of data? [closed]

This is for a discrete math course, not computer science.
0
votes
2answers
22 views

Number of lines/triangles determined by n points

Can someone please illustrate how this plane works by drawing. I just want to get an idea of how this plane works. There are n points in the plane, such that no three points are on the same line. a) ...
0
votes
1answer
44 views

Induction proof that $4^n > 3^n+2^n$ for $n\ge2$

This is a problem with induction and proofs but I'm not sure how to start with proving this one. $$\text{Show that for any $n \geq 2$, $4^n > 3^n+2^n$}$$
0
votes
4answers
84 views

Proof that $(1 + x)^n > 1 + nx$ for $x>-1$, $n$ a positive integer [duplicate]

For any positive integer $n$ and real number $x > -1$, show that $(1 + x)^n > 1 + nx$. This is Bernoulli’s inequality but I can't figure out how to start with this. Can someone help? Thanks
3
votes
1answer
36 views

Where did this “+1” term come from for this inductive proof?

Where did this "+1" term come from for this inductive proof? It is in boxed in black. For context, We are trying to prove this sequence: has the following solution: $$x_{ n }=\frac { 3^{ n+1 ...
0
votes
1answer
49 views

A formula for $\sum^n_{i=1}(1+1/n)$?

Find a formula for $$\sum^n_{i=1}\left(1 + \dfrac{1}{n}\right)$$ Prove that it holds for all $n \geq 1$. It kind of looks like is a series but I didn't succeed in this problem. Can someone help me ...
2
votes
1answer
138 views

Spelling has deteriorated by the year of 2075, how many spellings are possible?

By the year 2075, spelling has deteriorated such that the dictionary now defines the spelling of the word “RELIEF” to be any combination (with repetition allowed) of the letters F, L, R, I and E ...
0
votes
0answers
10 views

Discrete Math Trace recursive function

Does anybody know how to trace this function by specifying the recursive calls to the function? The inputs are: A = {24, 15, 7, 10, 8, 30}, i = 2, n = 6 RandomElement(A) returns an element of A ...
3
votes
0answers
19 views

(Counting problem) more challenging Modular N algebraic eqs - for combinatorics-permutation experts

Experts in algebra please help - Part II after Part I: we would like to know the number of solutions for this set of six of modular N algebraic equations: $$ x_1 y_2 = x_2 y_1 \pmod N \qquad (1) \\ ...
2
votes
2answers
60 views

(Counting problem) very interesting Modular N algebraic eqs - for combinatorics-permutation experts

Experts in algebra please help: we would like to know the number of solutions for this set of six of modular N algebraic equations: $$ (1) \quad x_1 y_2 \equiv x_2 y_1 \pmod{N}\\ (2) \quad x_1 y_3 ...
2
votes
2answers
25 views

Recurrence relation practice problem that I can't figure out

Thanks for taking the time to look at this problem. I'm trying to prepare for a test on Monday by doing some extra odd numbered problems from my textbook. I'm having a lot of trouble trying to solve ...
1
vote
1answer
63 views

Finding the radius of a sphere touching other spheres inscribed in n-dimensional spaces

I know for certain that the radius of the first one is $r=(\sqrt2-1)/2$. I assume the radius of the other dimensions are the same but I don't know how I would create an equation to prove that. Lastly ...
1
vote
2answers
46 views

Draw a finite state machine which will accept the regular expression $(a^2)^* + (b^3)^*$

Draw a finite state machine which will accept the regular expression: $(a^2)^* + (b^3)^*$ In particular, I am confused by the $+$ sign, what does it exactly mean? Most literature I could find about ...
1
vote
2answers
47 views

Induction And Proofs

Find a formula for $\sum_{i=1}^{n} \frac{1}{(2i-1)(2i+1)}$ and prove that it holds for all $n \geq 1$ I don't know how to solve this particular problem, can someone help me please. Thanks
-1
votes
2answers
32 views

Discrete Math: Inductions

Find a formula for $\sum_{i=1}^n \frac{i}{(i+1)!}$ and prove that it holds for all $n\geq 1$. I'm not sure how to go with this problem can someone help please. Thanks
3
votes
4answers
40 views

Is this a correct recursive sequence definition?

Take this definition: Is this definition of $s_k$ for $k\ge2$ correct? $s_k=6a_{k-1}-5a_{k-2}$ but where does the $a$ term come from? The book swaps $a$ and $s$ interchangeably.
1
vote
4answers
44 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
69 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
46 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
28 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
19 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} ...
2
votes
1answer
31 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
39 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
17 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
58 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
96 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
26 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
56 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
0answers
40 views

Number theory, proving or finding counterexample

Prove or find a counterexample: The product of any three consecutive natural numbers is divisible by 9. Answer False,since 1 x 2 x 3 = 6 which is not divisible by 9. Thus, 9∤6 .
1
vote
2answers
35 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 ...
0
votes
0answers
12 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
42 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 ...
1
vote
2answers
69 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
8 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 ...