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

learn more… | top users | synonyms

0
votes
1answer
20 views

Find base of numbers in a sum?

is there an easier way to find the base A in the following without essentially brute-forcing it with different conversions until I get the result? Again, trying to find base A such that the following ...
0
votes
0answers
9 views

Is it possible for a graph to be both null and complete

Is it possible for a graph to be both null and complete?If so,how?If not,why not?
4
votes
0answers
32 views

Limit of a Discrete Dynamical System, Part 2

In my previous post (i.e., Limit of a Discrete Dynamical System) the following system was considered: ...
0
votes
3answers
35 views

Prove that the sum to n terms of the sequence Question

I'm not quite sure what this question is asking and I don't know how to start the proof for it. Do I need to make my own summation? not really sure. Prove that the sum to n terms of the Sequence: ...
1
vote
3answers
68 views

Proving that something is irrational

I'm trying to evaluate the following claim: $$ \sqrt{2} + \sqrt{n} $$ is irrational. This is what I tried: Proof by contrapositive: Suppose $$ r = \sqrt{2} + \sqrt{n} $$ and r is rational. Then $$ ...
1
vote
1answer
22 views

Need help with proving conditionals

Suppose P(x) is the assertion that "x is odd" and Q(x) is the assertion that "x^2 - 1 is divisible by 8" For part A it wanted us to prove P(x) -> Q(x). I solved that one but I'm having trouble ...
0
votes
0answers
27 views

Length of longest path of optimal graph with maximum degree n, number of edges k, on m vertices

I think this a well studied problem, giving the length of the optimal graph's (ie: graph with shortest longest path of graphs with max degree n, number of edges k, vertices m) longest path. For ...
0
votes
1answer
42 views

Discrete mathematics - Set Theory

Let d ∈ N be a given natural number. Let E ⊆ N be any subset of the natural numbers which has the following properties: (i) 0 ∈ E ; (ii) d ∈ E ; (iii) for any x,y ∈ E, one has x+y ∈ E. Let D ⊆ N ...
0
votes
1answer
18 views

How to prove a statement with multiple conditionals

Suppose I have a claim to prove: If x and y are distinct real numbers, then $$(x+1)^2=(y+1)^2$$ iff $$ x+y = -2$$ $$\n$$ In order to solve this do I tackle the if and only if part first? i.e. ...
-2
votes
0answers
17 views

graph (discrete math) and automata [closed]

These are 3 questions I have been asked in my assignment. I need help because I have taked the prerequisite the the course in the same semester. Question 1.Assume that G is a connected (undirected) ...
1
vote
1answer
21 views

Logic for implications

Example statement: Suppose we have a statement like : (P)Let S be a set... if (Q){other stuff} So I was wondering what the example statement refers to exactly. Is it Q -> P? Because Q comes after ...
1
vote
6answers
52 views

I'm not sure what this is exactly asking

Without using words of negation, write the meaning of : "f is not an increasing function" I did: $$"f\ is\ not\ an\ increasing\ function" \ \equiv\ "f\ is\ a\ decreasing\ function"$$ Is this what ...
2
votes
1answer
32 views

number of patterns of suit distributions in bridge deal

I would like to find the number of ways the suits can be distributed when the cards in a deck are dealt to 4 bridge players. If we let $a_{ij}$ be the number of cards in suit $j$ which are held by ...
0
votes
0answers
20 views

Some theorem of Newton (discrete Taylor expansion)

Let $\Delta$ be the forward difference operator, $\Delta f(x)=f(x+1)-f(x)$. Is there an elegant way to prove that for every $f\in\mathbf{Q}[x]$ (of degree $n$, say) the equality $$f(x)=\sum_{k=0}^n ...
0
votes
1answer
22 views

Are the negations of these statements correct?

If today is New Year's Eve, then tomorrow is January. Negation: Today is New Year's Eve and tomorrow is not January. If y is non negative, then y is positive or y is 0. Negation: Y is not a non ...
1
vote
2answers
21 views

Properties of functions throughout different domain/codomains.

Let f : S → T and g : T → U, then g ∘ f is injective implies that f is injective, and g ∘ f is surjective implies that g is surjective. Do these still hold if the functions are defined differently? ...
0
votes
1answer
26 views

How can I use these logical equivalences to rewrite this sentence?

Here are the logical equivalences: $p \rightarrow q \vee r$ $p \wedge \lnot q \rightarrow r$ $p \wedge \lnot r \rightarrow q$ Sentence: If $c$ is prime, then $c$ is odd or $c$ is $2$. How can I ...
3
votes
1answer
68 views

Is this proof that $\lfloor x \rfloor \geq n \left\lfloor \frac{x}{n} \right\rfloor$ correct?

In this text the fractional part of a real $x$ shall be denoted $\{x\}$, such that $x = \lfloor x \rfloor + \{x\}$. Theorem: $$ \forall x \in \mathbb{R}_{\geq 0} \forall n \in \mathbb{N}_{\geq 1} : ...
0
votes
1answer
21 views

Basis Composition of permutations

Hi I have the following questions: Calculate the following compositions of permutations on $A=\{0,1,2,3\}$ $(12)(102)$ Ans:$(02)$ $(01)(23)(0123)$ Ans:$(02)$ $(123)(32)$ Ans:$(13)$ ...
3
votes
2answers
70 views

Find the generating function of the sequence $a_n = \sum\limits_{k=0}^n k(k-1)$

Find the generating function of the sequence $ a_n =\sum\limits_{k=0}^n k(k-1)$ My try: Let's assume $k(k-1)$ is genereated by $F(x)$ then $a_n$ is generated by $\frac{F(x)}{1-x}$ (that's a ...
2
votes
2answers
36 views

Proof of Pascal' identity

The identity $$\binom{x+1}{k}-\binom{x}{k}=\binom{x}{k-1}$$ is claimed to hold (using the binomial polynomials, considered as lying in $\mathbf{Q}[x]$) for $k$ at least $1$. Proof: by the usual ...
1
vote
2answers
48 views

How can I use modus ponens or modus tollens to produce valid arguments? [closed]

I know this one is: $(1)$ If logic is easy, then I am a monkey’s uncle. I am not a monkey’s uncle. ∴ ? My answer: $\therefore$ Logic is not easy. (2) Can someone help me with this one? If ...
0
votes
3answers
64 views

How many bits are needed to represent the integers 3^1000 and 2^1000?

I'm struggling with a math exercise here, and I would gladly appreciate some help. My problem is that I've encoutered some very big numbers such as $3^{1000}$ and $2^{1000}$ and I want to estimate ...
0
votes
0answers
27 views

How many solution are possible for this multivariable equation? [duplicate]

$$2(a+b+c+d+e+f)+g=N$$ where $$a,b,c, \cdots ,N \in \mathbb{N}$$ Any lead will be appreciated.
3
votes
2answers
43 views

Could someone explain DeMorgan Laws?

I'm having a bit of trouble visualizing these laws we learned in class today. He mentioned DeMorgan's Law when dealing with Quantifiers, and wrote this on the board: $$\neg \forall x P(x) \iff ...
0
votes
1answer
22 views

Automorphisims of $\mathbb{Q}[\sqrt{d}]$

How can I show that Aut($\mathbb{Q}[\sqrt{d}])= \lbrace 1,\sigma\rbrace$ where $\sigma(x+y\sqrt{d}) :=x-y\sqrt{d} $ where $\sqrt{d}=i$. I know a automorphisim is a isomorphisim whose domain and ...
1
vote
0answers
56 views

Efficient calculation of minimal expected number of inversions

Problem: I have an array of size n with Z inversions initially and I am allowed to perform K operations where each operation can be decrease the number of inversions by 1. make a random shuffle of ...
0
votes
1answer
34 views

Verification of my set solutions [duplicate]

Can you verify my proof if it is right? Let A and B be sets. (a) Show that A is a subset of B if and only if for any set C, one has A U C is a subset of B U C. (b) Show that A is a subset of B if and ...
1
vote
0answers
32 views

Question concerning defining a particular class of functions

I have a multiset of real numbers $X \subseteq \mathbb{R} $ and I want to create a class of injective function to map the elements of $X$ to the unit interval(so basically a normalization). However ...
1
vote
1answer
44 views

Disproving the statement “$x^2\ne x$ for all $x\in\mathbb R$”

I am learning discrete mathematics in school and one of the practice question says: Find a counterexample for these quantifiers, where the domain for all variables consists of all real numbers. ...
0
votes
1answer
36 views

Discrete Mathematics - Logic

Let $UH = \{0, 1\}$. For each of the following formulae charaterize their models (tell what needs to be true for the formulae to be true). $\forall X(p(X,0,X))$ $\forall X\exists Y(p(X,Y,0))$ ...
1
vote
1answer
66 views

Prove $99^{100}>100^{99}$ using binomial theorem [duplicate]

Prove $0<(1+\frac{1}{n})<3$ and hence prove $99^{100}>100^{99}$. I did the first part and showed $0<\frac{1}{n^{n-1}}\le3$ and hence $0<(1+\frac{1}{n})<3$. But for the second bit, I ...
5
votes
6answers
148 views

What's the result? $1/i=?$, where $i=\sqrt{-1}$ [duplicate]

I just had my first math class in the university, and I understood everything pretty well, but I think I have misread this one because I read that the result is $-1$. Thanks for your answers!
1
vote
2answers
67 views

Understanding Inclusion-Exclusion principle

Problem: You have $20$ employees. $4$ of them are women. You have $50$ different jobs to give for your employees, but each women should get at least one job. The Proof: The author split the ...
1
vote
1answer
19 views

Discrete math assignment and pigeon-hole principle.

Assume that at the end of the semester there will be 30 students receiving grades for this class. Prove that some group of 3 students will get exactly the same letter grade (eg 3 students all earning ...
0
votes
2answers
66 views

Show that it is not true in general that for any sets A,B, one has P(A union B) is a subset of P(A) union P(B)

Show that it is not true in general that (i) for any sets A,B, one has P(A union B) is a subset of P(A) union P(B) Show that it is true in general that (ii) for any sets A , B , one has P(A) union ...
0
votes
1answer
30 views

How do I solve gcd(2569,856) with Euclid's extendeded algorithm?

With this algorithm I have to modulate until r = 0 Afterwards I have to find z and t in the formula gcd(2569, 856) = 2569*z + 856*t So here's what I've done: gcd(2569, 856) 2569 mod 856 2569/856 ...
1
vote
1answer
260 views

Let A and B be sets. Show that A is a subset of B if and only if for any set C, one has A union C is a subset of B union C.

Can you verify my proof if it is right? Let A and B be sets. (a) Show that A is a subset of B if and only if for any set C, one has A union C is a subset of B union C. (b) Show that A is a subset of ...
4
votes
8answers
128 views

Show that $n^3+2n$ is divisible by 3 for all $n\ge 1$

i want to prove it with mathematical induction : first i am tried with n=0 then it is divisible by zero then i move to next step change all n with K then i get this product : $$P(K)=K^3+2K = 3m$$ ...
0
votes
1answer
22 views

How many partitions are there?

How many partitions are there for $\{1,\cdots,100\}$ for $3$ sets, $A,B,C$, such that $A$ cannot contain consecutive numbers ($\left|a-b\right|=1$) Anyway, I thought about using recurrence ...
1
vote
1answer
61 views

Show that the product of $n(n+1)\cdots(n+k-1)$ is a multiple of $k!$.

my solution is to re-write the statement into $n(n-1)\cdots(n-k+1)$. Therefore, $[n(n-1)\cdots(n-k+1)]/(k!) = {n \choose k}$ which yields an integer therefore it is a multiple of $k!$. Or should i do ...
0
votes
1answer
38 views

Solve this 'Pigeonhole principle problem' without Pigeonhole principle

The question goes like this: Let $A = \{4,5,6,\ldots,61\}$. We will create set $B$ by randomly choosing $9$ different numbers out of A. We have to prove that there are at least 2 subset of $B$ ...
0
votes
1answer
67 views

Prove this recurrence relation? (catalan numbers)

$$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots + C_kC_{n−k} + \cdots + C_nC_0\text{ ?}$$ Where Cn denotes the number of ways of writing a valid list of open and closed parentheses of length ...
1
vote
1answer
22 views

Why is the equality right? (Set-Theory)

Let $A, B$ finite sets, and let $f,g\in A\to B$. Also, Let the equivalence class: $$f \sim g \iff \exists h\in Eq(A,A). f=g\circ h $$ Claim: $$f\sim g \iff \forall b\in B. \left| \left\{ a\in A : ...
0
votes
1answer
37 views

How many sequences are there (Using generating functions)

How many sequences are there, with the length of $n$ above $\left\{0,1,2,3,4\right\}$ such that the digits sum is $9$. The solution offers the following generating function for the problem: $$ ...
1
vote
2answers
34 views

Proof an inequality by mathematical induction

I have a problem that I have to solve using mathematical induction but I'm stuck from a part. The problem is: Proof that $\large n<2^n$ is true for $\large n \in \mathbb{N}\ $ So, I did that ...
0
votes
1answer
23 views

Ratios and probability mass function

It was given that $p_{2,3} = 2$ and $p_{0,1} = 12$ $p_{k, k+1} = \frac{P(X=k+1)}{P(X=k)}, k=0,1,2,...,n = (\frac{n-k}{k+1})(\frac{1-\theta}{\theta})$ The question was: Find $P(X \geq 2)$. Answer: ...
0
votes
1answer
37 views

Prove the growth of Fibonacci numbers

Consider a function defined by $f(1) =1$$f(2)=2$$f(n)=f_{n-1}+f_{n-2}$ for all $n>2$. Show that this function grows exponentially. how can I prove this using Master theorem, not using any other ...
1
vote
1answer
42 views

Segner's Recurrence Relation [closed]

Why is Segner's Recurrence Relation formula valid. Does anyone know how to prove it? I can't seem to understand why this formula works/is true. $$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots ...
1
vote
1answer
98 views

Proof of recursive formula for Catalan numbers, and their interpretation as the number of paths

If $C_n$ is the $n$th Catalan number, then show that they satisfy the following recurrence: $$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots + C_kC_{n−k} + \cdots + C_nC_0\text{ ?}$$ I tried ...