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
0answers
76 views

Chernoff Bounds. Solve the probability

Toss $n$ coins. What is the probability that we get more than $$ n/2 + 2\sqrt{n\cdot \log(n)}. $$ I have to use Chernoff Bounds here. If I let $X_i$ indicate whether coin $i$ comes up heads, ...
1
vote
3answers
195 views

Congruence Relation with exponents and variables

I am currently trying to solve a congruence relation with a constant and a variable, both of which have attached exponents. The relation is as follows: $7^{95}\equiv x^{3} (mod 10)$ How does one ...
1
vote
1answer
339 views

Variation of Coupon Collectors Problem, involving N Cereal Boxes and 6 Prizes

Suppose boxes of cereal are filled with a random prize, each drawn independently and uniformly from 6 possible prizes. If N boxes of cereal is bought, what is the expected number of distinct prizes ...
1
vote
3answers
232 views

Solution to a linear recurrence

What is the general solution to the recurrence: $x(n + 2) = 6x(n + 1) - 9x(n)$ for $n \geq 0$; with $x(0) = 0; x(1) = 1$? Solution. The first few values of $x(n)$ are $0,1,6,27,...$ The auxiliary ...
1
vote
2answers
145 views

pigeonhole principle and division

How is it possible to prove with the use of the pigeonhole principle that in every set of 2012 different numbers that are bigger or equal to zero there is at least one subset that if you sum up its ...
1
vote
2answers
632 views

Congruence Class $[n]_5$ (Equivalence class of n wrt congruence mod 5) when n = $-3$, 2, 3, 6

The question is, "What is the congruence class$[n]_5$ (that is, the equivalence class of $n$ with respect to congruence modulo 5) when n is a) 2? b)3? c) 6? d)−3?" I know this is more work ...
1
vote
2answers
89 views

Bounds on difference of squares representations of integers [duplicate]

Possible Duplicate: $a^2-b^2 = x$ where $a,b,x$ are natural numbers I'm trying to find all the $(m,n)$ pairs that satisfy $m^2-n^2=r$, where $r$ is a given positive odd integer, ...
1
vote
0answers
83 views

Count Exclusive Partitionings of Points in Circle, Closing Double Recurrence?

I am studying a problem that I have worked out is equivalent to the following: Problem Description Given N distinct points on the border of a circle, there are $B_N$ ways to partition them - where ...
1
vote
2answers
282 views

Finding the intersection of elements in a set

I was studying for finals and I came across this question: Assume that: $|A\cup B|=10, |A|=7$, and $|B|=6$. Determine $|A\cap B|$ How do I approach this question? I mean I know the the union ...
1
vote
2answers
671 views

Pigeonhole Principle question

There is a row of 35 chairs. Find the minimum number of chairs that must be occupied such that there are some consecutive set of 4 chairs or more occupied. I would like to have some hints as to ...
1
vote
1answer
428 views

Elementary Probability and Statistics

Choose any $38$ different natural numbers less than $1000$. Prove that among the selected numbers there exists at least two whose difference is at most $26$.
1
vote
3answers
430 views

Proof by Induction: Solving $1+3+5+\cdots+(2n-1)$

The question asks to verify that each equation is true for every positive integer n. The question is as follows: $$1+ 3 + 5 + \cdots + (2n - 1) = n^2$$ I have solved the base step which is where ...
1
vote
3answers
429 views

Strong Induction: Every natural number $n\geq 8$ can be represented as $n=3k + 5\ell$

Can you please help me and tell, how should I move on? Can this be proved by induction? Every natural number $n\geq 8$ can be represented as $n=3k + 5\ell$. Thank you in advance
1
vote
2answers
2k views

Troubles finding inverse modulus [duplicate]

Possible Duplicate: finding inverse of $x\bmod y$ Hello all Me and some friends are studying for a discrete exam and we are having some troubles finding the inverse modulus of things. ...
0
votes
2answers
115 views

Arranging books on the shelf.

There are five distinct computer science books, three distinct mathematics books, and two distinct art books. In how many ways can these books be arranged on a shelf if no two of the three mathematics ...
0
votes
2answers
28 views

Prove sum of combinations

Let n and r be positive integers with n ≥ r. Prove that C(r, r) + C(r + 1, r) + ... + C(n, r) = C(n + 1, r + 1) I would like to approach with mathematical induction. However, I don't understand what ...
0
votes
2answers
41 views

Using inclusion-exclusion principle to count the integers in $\{1, 2, 3, \dots , 100\}$ that are not divisible by $2$, $3$ or $5$

Question: How many integers in $\{1, 2, 3, \dots , 100\}$ are not divisible by $2$, $3$ or $5$? Can anyone give me a full explain of how this applies to the inclusion-exclusin principle? Because I ...
0
votes
1answer
61 views

How many combinations can I make?

let $n \gt 1$ be an integer, and consider $n$ people; $P_1, P_2,..., P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two ...
0
votes
1answer
40 views

Functions involving codomains

Problem: Consider the possible $f: [7]\to[9]$ a) How many have $f(i) $even , for all i? b) How many have rng(f) = {5,6} As far problem a goes, I've only gotten to the answer = 4^7. However I'm not ...
0
votes
2answers
156 views

the strings of five decimal digitis

My question is : Consider strings of five decimal digits, such as 00147, or 99999. In each case below, what is the number of such strings satisfying the given property? (a) The string has no repeated ...
0
votes
1answer
33 views

Show that are logically equivalent

Can you answer me , please. 1- Show that (p→r)∧(q→r) and (p∨q)→r are logically equivalent 2- show that (p → r) ∨ (q → r) and (p ∧ q) → r are logically equivalent without truth table .
0
votes
1answer
87 views

Predicate Logic Proof Question

I am struggling really hard with proofs I cannot seem to understand them at all no matter how hard i try. I'm thinking of getting a tutor because questions like this I just give up and fail on. Any ...
0
votes
1answer
80 views

Gambler's ruin and coin toss

Edit 3. Fixed question to be more clear and include current solution Problem Two players player 1 and player 2 plays a game of fair coin flipping. Player 1 starts with $A$ coins and Player 2 with ...
0
votes
1answer
242 views

Predicate Logic and Logic Proofs(Review & Homework Questions)

I'm working on some homework questions and I am struggling very hard with the logic proofs. I might have an incorrect answer for 1 of the predicate questions but I think my question makes some sort of ...
0
votes
2answers
83 views

Let $f : \mathbb Z\to \mathbb Z/x\mathbb Z \times \mathbb Z/y\mathbb Z$ be the homomorphism defined by $f (n) = (n + xZ, n + yZ)$…

For $x,y \geq 2$, let $f : \mathbb Z\to \mathbb Z/x\mathbb Z \times \mathbb Z/y\mathbb Z$ be the ring homomorphism defined by $f (n) = (n + xZ, n + yZ)$. (i) The kernel $K$ of $f$ is the ideal ...
0
votes
1answer
63 views

Proofing a Reachable Node Algorithm for Graphs

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
0
votes
2answers
50 views

show that $\det(A)=0$ in this case

(a) Let $x$ and $y$ be $n\times 1$ matrices, $n \ge 1$, and let $A=xy^T$. Show that $\det(A)=0$. (b) Explain why the statment in part (a) is false if $n=1$.
0
votes
1answer
64 views

Proving that these two sets are denumerable.

(a) $S_k=\{A\subset\mathbb{N}: |A|=k\}$ for $k\in\mathbb{N}$ (b) $S = \bigcup_{k=1}^\infty S_k$ Work: For (a), I am not too sure about what approach I should use. I think finding a bijective ...
0
votes
3answers
121 views

N-Dimension Hypercube question? (making sense of the question)

I just failed a test in discrete math. Here is the Question that cost me the most points: An n-dimension hypercube f(n) is defined as follows. Basis Step: f(1) is a graph with 2 vertices ...
0
votes
2answers
189 views

Proving that $f$ is a bijection from $N$x$N$ to $N$.

I am having trouble with the following problem: $f: N\times N\rightarrow N$ and $f(i,j)=2^{i-1}(2j-1)$. Prove that $f$ is a bijection thus $N\times N$ and $N$ are numerically equivalent. Work: I ...
0
votes
9answers
736 views

How to prove for each positive integer $n$, the sum of the first $n$ odd positive integers is $n^2$?

I'm new to induction so please bear with me. How can I prove using induction that, for each positive integer $n$, the sum of the first $n$ odd positive integers is $n^2$? I think $9$ can be an ...
0
votes
2answers
190 views

Proof by induction that $B\cup (\bigcap_{i=1}^n A_i)=\bigcap_{i=1}^n (B\cup A_i)$

$B\cup (\bigcap_{i=1}^n A_i)=\bigcap_{i=1}^n (B\cup A_i)$ I was able to prove this without using induction, however I am supposed to prove it using induction. How should I go about doing so?
0
votes
1answer
114 views

proving bitstrings [duplicate]

1.Let it be $a_n$ the number of bitstrings which contain 000 How would I prove that for $n\ge4$: $$a_n = a_{(n-1)} + a_{(n-2)} + a_{(n-3)} + 2^{n-3}$$
0
votes
1answer
51 views

Induction help discrete Math?

A) For what natural number is this claim true? B) Prove that your answer to (a) is correct using induction on n I know the answer is 3 for the first one but I don't know how to do the second ...
0
votes
1answer
206 views

Count the number of topological sorts for poset (A|)?

can someone please explain to me how to count the number of topological sorts for poset(A|) where A = {2,3,4,8,9,16,27,81} ? Quick example would be nice. Please help...I have an exam in several ...
0
votes
1answer
90 views

Element of, subset of and empty sets

I am trying to make sense of these. To me a is false because the set isn't empty. Is that correct? b is true because the empty set is an element of that set. c is false because the set the empty set ...
0
votes
1answer
110 views

I don't know where to begin with this functions question (one-to-one, onto)

a) Suppose that $f:\Bbb Z\to \Bbb Z$ is a one-to-one function. Define a function $g:\Bbb Z\to \Bbb Z$ by: for all integers $x$, $g(x)= -f(x)$. Prove that $g$ is also one-to-one. b) Suppose $f:\Bbb ...
0
votes
1answer
118 views

Reflexivity, Transitivity, Symmertry of the square of an relation

$\def\p{\mathrel p}$If $\p$ is a relation on a set $A$, define $\p^2$ by $a \mathrel{\p^2} b$ if and only if there exists $c$ with $a \p c$ and $c \p b$. If $p$ is reflexive/symmetric/transitive ...
0
votes
2answers
147 views

Formal definition of Mathematical Induction & Strong Induction

I have been reading some notes on Induction and Strong Induction and fully understand how they work. However I was interested in a formal/mathematical way of expressing their definition and was ...
0
votes
3answers
68 views

Induction to prove $2n + 3 < 2^n$

I am having trouble and was wondering if someone could go over the steps slowly to show that: $$2n + 3 < 2^n \ \text{for} \ n \geq 4$$ Any help would be amazing!
0
votes
2answers
604 views

Find out all solutions of the congruence $x^2 \equiv29 \mod 5$.

Find out all solutions of the congruence $x^2 \equiv29 \mod 5$. [Hint:Find the solutions of this congruence $\mod 5$ , $\mod 7$ , and $\mod 7$ , and then use the Chinese Remainder Theorem.]
0
votes
1answer
195 views

Equivalence Relation? Column-equivalence on the set of all $m\times n$ matrices.

How do I show that column equivalence on the set of all $m\times n$ matrices is an equivalence relation? I know that to show it is an equivalence relation, I need to show that column equivalence is ...
0
votes
3answers
1k views

Isomorphism between two particular graphs

Are these two graphs isomorphic?
0
votes
1answer
72 views

How many cases are there in this specific example?

$\lfloor (n+m)/2\rfloor\ = \lfloor m/2\rfloor\ + \lceil n/2 \rceil $ I thought it was 4, but I am not sure n greater than 1 and greater than 2 m greater than 1 and greater than 2 trying to do a ...
0
votes
3answers
1k views

Sum of three squares: need to check the expressions with the lower powers of $4$.

It is a well-known theorem that a positive integer cannot be expressed as a sum of three squares iff. it is of the form $4^n(8m+7)$ for some non-negative integers $m$ and $n$. E.g. ...
0
votes
1answer
2k views

Positive integers less than 1000 without repeated digits

How many integers from 1-999 do not have any repeated digits? The answer is explained in this link, but why is the last set 9*9*8? Why not 9*9*9?
0
votes
3answers
415 views

Discrete Fibonacci sequence problem

The Fibonacci sequence satisfies $F_0 = F_1 = 1$ and the recurrence relation $F_k=F_{k-1}+F_{k-2}$ for all integers $k\geq 2$. Prove that $F_k+2F_k-F_{2k+1}= (-1)^k$ for all integers $k\geq 0$.
-1
votes
1answer
484 views

how to determine the largest n for which one can solve within one second using an algorithm

So I am confused on this problem for my discrete math class, I didn't know if there was a specific formula you were supposed to use or what. The question is "What is the largest n for which one can ...
-2
votes
2answers
126 views

$x_1+x_2+\cdots+x_n\leq M$: Cardinality of Solution Set is $C(M+n, n)$

Show that the number of solutions in nonnegative integers of the inequality $$x_1+x_2+\cdots+x_n\leq M,$$ where $M$ is a nonnegative integer, is $C(M+n, n)$.
-5
votes
1answer
107 views

Are variables the same in pure mathematics??? [closed]

my question is In pure mathematics, $x$ always $=x$ $x = x$, the variables are abstract. In modelling, $t$ could mean the time that has elapsed since you started a machine for example. Or ...