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

5
votes
1answer
106 views

All $k$-regular subgraphs of $K_{n,n}$ have a perfect matching: a proof without Hall's Marriage Theorem?

There are several ways of describing this result: Theorem: For $k \in \{1,2,\ldots,n\}$, any $k$-regular subgraph of $K_{n,n}$ has a perfect matching (also known as a $1$-factor). I tend to ...
5
votes
4answers
855 views

Help with combinatorial proof of binomial identity: $\sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2{2n-2\choose n-1}$

Consider the following identity: \begin{equation} \sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2{2n-2\choose n-1} \end{equation} Consider the set $S$ of size $2n-2$. We partition $S$ into two sets $A$ ...
4
votes
1answer
193 views

How does one prove that $\frac{1}{2}\cdot\frac{3}{4}\cdots \frac{2n-1}{2n}\leq \frac{1}{\sqrt{3n+1}}?$

I would like to show that $\frac{1}{2}\cdot\frac{3}{4}\cdots \frac{2n-1}{2n}\leq \frac{1}{\sqrt{3n+1}}$ holds for all natural numbers. I got stuck here: $\frac{1}{2}\cdot\frac{3}{4}\cdots \frac{2n-1}{...
4
votes
1answer
416 views

Efficiently evaluating the Motzkin numbers

So I made an error on the question here: $T_N = 1 + \sum_{k=0}^{N-2}{(N-1-k)T_k}$ The correct formula I'm trying to solve is more complicated and as follows: $$T_0 = T_1 = 1 $$ $$T_{N+1} = T_N + \...
4
votes
2answers
7k views

Free resources to start learning Discrete Mathematics

Can anyone recommend good, free online articles or books to learn Discrete mathematics? When I google'd for them, I came across few resources..but don't know whether they are good to start learning ...
4
votes
2answers
257 views

Counting the numbers with certain sum of digits.

The question : In how many different numbers between $1$ and $100000000$ have the sum of their digits equal to $45$? I'm thinking about using the stars and bars formula but I'm not sure if it's ...
4
votes
3answers
375 views

Are these two predicate statements equivalent or not?

$\exists x \forall y P(x,y) \equiv \forall y \exists x P(x,y)$ I was told they were not, but I don't see how it can be true.
4
votes
2answers
185 views

If $n$ is squarefree, $k\ge 2$, then $\exists f\in\Bbb Z[x_1,\dots,x_k] : f(\overline x)\equiv 0\pmod n\iff \overline x\equiv \overline 0\pmod n$

Starting from this question, we set $n=k=2$ and use the function $f\in\Bbb Z[x,y]$ where $f(x,y)=x\cdot y+x+y$, then the proofs applied to that question satisfy this case. Note that for $k=1$ the ...
4
votes
3answers
3k views

Trees whose complement is also a tree

I am searching for those graphs $G$ where $G$ is a tree and its complement is also a tree. I came out with one such graph $P_4$. Are there any other too? I am not getting any other example. thanks
3
votes
3answers
475 views

Coloring dots in a circle with no two consecutive dots being the same color

I ran into this question, it is not homework. :) I have a simple circle with $n$ dots, $n\geqslant 3$. the dots are numbered from $1\ldots n$. Each dot needs to be coloured red, blue or green. No ...
3
votes
3answers
643 views

$x+1/x$ an integer implies $x^n+1/x^n$ an integer

Suppose that $0\neq x\in\mathbb{R}$ and $x + \frac1x\in\mathbb{Z}$. Prove that, for all $n\ge1$, $x^n + \frac1{x^n}\in\mathbb{Z}$. I can't figure out and understand the question. Can you give me ...
3
votes
2answers
251 views

Choosing $15$ out of $100$ whole numbers with difference of any $2$ divisible by $7$

How can we prove with the pigeonhole principle that having $100$ whole numbers, one can choose $15$ of them so that the difference of any $2$ is divisible by $7$?
3
votes
1answer
88 views

Calulating the Ramsey number $R(T, K_{1,n})$ of a tree $T$ and bipartite graph $K_{1,n}$

Let $m,n \ge 2$ be such that $m-1$ is a divisor of $n-1$. Let $T$ be a tree with $m$ vertices. Calculate the Ramsey number $R(T,K_{1,n})$. Thoughts: I'm having trouble approaching this question. I ...
3
votes
3answers
103 views

In how many ways can a $31$ member management be selected from $40$ men and $40$ women so that there is a majority of women?

Here's the question: In an organization there are $80$ people, $40$ men and $40$ women. In how many ways can we choose, from those $80$ people, a $31$ member management so that there is a ...
3
votes
2answers
89 views

Prove $\sum_{i=1}^n i! \cdot i = (n+1)! - 1$?

Prove the summation: $$\sum_{i=1}^n i! \cdot i = (n+1)! - 1$$ using induction. base case: $n=1$: \begin{align*} \sum_{i=1}^1 i! \cdot i &= (1+1)! - 1 \\ 1 &= 2 - 1 \\ 1 &= 1 \end{align*...
2
votes
3answers
733 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
204 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
6answers
115 views

Prove by induction $3+3 \cdot 5+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$

My question is: Prove by induction that $$3+3 \cdot 5+ 3 \cdot 5^2+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$$ whenever $n$ is a nonnegative integer. I'm stuck at the basis step. If I ...
2
votes
2answers
350 views

$a, b \in\Bbb N$, find all solutions to $2^a = b^2 - 5$ and prove there are no more solutions?

I am currently studying discrete mathematics at uni (in my computer science degree). We have an assignment due tomorrow, and i have been able to do most of it, but one question eludes me. I spoke to a ...
2
votes
3answers
83 views

Prove that $\frac{1}{1*3}+\frac{1}{3*5}+\frac{1}{5*7}+…+\frac{1}{(2n-1)(2n+1)}=\frac{n}{2n+1}$

Trying to prove that above stated question for $n \geq 1$. A hint given is that you should use $\frac{1}{(2k-1)(2k+1)}=\frac{1}{2}(\frac{1}{2k-1}-\frac{1}{2k+1})$. Using this, I think I reduced it to $...
2
votes
1answer
1k views

$(p \implies q) \wedge (q \implies r) \implies (p \implies r)$

Show that $(p \implies q) \wedge (q \implies r) \implies (p \implies r)$ is a tautology. I have the truth tables but cannot algebraically manipulate the language itself to prove it. What I ...
2
votes
2answers
10k views

Sum of digits and product of digits is equal (3 digit number)

My child got a question in school (grade) that is: Find biggest and smallest 3 digits number, which has sum of it's digits equal to product of those digits. Help please since I cannot explain my ...
1
vote
3answers
4k views

Let A and B be sets. Show that A is a subset of B if and only if for any set C, one has A union C is a subset of B union C.

Can you verify my proof if it is right? Let $A$ and $B$ be sets. (a) Show that $A$ is a subset of $B$ if and only if for any set $C$, one has $A$ union $C$ is a subset of $B$ union $C$. (b) Show ...
1
vote
3answers
109 views

How many positive integers $ n$ with $1 \le n \le 2500$ are prime relative to $3$ and $5$?

I am trying to understand this example from my study guide and am getting no where with it and need some help. Example: How many positive integers $n$ with $1 \le n \le 2500$ are prime relative to $3$...
1
vote
2answers
124 views

Proving a triangle with different edge colors exists in a graph.

This is again some homework translated (hopefully not too badly) from my book The graph $K_{n}$ is colored using $n$ different colors, in a way that each color is used at least once. Prove that there ...
1
vote
1answer
250 views

Functions that are sets of all function - proofs

I'm going through the book Proofs and fundamentals, by Bloch, and it doesn't include a solution manual for it's examples. It doesn't have many examples on notation and proof strategy for certain cases,...
1
vote
3answers
488 views

Proving statement - $(A \setminus B) \cup (A \setminus C) = B\Leftrightarrow A=B , C\cap B=\varnothing$

I`m trying to prove this claim and I need some advice how to continue, $$(A \setminus B) \cup (A \setminus C) = B \Leftrightarrow A=B , C\cap B=\varnothing$$ what I did is: $$(A \setminus B) \cup (A \...
1
vote
1answer
280 views

Submodularity of the product of two non-negative, monotone increasing submodular functions

I'm trying to prove the submodularity of the product of two non-negative, monotone increasing submodular functions Formally, we have $f$ and $g$ are submodular functions, that is, $f:2^{\Omega}\...
1
vote
1answer
117 views

Proving Set Operations

I'm trying to prove that if $A$ is a subset of $B$ then $A \cup B = B$, but I am having trouble trying to proves this mathematically. I know that since $A$ is a subset, then $A$ has an element $x$ ...
1
vote
2answers
943 views

Matrix exponential of a skew symmetric matrix

I have a skew symmetric matrix $$C=\left( \begin{array}{ccc} 0 & -a_3 & a_2 \\ a_3 & 0 & -a_1 \\ -a_2 & a_1 & 0 \\ \end{array} \right).$$. Question 1) How do I compute $e^{...
0
votes
1answer
545 views

Discrete Math Counting Question

I need help with one of those question where you have to count the number of ways you can place r objects into n distinct boxes kinds. I was wondering if someone could solve an example in detail. How ...
0
votes
2answers
54 views

Number of functions from n-element set to {1, 2, …, m}

I've gotten stuck at the following exercise; There are m functions from a one-element set to the set {1, 2, …, m}. How many functions are there from a two-element set to {1, 2, …, m}? From a ...
0
votes
2answers
1k views

Combinatorics: Number of subsets with cardinality k with 1 element.

Consider the set |n| = {1,2,...,n}. How many subsets does it have of cardinality k and that contain the element 1? I understand that with each element, you can either include it or not to have a ...
0
votes
1answer
44 views

strong induction postage question

Use strong Principle of induction to prove that the amount of postage greater than or equal to $30$ cents can be made using a combination of $10$ cent and $3$ cent postage this is what i have so far:...
0
votes
1answer
111 views

Properties of the greatest common divisor: $\gcd(a, b) = \gcd(a, b-a)$ and $\gcd(a, b) = \gcd(a, b \text{ mod } a)$

Prove that (a) gcd(a, b) = gcd (a, b – a) (b) Let r be the remainder if we divide b by a. Then gcd(a, b) = gcd(a, r). I solved part a like: Assume a=pcommonpa b=pcommonpb gcd (a,b) = ...
-1
votes
1answer
82 views

Number of Elements Not divisble by 3 or 5 or 7 [closed]

if A={1,2,...,600} includes all natural numbers between 1 to 600. I want to find number of elements of A that not divisible by 3 or 5 or 7? any hint or idea?
7
votes
8answers
3k views

What is an example of function $f: \Bbb{N} \to \Bbb{Z}$ that is a bijection?

Could you give me an example of function $ f \colon \mathbb N \to \mathbb Z$ that is both one-to-one and onto? Does this work: $f(n) := n \times (-1)^n$? N starts with zero.
7
votes
4answers
140 views

Inductive Proof that $k!<k^k$, for $k\geq 2$.

Call $P(k): k!<k^k$, for $k\geq 2$ Test it out with 2, and it's true ($2<4$). Assume that $P(k)$ is true for some $k\geq2$. Then show that $P(k+1)$ is true. $P(k+1): (k+1)!<(k+1)^{k+1}$ ...
6
votes
1answer
580 views

Towers of Hanoi - are there configurations of $n$ disks that are more than $2^n - 1$ moves apart?

This is an exercise from Chapter 1 of "Concrete Mathematics". It concerns the Towers of Hanoi. Are there any starting and ending configurations of $n$ disks on three pegs that are more than $2^n - ...
6
votes
2answers
774 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
3answers
344 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
1answer
183 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
446 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 ...
5
votes
8answers
191 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 ...
4
votes
2answers
152 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
1answer
2k 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
155 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
3answers
1k views

Definition of a countable set

What is the proper definition of a Countable Set?
4
votes
5answers
4k 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 ...
3
votes
3answers
242 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 ...