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
1answer
1k views

Prove that the maximum number of edges in a graph with no even cycles is floor(3(n-1)/2)

The question is in the title. I can see why the bound is sharp (for example, a lot of triangles sharing one common vertex if n is odd, or the same but with one spare edge hanging out if n is even). ...
2
votes
1answer
557 views

Find Total number of ways out of N Number taking K numbers every M interval

I have been stuck in a problem, that has thrown my brain out of the coding. This problem is at very high priority and I need the solution as early as possible. Problem is as : There are exactly N ...
2
votes
1answer
1k views

probability of hand with at least 2 kings

A hand H of 5 cards is chosen randomly from a standard deck of 52. Let E1 be the event that H has at least one King and let E2 be the event that H has at least 2 Kings. What is the conditional ...
2
votes
1answer
452 views

Factoring a number $p^a q^b$ knowing its totient

We are given: $n=p^aq^b$ and $\phi(n)$, where $p,q$ are prime numbers. I have to calculate the $a,b,p,q$, possibly using computer for some calculations, but the method is supposed to be symbolically ...
2
votes
4answers
193 views

recursion need a closed form

Is there a closed formula to the problem $f(1)=1, f(2n)=f(n), f(2n+1)=f(2n)+1$. So far i have found a solution for $n$, which is the number of power of $2$'s needed to add up to the number starting ...
1
vote
6answers
118 views

The function $G: x \mapsto 2^{x^2}$ maps $\mathbb{R}$ onto $\{ x \in \mathbb{R} : x \geq 1 \}$

Let $X = \mathbb{R}$ and $Y = \{x \in \mathbb{R} :x ≥ 1\}$, and define $G : X → Y$ by $$G(x) = e^{x^2}.$$ Prove that $G$ is onto. Is this going along the right path and if so how do get the ...
1
vote
1answer
48 views

Is this quantifier is true?

"Every mail message larger than one megabyte will be compressed". Let $M(x) = x$ mail message $L(x) = x$ larger than one megabyte will be compressed $ \forall x \space (M(x) \rightarrow L(x))$
1
vote
1answer
136 views

Prove this equality by using Newton's Binomial Theorem

Let $ n \ge 1 $ be an integer. Use newton's Binomial Theorem to argue that $$36^n -26^n = \sum_{k=1}^{n}\binom{n}{k}10^k\cdot26^{n-k}$$ I do not know how to make the LHS = RHS. I have tried ...
1
vote
1answer
39 views

Is Proof by Resolution really needed here?

So I'm doing a problem in the book but this problem (where they ask me to use proof by resolution) seems unnecessary: $p\iff r$ $r$ $\therefore p$ By definition of IFF, this seems true, but they ...
1
vote
4answers
71 views

Prove by induction that $n < 2^n$ for all $n \ge 1$

I'm trying to do homework problems and for the most part I've been getting the results. For this one though, I am having some trouble since its $2^n$ and I can't relate it properly: Prove using ...
1
vote
2answers
87 views

Finding a formula for $1+\sum_{j=1}^n(j!)\cdot j$ using induction

I need help with finding the formula and proving it by induction. Am stuck, but the professor says we should know this by now.
1
vote
2answers
80 views

Proving that a function from $N\times N$ to $N$ is bijective.

I am stuck on this problem: Define $f: N\times N \rightarrow N$ by $f(i,j)=\frac{(i+j-1)(i+j-2)}{2}+i$. How do you prove that $f$ is a bijection thus $N\times N$ and $N$ are numerically ...
1
vote
3answers
148 views

Draw a finite state machine which will accept the regular expression $(a^2)^* + (b^3)^*$

Draw a finite state machine which will accept the regular expression: $(a^2)^* + (b^3)^*$ In particular, I am confused by the $+$ sign, what does it exactly mean? Most literature I could find about ...
1
vote
4answers
495 views

proof by induction: sum of binomial coefficients $\sum_{k=0}^n (^n_k) = 2^n$

Question: Prove that the sum of the binomial coefficients for the nth power of $(x + y)$ is $2^n$. i.e. the sum of the numbers in the $(n + 1)^{st}$ row of Pascal’s Triangle is $2^n$ i.e. prove ...
1
vote
1answer
44 views

Question over induction, suppose $P(n)$ is true for all positive integers $n$ that is a power of 2.

Suppose, that $P(k+1) \Rightarrow P(k)$ for all positive integers $k$. How would I prove $P(n)$ is true? I am getting confused since this is going the 'other way'. Usually $P(k)\Rightarrow P(k+1)$
1
vote
1answer
106 views

Discrete Math- Four different dice are rolled

Four different dice are rolled. a) In how many outcomes will at least one five appear? b) In how many outcomes will the highest die be a five? I think i figured out the answer for how many outcomes ...
1
vote
1answer
109 views

Different arrangements of the word PHILOSOPHY

I want to figure out the number of different arrangements using all the letters in PHILOSOPHY such that the letters H,I,S,Y always stick together. The way I solved this is given below ; Selecting a H ...
1
vote
1answer
96 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
2answers
373 views

How to prove a total order has a unique minimal element

Let $R$ be a total order on set $S$. Prove that if $S$ has a minimal element, than the minimum element is unique. I have difficulties with proofs. I know any graph of a total order is a straight ...
1
vote
1answer
99 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
160 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
60 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
218 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
889 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
219 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
92 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
342 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
79 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
205 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
369 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
250 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
146 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
718 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
91 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
295 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
729 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
445 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
436 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
39 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
152 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
33 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
53 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
62 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
65 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
41 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
171 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
34 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 .