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

Prove that a recurrence relation (containing two recurrences) equals a given closed-form formula.

Prove that $a_n = 3a_{n-1} - 2a_{n-2} = 2^n + 1$ , for all $n \in \mathbb{N}$ , and $a_1 = 3$ , $a_2 = 5$ , and $n \geq 3$ Basis: $a_1 = 2^1 + 1 = 2 + 1 = 3$ $\checkmark$ $a_2 = 2^2 + 1 = 4 + 1 = 5$ ...
-3
votes
0answers
16 views

Parabolic Integration [on hold]

Hello, please i would like to understand the step from the first integral to the seconde. thanks
1
vote
1answer
12 views

Big O and Big Omega Proof with lg base 2

Hello I am a beginner to this kind of notation and I would greatly appreciate an explanation which is easy to understand. I need to prove $$ \log_2(6 + \frac1x) = O(1) $$ and $$ \log_2(6 + ...
2
votes
0answers
28 views

(Concrete) mathematical aspects of programming

It is often said that progamming is mathematics as it "makes use" of "discrete mathematics". However, I would like to ask a more concrete question: what are the concepts of a programming ...
0
votes
3answers
42 views

Showing that $S_1 \cup S_2$ is countable [duplicate]

Let's say that $S_1$ and $S_2$ are two countable infinite sets that are disjoint (i.e. $S_1 \cap S_2 = \emptyset$). How would you show that $S_1 \cup S_2$ is also countable?
0
votes
0answers
17 views

Ramsey Numbers and edge coloring

Show that for every $k \in\mathbb{N}$ there exists an $n \in\mathbb{N}$, where $n ≤ 3k!$ such that if $K_n$ is coloured in $k$ colours then we can find in $K_n$ a triangle whose edges are of the same ...
5
votes
1answer
46 views

Combinatorics - Without order

You have 10 different types balls to choose from. How many different ways are there to choose 5 balls such that no type of ball appears more than twice. My attempt: Case 1 (selecting different ...
2
votes
3answers
29 views

How do I describe a set of names?

I want to describe the following set... { "Person1", "Person2", "Person3"... } ... where the number is from 1.. 100. How do I do this using mathematical set ...
4
votes
5answers
89 views

Proving a Statement using Mathematical Induction

I'm trying to prove that $6 \mid (n^3 - n)$ where $n$ is a nonnegative integer. I started off by proving the basic step with $P(6)=4$. The next step would be the induction. However I'm having a bit f ...
-1
votes
0answers
17 views

Discrete Mathematics; Counting, Summations [duplicate]

Let n ≥ 1 be an integer. Prove that: $$ \sum\limits_{i=1}^n i(\frac{n}{i}) = n \bullet 2^{n-1} $$ I am not sure how to prove this, I think I need to use the derivative of $$(1 + x)^ n$$ any help ...
1
vote
1answer
28 views

Number of Partitioning a deck with m cards in n types into n-element sets.

For exsample, There are 2cards in 3type. AA,BB,CC. Partition 6cards into 2 3-element sets. [AAB,BCC],[AAC,BBC],[ABB,ACC],[ABC,ABC],... 4 ways or Partition 6cards into 3 2-element sets. ...
0
votes
2answers
41 views

array of $n$ numbers, find the $2$ missing numbers

Given an array of size $n$. It contains numbers $1$ to $n$. Each number is present at least once, except for $2$ numbers. What algorithm will allow you to find the $2$ missing numbers?
2
votes
1answer
25 views

Find the covariance of $Y_1$ and $Y_2$

I had a statistics question I was hoping for help on: Let $Y_1$ and $Y_2$ be discrete random variables with join probability function: $$f(x,y) = \begin{cases} \dfrac{y_1 + 2y_2}{18} & \text{if ...
1
vote
2answers
29 views

Proving $\sum_{k=0}^{n} {n \choose k} = 2^n$ with Newton's Binomial Theorem

I'm having a hard time proving this theorem from a textbook. Theorem For any integer $n \ge 0$, we have $$\sum_{k=0}^{n} {n \choose k} = 2^n$$ Proof Take x = y = 1 in Newton's Binomial Theorem My ...
0
votes
0answers
8 views

finding percentge given number range

I have a range from 2.3566e-19 to 0.0010997 I'm trying to get the bottom 10% and the top 10% the formula / numbers I used is below but the answer doesn't look right how can I fix this. ...
1
vote
1answer
37 views

How does $n(n-1)(n-2)\cdots(n-m+1) \cdot \frac{(n-m)(n-m-1)\cdots1}{(n-m)(n-m-1)\cdots1} = \frac{n(n-1)(n-2)\cdots1}{(n-m)(n-m-1)\cdots1} $

I'm having issues understanding how the previous line goes to the net line. $$ \text{Assume } m \le n \\ n(n-1)(n-2)...(n-m+1) \cdot \frac{(n-m)(n-m-1)\cdots1}{(n-m)(n-m-1)\cdots1} \\ = ...
0
votes
3answers
52 views

Proof by Contrapositive?

i am having trouble proving the statement below using Proof by Contrapositive. I have negated the statements as required and then i prove that $n$ is odd if and only if $7n+4$ is odd. However, from ...
-4
votes
0answers
18 views

Discrete Math - graph theory [on hold]

Need help on Discrete Math Thanks!! Matt
0
votes
0answers
20 views

Proving bijection of a function of the form f(x,y).

I am trying to prove that the function $f:\mathbb{R}^2\rightarrow \mathbb{R}^2$ defined by $$f(x,y) = ((x^2+1)y, x^3)) $$ is bijective. I know that to prove a function is bijective we have to prove ...
0
votes
1answer
26 views

Modify the Cantor pairing function

I have an infinite set of pairs $I:=\{(k,m) \mid k,m \in \mathbb{N},\quad m\geq 1, \quad 1\leq k\leq m\}$. I want to establish a bijective correspondence $\phi$ between $I$ and $\mathbb{N}$. I've ...
1
vote
1answer
20 views

Prove that for all $m$, there exist some $k$, such that $(m-n)^2 > m^2$ for all $n>k$

I have a problem where I need to prove: $\forall m \in \mathbb{N}:\exists m \in \mathbb{N} ∋(m−n)^2>m^2~∀n>k$ My thought was since it is only "there exists some k.." can I not say: if $k = ...
0
votes
2answers
27 views

Logical equivalence + Quantifiers (Universal and Existential)

I'm taking a Discrete Mathematics course and we're using Rosen's book (which I hate because it seems like it makes difficult material to understand even more incomprehensible). Trouble is, I am lost ...
1
vote
2answers
48 views

Isn't $ n(n-1)(n-2)…(n-m+1) $ a factorial already?

Let $ m \ge 1 $ and $ n \ge 1 $ be integers Let $A$ be a set of size $m$ Let $B$ be a set of size $n$ How many one-to-one functions $f: A \rightarrow B$ are there? skipped stuff $$ ...
0
votes
1answer
26 views

the sum of two unbounded normal operators

why A and B are normal?and why "0" is not closed on H1(R)?
-1
votes
0answers
21 views

Probability helps to evaluate a sum

Let's consider a sum $$\sum_{n=0}^{m} \binom {n+m} {n} \cdot 2^{-n}$$. How does this sum can be evaluated, considering the topics about probability? One of the solutions is written at the "Concrete ...
1
vote
1answer
22 views

Determining if a function is one-to-one or onto.

We have two sets: {1,2} and {a,b,c}. How would I go about listing the functions between these two sets and then identifying if those functions are either one-to-one or onto? Would the functions be ...
0
votes
2answers
32 views

placing couples in a circle combinatorics question

In how many ways you can sit n men and n women so that : a) Every man sits near his wife. b) None of the men can sit next to thier wives. I think the answer for A is 2(n-1)!, not sure if it's true ...
2
votes
2answers
78 views

Counting the numbers with certain sum of digits.

The question : In how many different numbers between $1$ and $100000000$ have the sum of their digits equal to $45$? I'm thinking about using the stars and bars formula but I'm not sure if it's ...
1
vote
4answers
22 views

Completing simplification step when solving a recurrence

I am trying to understand a simplification step in one of the recurrence examples solved by repeated substitution in a book of algorithms problems I found on Github. I am using it for extra practice ...
2
votes
0answers
18 views

Erdős-Szekeres theorem on monotone sequences

Given a sequence $S$ with $21$ different numbers. It is known that there isn't any monotone subsequence in the length of $6$. Prove that there exists $2$ monotone subsequences, one decreasing and the ...
0
votes
3answers
30 views

Combinatorics question about picking a staff

This is the Question : In a building there are 5 men and 5 women. we need to pick representive for the building so that at least one woman and at least one man has to be there. there are no limitions ...
-1
votes
1answer
27 views

Counting relations question

I have a small question about relation counting, i'm looking for formulas. I know that there is a formula for reflexive and anti reflexive. I'm not sure about the simetric or a-simteric ones, and if ...
4
votes
1answer
41 views

$\land,\lor$ and $\lnot$ determinate a functionally complete basis

I read that a Boolean algebra is defined by the binary operations $\land$ and $\lor$ and the unary operation $\lnot$ on a set such that $$\varphi\land(\psi\land \chi)=(\varphi\land \psi)\land ...
0
votes
0answers
31 views

Importance Sampling of 2D constant piecewise function convertible to 1D?

So I have a constant piecewise 2D function (luminance values of pixels of an image) that I am writing an importance sampling algorithm for. I was going to write my algorithm by first sampling the 1D ...
-2
votes
1answer
38 views

using boolean law to simplify equation

I need to use boolean laws to simlfy the folliwng: a) (A+B)(C+D)+(A+B)(C'+D')= what I did for a) (A+B)(C+D)+(A+B)(C'+D') (A+B)[(C+D)+(C'+D')) (A+B(C+B)+(A+B)(c'+D') (A+B(C+B)+(A+B)(c'+D') Am I ...
-1
votes
1answer
158 views

Am I solving this question correctly?

How can I evaluate the following term: $$\left((\{a,b\}\cup\{b,a\})\times(\{b,a\}\cap\{a,b\})\right)\setminus \left((\{b,a\}\setminus\{a,b\})\cup(\{a,b\}\times\{b,a\})\right)$$ You can see the notes ...
-1
votes
0answers
27 views

Am I doing the Cartesian product of sets correctly?

Question in the image and how I attempt to solve it. Did I do it correctly? And is that the right answer?
-3
votes
0answers
63 views

Proving that $x’y’ + yz’ + x’z’ = yz’ + x’y’$ using the laws of Boolean algebra. [duplicate]

I'm trying to prove the following identity using the laws of Boolean algebra. $$x’y’ + yz’ + x’z’ = yz’ + x’y’$$ Here's what I've tried: [insert attempt here]
0
votes
0answers
25 views

Clique cycles structure

I am currently going through the paper "Covering two-edge-coloured complete graphs with two disjoint monochromatic cycles" by Peter Allen (http://www.ime.usp.br/~allen/twocycle.pdf) and I have some ...
0
votes
1answer
22 views

The drawer has M different colored socks. What is the least amount of socks I that I need to draw to guarntee N pairs

So in my discrete math class, we all know that if the drawer has 2 different colored socks, you need to pull out 3 socks to ensure a pair. However, I am puzzled after there are more different ...
1
vote
1answer
41 views

What does it mean for a function to be $\Omega(1)$?

I am having a lot of trouble understanding this. Could someone put this in a context I might understand?
1
vote
3answers
42 views

Arranging a word

This is the question : In how many ways you can arrange the word AAABBCDEFG so that the first letter is A or E ? I'm not sure if im doing this right. My plan is to take all the arrangments and ...
0
votes
1answer
26 views

Diving students into teams

So this is the question : Count the number of ways in which you can divide a group of 33 sudents into 3 soccer teams (each team has 11 studends, them have no names). I know that i shouldn't use the ...
0
votes
0answers
4 views

Multinomial Coefficients proof?

prove that if n and m are positive integers, then ∑ (n )*(−1)^(k2+k4+...+k2l) (k1,...,km) k1+...+km is equal to 0 if m =2l, and is equal to 1 if m = 2l + 1. Please ...
1
vote
1answer
47 views

Theory of definitions

I am reading "Introduction to Logic" by P Suppes at the moment. In the Chapter 8 - Theory of definitions of it, I 've some confusion, actually about the Conditional Definition. The brief explanation ...
0
votes
0answers
15 views

Proving a Recurrence Using Substitution

I am trying to understand an example of solving a recurrence using substitution (or unrolling it) in my book right now, but all of the steps do not seem clear to me. Here is the basic example: ...
0
votes
2answers
35 views

Discrete maths proving a random observation

Suppose you had 6 points. Each point can choose to either visit another point, or choose not to visit another point. However, it can't visit itself. In addition, visiting another point works in both ...
1
vote
2answers
52 views

How to get to $5^3 \geq n^3$ in the proof by contradiction?

This is the same problem asked here. - Next step to take to reach the contradiction? Here is it again. I understand the solution - how you want to get to the fact 100 divides n^2 and then go ...
0
votes
2answers
52 views

how to prove boolean identities

I'm working on 2 boolean proofs (¬p⊕q)=(p⊕¬q=¬(p⊕q) <- I assume its equality law i'm not sure how to do this problem(I verified using truth table but I need to do algebraically) ...
1
vote
0answers
20 views

Find all points on the line 9x-21y=6

For this equation we are suppose to use the Euclidean Algorithm. But I run into a problem For the GCD (9,-21)= i tried 9=(-21)(0)+9 -21=9(3)+6 9=6(1)+3 6=3(2) +0 which gives a gcd of 3 and the ...