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

4
votes
1answer
315 views

Showing that a root $x_0$ of a polynomial is bounded by $|x_0|<(n+1)\cdot c_{\rm max}/c_1$

I have doubts about the following problem (Problem 3.21 from Sipser's "Introduction to the Theory of Computation"): Let $c_1 x^n + c_2 x^{n-1} + \cdots + c_n x + c_{n+1}$ be a polynomial with a ...
4
votes
2answers
1k views

Derangement problem!

Is the solution of the problem, in how many ways can the digits $$0, 1, 2, 3, 4, 5, 6, 7, 8, 9$$ be arranged so that no even digit is in its original position, is $5!D_5$. Where $D_n$ = $n! \left( ...
4
votes
5answers
2k views

Equivalence relation $(a,b) R (c,d) \Leftrightarrow a + d = b + c$

Suppose $A$ is the set composed of all ordered pairs of positive integers. Let $R$ be the relation defined on $A$ where $(a,b) R (c,d)$ means that $a + d = b + c$. (a) Prove that $R$ is an ...
4
votes
3answers
890 views

Definition of a countable set

What is the proper definition of a Countable Set?
3
votes
2answers
71 views

Need a counter example for cycle in a graph

Could anyone give a counter example for that theorem : A graph G has exactly one vertex of degree $1$, then it contains a cycle. I am so confused. I wonder that may I give a counter example ...
3
votes
3answers
116 views

Proof verification for proving $\forall n \ge 2, 1 + \frac1{2^2} + \frac1{3^2} + \cdots + \frac1{n^2} < 2 − \frac1n$ by induction

Prove by mathematical induction: $\forall n \ge 2, 1 + \frac1{2^2} + \frac1{3^2} + \cdots + \frac1{n^2} < 2 − \frac1n$ Basis Step: (We want to show, $P(2)$, which is 1 + ...
3
votes
1answer
97 views

The number of regions into which a plane is divided by n lines in generic position [duplicate]

Suppose that $n$ lines are drawn on a plane in such a way that no lines are parallel and no three of them intersect at a point. Let $r(n)$ be the number of regions the plane is divided into after ...
3
votes
1answer
367 views

The product of any three consecutive natural numbers is divisible by 9.prove or find a counterexample

can anyone give me feedback on my solution false counterexample: n(n+1)(n+2) let n= 1 1(2)(3) =6 is not divisible by 9 is this correct?
3
votes
2answers
3k views

Linear Homogeneous Recurrence Relations and Inhomogenous Recurrence Relations

I'm having some difficulty understanding 'Linear Homogeneous Recurrence Relations' and 'Inhomogeneous Recurrence Relations', the notes that we've been given in our discrete mathematics class seem to ...
3
votes
2answers
177 views

Pigeon hole principle with sum of 5 integers

Prove that from 17 different integers you can always choose 5 so the sum will be divisible by 5. I tried with positive,negative numbers. Even, odd numbers etc but can't find the solution. Any ...
3
votes
2answers
61 views

Number of permutations of a word taking four at a time

Take the letters $NNAAARRGGTTSE$. I have written my answer below to find out the number of permutations of four letters chosen from the given set of letters. 3 of the same kind and 1 other = $\left( ...
3
votes
2answers
150 views

to clear doubt about basic definition in graph theory

Can anybody help me in clearing the doubt about hierarchical product of graphs. Its quite different from other graph products. Here is the screenshot and link how it is done. I know the rooted graph, ...
3
votes
1answer
1k views

Is there a formula for finding the number of nonisomorphic simple graphs that have n nodes?

As my subject line asks, is there a formula for finding the number of nonisomorphic simple graphs there are with n nodes, outside of trial, error, and enumeration over max degrees of vertices? Thanks ...
3
votes
1answer
149 views

finding the minimal property of a graph

While working out on a problem, I found that cycles $C_n$ are minimally self-centered graphs, as if we remove any edge then it is paths $P_n$ and $P_n$ are not self-centered graphs. My question is ...
3
votes
3answers
217 views

Gerrymandering urns (redux)

This is a rehash of this question (and probably the intent of this, and several other similar questions), but I'd like: a more detailed answer that builds from the simplest cases to potentially ...
2
votes
9answers
137 views

If $n\ge2$, Prove $\binom{2n}{3}$ is even.

Any help would be appreciated. I can see it's true from pascal's triangle, and I've tried messing around with pascal's identity and the binomial theorem to prove it, but I'm just not making any ...
2
votes
2answers
73 views

Prove that if an average of a thousand numbers is less than 7, then at least one of the numbers being averaged is less than 7 [closed]

I tried proving this by contraposition, by saying, "If every number that is being averaged is greater than 7, then the average of a thousand numbers is less than 7." This seems easier to prove, but I ...
2
votes
2answers
550 views

If $x \in\mathbb{Z}$ has the property that for all $m \in\mathbb Z$, $mx = m$, then $x = 1$

I am learning proofs, and I am stuck with this proposition: Let $x \in\mathbb{Z}$. If $x$ has the property that for all $m \in\mathbb Z$, $mx = m$, then $x = 1$. I want to use the additive ...
2
votes
4answers
78 views

Clarifying on how if p,q is logically equivalent to p only if q [duplicate]

Here is what my book says about the different ways implications are worded I am struggling with how "if p, then q" is logically equivalent to "p only if q" The example I came up with With "if ...
2
votes
2answers
41 views

Next step to take to reach the contradiction?

This problem is from Discrete Math and its Applications I am trying to use proof by contradiction to do this problem, proof by contradiction as described by the book Here is my work so far for ...
2
votes
1answer
77 views

Asymptotic Function proof?

I am doing questions from past exams and I stumbled upon this one. I have no idea how to go about solving it.I never had any logarithmic functions in my previous bigOh proofs nor have I had to use ...
2
votes
1answer
68 views

Express $\forall n \in \mathbb N$, $\exists m \in \mathbb N$, $n^4 = m^2$ in words without using the symbol $\mathbb N$

Express $\forall n \in \mathbb N$, $\exists m \in \mathbb N$, $n^4 = m^2$ in words without using the symbol $\mathbb N$. My Solution: For all $n$ that is an element of Natural number there is ...
2
votes
1answer
253 views

Pigeonhole Principle

Let $X = {x_0, x_1, · · · , x_m}$ be a subset of ${1, 2, · · · , n}$, where $m > n/2$, and $x_0$ is the smallest number in $X$. Use the pigeonhole principle to show that $X$ contains two numbers ...
2
votes
2answers
149 views

At a party $n$ people toss their hats into a pile in a closet.$\dots$ [duplicate]

Question: At a party $n$ people toss their hats into a pile in a closet. The hats are mixed up, and each person selects one at random. What is the expected number of people who select their own hats? ...
2
votes
1answer
108 views

Fibonacci proof by induction

I have fibonacci numbers defined as such: $$ f(n) = f(n-1) + f(n-2)$$with$$ f(0) = 0 $$$$f(1) = 1$$ I have to prove that $$ F(n) \geq 1.5^{n-1}, n \geq 6$$ Base Case: $$ f(6) = 8 \geq (1.5)^5 ...
2
votes
1answer
45 views

Need help with Proof by Strong Induction question

So, here is the question: For any position integer $n$, let $T(n)$ be the number 1 if $n<4$ and the number $T(n-1) + T(n-2) + T(n-3)$ if $n \geq 4$. We have $T(1)=1, T(2)=2, T(3)=3$ ...
2
votes
2answers
209 views

Infinite Sum with Combination

I am trying to figure out what the following sum converges to: $$\sum_{n=0}^\infty {6+n\choose n}x^n(6+n),\qquad\qquad0<x<1$$ An answer would be great, but if you have an explanation, that'd ...
2
votes
4answers
190 views

For the Fibonacci sequence prove that $\sum_{i=1}^n F_i= F_{n+2} - 1$

For the Fibonacci sequence $F_1=F_2=1$, $F_{n+2}=F_n+F_{n+1}$, prove that $$\sum_{i=1}^n F_i= F_{n+2} - 1$$ for $n\ge 1$. I don't quite know how to approach this problem. Can someone help and ...
2
votes
2answers
185 views

Proving a recurrence relation for strings of characters containing an even number of $a$'s

We consider strings of $n$ characters, each character being $a$, $b$, $c$, or $d$, that contain an even number of $a$'s. (Recall that $0$ is even.) Let $E_n$ be the number of such strings. ...
2
votes
1answer
75 views

Bijective function proof in $R\times R$ and $Z\times N$

How can I verify if these functions are bijective? $ f_4:\Bbb{R^2} \rightarrow \Bbb{R^2}, \ (x,\ y)\mapsto (x+y,\ x-y)$ $ f_5:\Bbb{Z} \times \Bbb{N^*} \rightarrow \Bbb Q, \ (p,\ q)\mapsto p + ...
2
votes
4answers
128 views

Fibonacci sequence proof

Prove the following: $$f_3+f_6+...f_{3n}= \frac 12(f_{3n+2}-1) \\ $$ For $n \ge 2$ Well I got the basis out of the way, so now I need to use induction: So that $P(k) \rightarrow P(k+1)$ for some ...
2
votes
1answer
112 views

Solve $x^2$ $mod$ $23 = 7^2$

What is the procedure to solving $x^2$ $mod$ $23 = 7^2$? According to WolframAlpha, there is no integer solution but I am completely confused as to what steps was taken to determine that. Before ...
2
votes
1answer
92 views

Planar Realization of a Graph in Three-Space

We call a planar graph one that we can draw in two-space such that no two edges intersect. I was told that we're not so interested in drawing graphs in three-space, because it is "intuitively obvious" ...
2
votes
3answers
330 views

Demonstrate that if $f$ is surjective then $X = f(f^{-1}(X))$

I haven't been able to do this exercise: Let $f: A \rightarrow B$ be any function. $f^{-1}(X)$ is the inverse image of $X$. Demonstrate that if $f$ is surjective then $X = f(f^{-1}(X))$ where $X ...
2
votes
1answer
137 views

pigeonhole principle divisibility proof

Let n be some positive odd number, prove that there exists some positive integer k such that n|(2k-1), prove in terms of the pigeonhole principle
2
votes
1answer
162 views

Possible ways to walk to school

I am not sure how to approach this problem. Every day, a dance student walks from her home to dance-school, which is located $12$ blocks east and $16$ blocks north from home. She always takes the ...
2
votes
2answers
220 views

Parity function proofing for every n>=1 using only AND, OR, 0, and 1

Consider the parity function: $F_n$($x_1$, $...$ ,$x_n$) $=$ $\oplus_{i=1}^n$$x_i$ where each $x_i$ is boolean. Prove that, for every $n \ge 1$, there is no way to compute $F_n$ using only ...
2
votes
4answers
1k views

How to find a closed form solution to a recurrence of the following form?

I need to find the closed form solution to the following recurrence -: $ T(n) = 8*T(n/2) + 0.25*n^2$ with $T(1) = 1$ and $n=2^j$ and this is what I have tried so far but just can't seem to get a ...
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
654 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
4answers
841 views

Proving that for any sets $A,B,C$, and $D$, if $(A\times B)\cap (C\times D)=\emptyset $, then $A \cap C = \emptyset $ or $B \cap D = \emptyset $

I'm trying to prove that for any sets $A$, $B$, $C$, and $D$, if the Cartesian product of $A$ and $B$ is disjoint with the Cartesian product of $C$ and $D$, then either $A$ and $C$ are disjoint or $B$ ...
2
votes
1answer
469 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
3answers
467 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 ...
2
votes
3answers
202 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
1answer
18 views

One hypothesis concerning Hamming distance matrix

Suppose $a_1, a_2, \ldots, a_m$ are different strings of the same length n. And let $V = [v_1, v_2, \ldots, v_n]$ be a matrix such that $V_{i, j}$ is a Hamming distance between $a_i$ and $a_j$. ...
1
vote
1answer
22 views

Proof of cardinalities sets

Prove that the cardinality of set $A^{B+C}$ is equal to the cardinality of $A^{B}\times A^{C}$. I think I need to make functions from $B+C$ to $A$ and one from $B$ to $A$ and one from $A$ to $C$. I ...
1
vote
1answer
84 views

how to solve generating function for odd number?

im working on this question and i don't know where to start the question is: a) Find a closed form for the generating function $c(x)$ for counting compositions with $k$ parts, where each part is ...
1
vote
6answers
122 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
49 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))$