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

2
votes
2answers
72 views

How to substitute sum variable?

I am not entirely sure how to use variable substitution for a sum. Take the following example: I would like to compute $$\sum_{i=1}^N(2i-1)^2$$ One straightforward way is to split the sum, i.e. ...
4
votes
2answers
182 views

How many arrangements are there with $n$ zeros($0$) and $m$ ones($1$) and $k$ runs of zeros

How many arrangements are there with $n$ zeros($0$) and $m$ ones($1$) and $k$ runs of zeros.A run is the same digit occurring consecutively 1 or more times. For example: $110010001110$ has 3 runs of ...
0
votes
0answers
55 views

Is this method correct for solving equation?

I have the following equation $z=1.093x^{0.002939}- 0.1887(x^{0.7637} )(y^{0.2306} )- 0.04425y^{0.9143}$ I want to find expression $x$ Is my method correct? I can add powers of same variables? $z+ ...
0
votes
1answer
36 views

prove $n(A \oplus B) =n(A) + n( B) - 2n(A \cap B)$

I can see the logic but can't put myself to see the reasoning. I don't know how to prove these type of questions, so so far I've been setting up an element $x$ contained in the left hand side and ...
1
vote
1answer
30 views

Ratio of vertices to edges when airplaines can fly from 1 of 4 cities to any other of the 4 cities

This is a true of false question: There are direct (nonstop) flights amount four cities that make it possible to get from any city to any other city by air. It follows that the beta index of the ...
2
votes
1answer
66 views

Discrete math counting question help

100 students from each of the 3 schools form a line. For each student (except the 1st and the last), the two neighboring students must be from 2 schools different than his/her school. The 1st and last ...
1
vote
4answers
421 views

Prove that $R$ is an equivalence relation.

Define the following $R$ on the set of integers $\Bbb{Z}$ $(a,b) \in R$ if and only if $3a + 5b$ is divisible by $8$ Prove that $R$ is an equivalence relation. Attempt: Reflexive: a~a if and only ...
0
votes
1answer
134 views

identity and inverse elements from a group

so, i have this Question: based on a set $\mathbb{Z}$x$\mathbb{Z}$ provided by this expression: $(a,b)*(c,d) = (ac,bd)$ find the identity element and the inverse element. finding the identity ...
0
votes
1answer
37 views

Power Relation $\ge$ on the Set of Natural numbers

Good afternoon, I am having trouble defining the following: Let $R$ denote the binary relation $\ge$ on the set of Natural Numbers $\mathbb N$. Find $R^2$. What I have so far for R: ...
0
votes
2answers
42 views

Congruence equation proof

Proof that $\forall{a}\in\Bbb N \rightarrow a^3\equiv a\mod (a+1)$ I do not know how to prove these equations. I only know that $a\equiv m \mod b \implies m | ( b- a ) \implies b-a=m\times k $ for ...
0
votes
1answer
72 views

Predicate Logic using Quantifiers

$$\lnot \forall y: Y.A\vdash \exists y: Y.(A\rightarrow B)$$ Need to prove that LHS entails RHS, however I'm confused as to how to do it. Never used a negation on a universal quantifier before. ...
1
vote
1answer
47 views

Combinatorics / nCr - How do I set this up?

A Bag contains 5 red and 5 green gumballs. If you select 4 of them without looking, how many ways can you get exactly 3 red or exactly 2 green gumballs? I am unsure of how to start his. I know it has ...
1
vote
1answer
138 views

Writing statements into symbols Discrete Math

The variable $x$ represents stduents, $F(x)$ means "$x$ is a freshman", and $M(x)$ means "$x$ is a math major" a) some freshme are math majors? $\exists x:F(x) \implies M(x)$ b) Every math major is ...
0
votes
3answers
163 views

Find two sets $A$ and $B$ such that $A$ is an element of $B$ and $A \subseteq B$.

Find two sets $A$ and $B$ such that $A$ is an element of $B$ and $A \subseteq B$. Would $A = \{1,2,3\}$ and $B = \{1,2,3\}$ work? Any help?
1
vote
2answers
334 views

Universal set of subsets A and B

The question is: Two subsets given: $A = \{ Z, H, O, V, N, I, R \}$; $B = \{ I, G, O, R \}$ The aim is to find universal set of this subsets. I tried to use definition of "universal set" and here are ...
0
votes
1answer
14 views

sums of row on graphs

I'm not sure how to express the sum of rows of an adjacency matrix for a directed graph. I know for an indirect it is deg(v). I guess it would be an "out-degree" but I don't know how to represent ...
1
vote
1answer
31 views

Combinatorial help

I completely understand the algebra behind this, but I'm having trouble writing a worded combinatorial proof to show C(2n,2) = 2C(n,2) + n^2 Can anyone at least hint me in the right direction?
0
votes
2answers
48 views

Whats the solution of this problem

Let $R_1 = \{(x, y): |x - y| ≤ 1\}$ and $R_2 = \{(x, y): 2x + y ≤ 6\}$ be relations on the set $A = \{1, 2, 3, 4\}$. List the elements of $R_1$ and $R_2$.
2
votes
5answers
700 views

How many numbers must be selected from the set

How many numbers must be selected from the set {1, 3, 5, 7, 9, 11, 13, 15 } to guarantee that at least one pair of these numbers add up to 16, explain your answer?
2
votes
2answers
71 views

Using a combinatorial proof [duplicate]

How should I solve this problem? can anyone help? Thanks.
2
votes
1answer
61 views

How many integer solutions does $x_{1} + x_{2} + x_{3} = 14$ have ?, where $x_{1} , x_{2} \geq 0$ and $x_{3} > 2$.

How many integer solutions does $x_{1} + x_{2} + x_{3} = 14$ have ?, where $x_{1} , x_{2} \geq 0$ and $x_{3} > 2$. What should I do with this kind of problems ?. Thanks.
7
votes
10answers
2k views

Prove by induction that $5^n - 1$ is divisible by $4$.

Prove by induction that $5^n - 1$ is divisible by $4$. How should I use induction in this problem. Do you have any hints for solving this problem? Thank you so much.
1
vote
2answers
701 views

Let A,B and C be sets. Using set identities, show that:

Let A,B and C be sets. Using set identities, show that: (a) A ∪ ( B-A ) = A ∪ B (b) (A-B)-C = (A-C)-(B-C) how should I solve this problems? Thank you so much.
-1
votes
1answer
34 views

Which equation has a solution $(x,y)$ i which both $x$ and $y$ are integers?

Which equation has a solution $(x,y)$ in which both $x$ and $y$ are integers? $12x + 9y = 16$ $32 x + 80y = 27$ $42x + 56y = -28$ $20x + 90y = 105$ Do we have to use discriminant ($b^2 - 4ac)$ ...
0
votes
2answers
418 views

Give an example of two uncountable sets A and B such that A − B is

Give an example of two uncountable sets A and B such that A − B is a) finite. b) countably infinite.
2
votes
3answers
146 views

Prove that either $(2^{10500} + 15)$ or $(2^{10500} + 16)$ is not a perfect square. [duplicate]

Prove that either $(2^{10500} + 15)$ or $(2^{10500} + 16)$ is not a perfect square. how should I solve this problem? what is the idea for solving this kind of problems? Thank you so much
2
votes
2answers
79 views

Show that each of the following is a tautology. [closed]

Show that each of the following is a tautology. (a) [(p∨q) ∧ (p → r) ∧ (q → r)] → r (b) [¬p ∧ (p ∨ q)] → q
1
vote
1answer
84 views

Probability - Testing for diseases

I am just learning probability in my Discrete Structures class and am very lost. This is the example given in the book and I have no idea how to solve this problem. Problem: Suppose one in 1000 ...
0
votes
1answer
42 views

Cardinalities of power sets, $\mathbb{N}$, and $\mathbb{R}$.

Does there exist a set $X$ so that $|\mathcal{P}(X)|=|\Bbb{N}|$? What about $|\mathcal{P}(X)|=|\mathbb{R}|$? I'm pretty sure that the answer is no for the first one, and yes for the second one ...
-1
votes
2answers
28 views

Discrete Math Functions

$f:\mathbb N\to\mathbb N$ such that $f(x) = 2x$. $f:\mathbb Z\to\mathbb Z$ such that $f(x) = 2x$ How are these two different? And also $h:\mathbb R\to\mathbb R$ where $h(x) = \sqrt x$ $f:\mathbb ...
1
vote
3answers
66 views

Prove, by induction, that $5^n + 5 < 5^{n+1}$ for all $n\in\Bbb N$.

Prove, by induction, that $5^n + 5 < 5^{n+1}$ for all $n\in\Bbb N$. Attempt: If $n = 1$, then $5^1 + 5 < 5^{2}$ => $10 < 25$ which is a true statement so the base case holds. Assume $5^k + ...
0
votes
4answers
67 views

If $c$ is a positive real number, then the equation $2x^2 - 3x - c = 0$ has:

Multiple Choice: If $c$ is a positive real number, then the equation $2x^2 - 3x - c = 0$ has: (a) No Solutions (b) one solution (c) two solutions (d) three solutions Attempt: Can we assume $c$ to ...
-1
votes
2answers
135 views

Which function is an injection but NOT A SURJECTION

Which function is an injection but NOT A SURJECTION? (1) $h:\mathbb{N} \rightarrow\ \mathbb{Z}$ $h(x) = x^2 + 5$ (2) $p:[0,\infty) \rightarrow\ [5,\infty)$ $p(x) = x^2 + 5$ I think (1) is ...
2
votes
1answer
142 views

Write the negation of the following statement (in words):

"For any field $F$, and any $a\in F$, if $a^3 = 1$ then $a = 1$." Is this statement TRUE OR FALSE? Is the negation TRUE OR FALSE? Attempt: There is a field $F$ and there is an $a \in F$ such that ...
0
votes
4answers
91 views

How many four digit numbers are there?

Assume that 0 can't be a first digit. I got 9,000. Is that right? Follow up question: How many of those four digit numbers have no repeated digits?
0
votes
1answer
42 views

Congruence equation problem [verification]

Solve the equation $144x\equiv24\mod228$ giving all the integer and not congruent solutions. So, there's solution for this equation if and only if $(228:144)=d\implies d|24$ By the Extended ...
1
vote
3answers
49 views

Help with sequence: $a_k = 5*3^k + 7*2^k$ - Induction

Let $a_k$ be a sequence, where $a_0 = 12$, $\;$ $a_2 = 29$ and $a_k = 5a_{k-1} - 6a_{k-2}$ , $k\geq 2$ . I need to prove, using induction, that $a_k = 5\times 3^k + 7\times 2^k \; , k\geq 0$ . ...
1
vote
1answer
37 views

Generating function for division of $n$ into smaller subsets.

I need to find the generating function for the number of ways of dividing $n$ into parts out of even numbers. The ways are only different if their parts are different, meaning that $2+1+2$ and $2+2+1$ ...
0
votes
1answer
31 views

Advice for proving with induction scenarios with multiple chances for using the hypothesis.

I have done many, many questions about solving induction exercises. I managed to grasp a basic strategy: write all the information, take the statement you want to prove, try to apply the hypothesis ...
1
vote
1answer
37 views

What is meant by a|a notation?

Is the "divides" relation on set of positive integer reflexive? In solution of above question I found following. ...
0
votes
1answer
193 views

Proving number of digits d to represent integer n in base B?

I am interested in learning about proofs for discrete mathematics. One recurring fact I find in the literature is that the number of digits $d$ required to represent integer $N$ in base $B$ is ...
0
votes
1answer
322 views

Give a recursive definition

Give a recursive definition of a) The set of odd positive integers. b) The set of positive integers powers of 3. Solution for a) $ a^0 =1$ $ a^n = 2n+1 $ Is that right ? and how can i find b) ? ...
3
votes
2answers
288 views

Pigeonhole Principle: birthdays on same day of week

How many people must be in a room so that at least 10 have a birthday on a Friday? edit: Assume that no two people share the same birthday I'm somewhat confused and see two different ways to ...
0
votes
1answer
40 views

Prove that if and q are two distinct prime numbers, then …

Prove that if $p$ and $q$ are two distinct positive prime numbers, then $log_p(q)$ is irrational. I think first we have to assume $log_p(q)$ is rational.
2
votes
1answer
527 views

Expressing a positive integer as a sum of positive integers

I am trying to find a way for the positive integers written as the sum of other positive integers.( expressed in terms of some functions) I searched a bit and I came across with Partitions But in my ...
2
votes
2answers
200 views

Coin probability question

Question: Suppose that we flip a coin until either it comes up tails twice or we have flipped six times. What is the expected number of times we flip the coin? I thought the answer was 4 because if ...
2
votes
1answer
57 views

Finding probability of earning points

A professor asks a true/false question with ten individual questions. Suppose the professor assigns grades of: $10$ points for each correct response, $0$ points for each absent response, and $-10$ for ...
0
votes
1answer
54 views

Defining an Infinite Matrix

Hey I am getting ready for my final exam and I'm having trouble figuring out this practice question: Let X be a random variable that takes values in {0,1,2,3,...}. It is known that: E(X) = ...
2
votes
2answers
332 views

Choosing a committee (combination problem)

A group of people is comprised of six from Nebraska, seven from Idaho, and eight from Louisiana. In how many ways can a committee of six be formed with two people from each state? ${^6C_2} \times ...
0
votes
1answer
112 views

Expected probability of coin flips

I would appreciate help with my exam studying. A question asks: If we flip a coin 30 times, with every head winning 5 dollars and for every tail losing 4 dollars. What is the expected value $E(W)$ of ...