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
1answer
91 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 ...
1
vote
1answer
97 views

Help understanding solution to growth of partition function

I'm currently a Combinatorics student trying to parse through this solution. I do not understand the proof currently. Any help understanding it is greatly appreciated. Question Let the number of ...
1
vote
2answers
153 views

Extended euclidean algorithm

So I am trying to figure this out. And for one of the problem the question is x*41= 1 (mod 99) And the answer lists ...
1
vote
2answers
59 views

Polynomial Question

Find polynomials $A(x)$ and $B(x)$ such that $A(x)P(x) + B(x)Q(x) = x + 1$ for all $x$ where $P(x) = x^4 - 1$ and $Q(x) = x^3 + x^2$. I'm stumped on this question. I know that I'm supposed to apply ...
1
vote
1answer
211 views

Venn diagram question

Here is my question. A math examination has three questions. Twenty-six students took the examination, and every student answered at least one question. Six students did not answer the first ...
1
vote
3answers
824 views

Is 'every exponential grows faster than every polynomial?' always true?

My algorithm textbook has a theorem that says 'For every $r > 1$ and every $d > 0$, we have $n^d = O(r^n)$.' However, it does not provide proof. Of course I know exponential grows faster ...
1
vote
1answer
218 views

Stirling numbers combinatorial proof

This is a Homework Question. I am required to give a Combinatorial proof for the following. $$S(m,n)=\frac 1{n!} \sum_{k=0}^{n} (-1)^k\binom nk (n-k)^m$$ Hint given is : Show that $n!S(m,n)$ ...
1
vote
0answers
90 views

What is the best way to solve discrete divide and conquer recurrences?

Note: I have converted my announcement into a question and supplied an answer. What is the best way to solve discrete divide and conquer recurrences? The "Master Theorem" is one way. What other ...
1
vote
3answers
329 views

Proof of identity $F_m F_n + F_{m−1} F_{n−1} = F_{m+n−1}$ for Fibonacci numbers

I'm lost on where to start on this proof: Using the fact that $A^m A^n = A^{m+n}$ , prove the identity $F_m F_n + F_{m−1} F_{n−1} = F_{m+n−1}$ I want to use induction starting with n = 1, but would ...
1
vote
0answers
77 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
201 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
349 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
247 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
689 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
288 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
688 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
429 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
436 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
432 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
1answer
37 views

Is the relation on integers, defined by $(a,b)\in R\iff a=5q+b$, a function? [closed]

Let $A=B=\mathbb N$. Relation $R$ is: $(a,b)\in R$ iff for some $q \in \mathbb Z$ we have $a=5q+b$ Given a relation, show that it's a function. To Show: $\forall a \in A \ \exists b \in B$ such ...
0
votes
2answers
136 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
29 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
0answers
43 views

Mathematical proof to find the length of each side of a square filled with Regular Hexagons

I have to prove or disprove that in a square box if there are full regular hexagons( whose distance from center to every corner is r) inside it, then the centers of those hexagons should lie inside ...
0
votes
2answers
54 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
63 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
164 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
99 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
88 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
263 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
2answers
156 views

Recurrence Relation Solving Problem

Can anyone help me in solving this complex recurrence in detail? $T(n)=n + \sum\limits_{k-1}^n [T(n-k)+T(k)] $ $T(1) = 1$. We want to calculate order of T. I'm confused by using recursion tree ...
0
votes
1answer
67 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
52 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
65 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
126 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
212 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
760 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
255 views

List of calculation rules for asymptotic notation?

Background: I am working my way through CLR/CLRS's proof of the master theorem (section 4.4 in the 1st and 2nd editions of Introduction to Algorithms), and I'm doing my own write-up of this proof1 ...
0
votes
2answers
193 views

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

$\displaystyle 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 ...
0
votes
1answer
116 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
208 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 ...