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

6
votes
2answers
489 views

Distribution of points on a rectangle

Let $R$ be a rectangular region with sides $3$ and $4$. It is easy to show that for any $7$ points on $R$, there exists at least $2$ of them, namely $\{A,B\}$, with $d(A,B)\leq \sqrt{5}$. Just divide ...
5
votes
8answers
160 views

Prove with induction that $11$ divides $10^{2n}-1$ for all natural numbers.

$$10^{2(k+1)}-1 = 10^{2k+2}-1=10^{2k}\cdot10^{2}-1$$ I feel like there's something in that last part that should make it work, but I can't grasp it. Am I missing something obvious? Am I going in the ...
5
votes
1answer
176 views

Strange Recurrence: What is it asymptotic to?

So I have the following recurrence relation for the growth rate of an algorithm: $T(n)$ = time taken by algorithm to solve problem of size n: $$T(n) = T(n-1) + T(\lceil(n/2)\rceil)$$ Clearly this ...
5
votes
3answers
291 views

Help with Cartesian product subsets [duplicate]

I want to prove that if $A \subseteq C\,$ and $\,B \subseteq D,\,$ then $\,A \times B \subseteq C \times D.$ I know that $A \subseteq C \iff a \in A \rightarrow a \in C$ and that $B\subseteq D\iff ...
5
votes
3answers
304 views

Generating Functions- Closed form of a sequence

We are given the following generating function : $$G(x)=\frac{x}{1+x+x^2}$$ The question is to provide a closed formula for the sequence it determines. I have no idea where to start. The denominator ...
4
votes
2answers
86 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 ...
4
votes
2answers
105 views

Counting tilings of a $2\times n$ board

Let $n=>1$ be an integer and consider a $2*n$ board $B_n$ consisting of $2n$ cells,each one having sides of length one. This picture shows $B_{13}$: For $n=>1$, let $a_n$ be the number of ...
4
votes
3answers
2k views

Recurrence relation for number of bit strings of length n that contain two consecutive 1s

I'm pulling my hair out over a review question for my final tomorrow. Find a recurrence relation (and its initial conditions) for the number of bit strings of length n that contain two consecutive ...
4
votes
2answers
141 views

Prove that $\sim$ defines an equivalence relation on $\mathbb{Z}$.

For $a,b \in \mathbb{R}$ define $a \sim b$ if $a - b \in \mathbb{Z}$ I don't understand how I'm suppose to prove this: Prove that $\sim$ defines an equivalence relation on $\mathbb{Z}$ Also can you ...
4
votes
2answers
117 views

Prove $m=3k+1 \quad m,k \in \mathbb Z \implies m^2=3l+1 \quad m,l \in \mathbb Z$

Suppose we call an integer "throdd" $\iff$ $m=3k+1$ for some integer $k$. Prove that the square of any throdd integer is throdd. So here is what I have so far: $$(3k+1)^2 = 3k+1$$ ...
4
votes
1answer
322 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
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 ...
4
votes
2answers
2k 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
3k 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
926 views

Definition of a countable set

What is the proper definition of a Countable Set?
3
votes
1answer
37 views

a Maximum of Discrete Function

Define a set $$X=\{(x_1,\ldots ,x_n)\mid x_i=\pm 1,1\leq i\leq n\}$$ Fix $a$, $b\in X$. Consider the discrete function $$F(x_1,\ldots,x_n)=(x_1a_1+\cdots+x_na_n)^2+(x_1b_1+\cdots+x_nb_n)^2$$ ...
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
109 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
378 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
4k 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
190 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
62 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
156 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
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
221 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
138 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
78 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
554 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
81 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
42 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
78 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
263 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
161 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
116 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
47 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
228 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
201 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
192 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
113 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
93 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
355 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
171 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
661 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
2k 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 ...