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

0
votes
3answers
104 views

Compute equivalence classes of equivalence relation

I have already proven that the relation $R=\{(x,y) \in \mathbb Z \times \mathbb Z \mid x+y\text{ is even}\}$ is an equivalence relation by showing reflexive, symmetric, and transitive properties of ...
2
votes
2answers
60 views

Strong Induction to prove $T(n)$ is $O(n)$ for $T(n) = T(\lfloor n/3 \rfloor) + T(\lfloor n/5 \rfloor) + T(\lfloor n/7 \rfloor) + n$

I have some questions about Strong Induction where the inductive procedure isn't entirely clear to me. I will use a specific example to demonstrate and present my attempt at a proof with questions ...
2
votes
2answers
122 views

Prove that rational numbers $a,b$ are integers if $a+b$ and $ab$ are integers

I have been trying to prove this via divisibility, assuming that $a=\frac{n}{m}$ and $b=\frac{r}{q}$ for some $n,m,r,q$ in Ints($m$,$q$ not $0$), but I'm completely stuck here. Any help?
4
votes
1answer
60 views

Arranging the letters of INCONVENIENCE so that no C is adjacent to an N

As the title indicates, I would like to find the number of ways to arrange the letters of INCONVENIENCE so that no C is adjacent to an N. This is a problem I just made up, and I am interested in ...
1
vote
2answers
135 views

Find k integers that can make up all integers below N.

For given $N$, what is the smallest $k$ so that we can find $k$ natural numbers satisfiying some of these $k$ numbers can add up to any $i$ for $1\leq i\leq N$. Moreover, how to find all possible $k$ ...
0
votes
0answers
37 views

recursive definitions using sequences

lets say I have 2 sequences $$a_0, a_1,\ldots, a_n,\ldots$$ and $$b_0, b_1,\ldots, b_n,\ldots$$ where $$a_k \text{ and } b_k$$ are defined as: $$ a_n = \sum_{k=0}^n {n+k \choose 2k}, \quad \quad n\...
-2
votes
2answers
140 views

general formula using informal inductive reasoning

if I have 4 equations.. $$ 1=1$$ $$2+3+4=1+8$$ $$5+6+7+8+9=8+27$$ $$10+11+12+13+14+15+16=27+64$$ how do I find the general formula (that is suggested by the equations) using informal inductive ...
-1
votes
4answers
109 views

For all integers $x$ and $y$, if $ x^3 + x = y^3 + y$ then $x = y$. [duplicate]

For all integers $x$ and $y$, if $x^3 + x = y^3 + y$ then $x = y$. This is what I have done so far: Proof: Suppose $x$ and $y$ are arbitrary integers. We know that $x^3 + x = y^3 + y$, we want to ...
2
votes
4answers
269 views

Proof - for all integers $y$, there is integer $x$ so that $x^3 + x = y$

For all integers $y$, there is an integer $x$ so that $$x^3 + x = y.$$ This is what I have done so far: Proof: Suppose $y$ is some integer. We want to prove that $$x^3 + x = y$$ for some integer $x$....
-6
votes
1answer
52 views

Proof - a | b and b | a then a = b [closed]

For all integers a and b, if a | b and b | a, a = b. Can something think of a proof? I have done this: Proof: Suppose m and n are integers such that m|n and n|m, but n ≠ m. Let m = 1 and n = -1 ...
2
votes
0answers
94 views

Gradient of Probability Distribution

Given a random walk on a lattice $L$ (not necessarily centered - we allow $E[X_i] \neq 0$ for the i.i.d. increments $X_i$), let $p_t(x)$ denote the probability measure of state $x \in L$ after $t$ ...
1
vote
2answers
53 views

Simple proof by contradiction

I feel like I'm almost there, but I don't know what to right after this: for all real number $x$, if $x^2-2x\neq-1$, then $x\neq-1$. Let $p(x)$ be $x^2-2x\neq-1$ Let $q(x)$ be $x\neq-1$, My ...
1
vote
1answer
113 views

Counting switching functions

By using 16 bit binary in BCD , how many switching functions can exist ? Now , since this is BCD anything above 1001 is invalid. Considering 16 bits : 1001 1001 1001 1001 Above is number of possible ...
0
votes
1answer
331 views

Constructive Induction to derive and prove the formula for a geometric sequence

$\sum_{i=1}^nr^i = a \cdot (b^n) + c$ Base Case: n=1, this holds Inductive Hypothesis: Assume for $n = k$, $k \ge 1$ that $\sum_{i=1}^k r^i = a * (b^k) + c$. Inductive Step: Prove for $n = k+1$ ...
-2
votes
1answer
60 views

model Coin toss probability [closed]

Model the probability of tossing any sequence of 8 heads and tails as equally likely. Take the sample space to be the set of the 256 possible sequences. What is the probability of the event that the ...
2
votes
2answers
116 views

tuple of integers

The integers 1,2,...,30 are invited to a dinner party. They all sit around a round table, in some unknown order. Does there exist an ordering in which there are no three successive (successive means ...
1
vote
1answer
959 views

How to prove generalized DeMorgan's Law? [duplicate]

How to prove generalized DeMorgan's Law that $$\neg(A_1 \land A_2 \land \cdots \land A_n) = \neg A_1 \lor \neg A_2 \lor \cdots \lor \neg A_n.$$ Or in the set theory language, $$\Bigg(\bigcap_{i\in I}...
0
votes
2answers
85 views

How does $( 1 - (1- \frac{1}{2^{2^k}}))$ become $(1+ \frac{1}{2^{2^k}})$?

How does $\left( 1 - \left(1- \frac{1}{2^{2^k}}\right)\right)$ become $\left(1+ \frac{1}{2^{2^k}}\right)$? I distributed the former but got negative $-\frac{1}{2^{2^k}}$. So it does not match the ...
1
vote
2answers
48 views

How do I write $2(2^k+1) - 1$ as $(2 \cdot 2^k + 1)$?

How do I write $2(2^k+1) - 1$ as $(2 \cdot 2^k + 1)$? Mathematically, it is equivalent. But I need to the former form into the latter form for step 2 of inductive step for mathematical induction ...
2
votes
1answer
91 views

Is there a general rule for how to pick the base case value for proofs by mathematical induction?

I was looking at how to do mathematical induction. One source said to use $n = 1$ for the basis step. But I have seen other sources choose the value $n = 0$. So the question is as follows: ...
6
votes
4answers
631 views

“If A then B” in Venn (or Euler) Diagrams

How can I represent "If A then B" in a diagram? I thought it would be a simple subset like $A ⊂ B$. However this material says that If $A$ then $B$ $=$ $A^c ∪ B$. Now I am confused.
2
votes
1answer
138 views

Algorithm for generating restricted integer composition of N in k parts from interval [a,b] given the lexicographic number.

Consider the restricted compositions of $6$ in four parts from integers $\{1, 2, 3\}$. ...
2
votes
1answer
40 views

A construction of a Hadamard matrix

Let $H_n$ be a $2^n \times 2^n$ matrix indexed by all subsets of $[n] = \{1,\ldots,n\}$ and let the entry at the intersection of the row and column indexed by the sets $X$ and $Y$ be $$(-1)^{ |X \cap ...
1
vote
1answer
61 views

Number of bit strings

How many bit string of lenght 28 having at least one consecutive 000? without consecutive 000? I'm using ti nspire, can i do it with nCr function. I tried to do it but i did not found a way. ...
1
vote
0answers
39 views

Predicate logic a game where player goes first?

What kind of predicate logic statement describes a game that the person who goes first can always win? Write you answer in terms of successive moves by two players. I am lost here I tried initially ...
2
votes
1answer
101 views

Finding the number of ways to pick ${n}$ marbles from a jar

Problem: А jar contains 8 blue marbles, 6 green marbles, and 4 red marbles. Five marbles are selected at random, all at once. In how many ways can: A.) two red and three blue marbles be obtained? ...
3
votes
7answers
478 views

Grasping the concept of equivalence classes more concretely

I have read about equivalence classes a lot but unable to understand exactly what they are. I know about equivalence relations, but I am having a hard time understanding what equivalence classes are ...
2
votes
1answer
127 views

Combinatorics: How many ways are there to distribute zero to thirteen distinct cards to four distinct players?

Other ways to word the question so that it's clear: In a game where players hold a maximum of thirteen cards and a minimum of zero cards, how many possible positions are there? How many possible ...
0
votes
1answer
20 views

Proofs for certain ways of decomposing permutations as products of transpositions

I know $(1 2 3 4 5) = (15)(14)(13)(12)$. But I just discovered $(12345) = (12)(23)(34)(45)$ and $(12345) = (54)(52)(21)(25)(23)(13)$. Also, $(15) = (21)(32)(43)(54)(43)(32)(21)$. Excepting the ...
0
votes
1answer
114 views

A puzzle about choosing one of 9 doors with signs on them

This problem involves logic-based math, I tried making truth tables for this problem but I don't think you can because there are 9 doors! Below is what I came up with but I want to know if there is a ...
4
votes
2answers
78 views

Finding the number of ways of picking three cards

Problem: An urn has 10 red cards numbered 1 through 10 and 8 blue cards numbered 1 through 8. Three cards are randomly drawn, one at a time, without replacement. Find the number of ways to obtain:...
3
votes
2answers
105 views

Finding how many bits of length n there are

So we are starting on the section of combinatorics in my discrete math class and our instructor gave us a simple problem to see if we understood what we learned that day. The problem consists of three ...
1
vote
1answer
22 views

Questions about terminology (transpositions)

A cycle with only two elements is called a transposition. For example, the permutation of $\{1, 2, 3, 4\}$ that sends $1$ to $1$, $2$ to $4$, $3$ to $3$ and $4$ to $2$ is a transposition (specifically,...
1
vote
1answer
51 views

Nearly-unit-distance graph (UDG) density

Q1. How dense can a nearly-unit-distance graph be? Let points sit in $\mathbb{R}^2$. A unit-distance graph UDG "connect[s] two points by an edge whenever the distance between the two points is ...
6
votes
0answers
155 views

Balanced, center-free set. [closed]

We say that a finite set $\mathcal{S}$ of points in the plane is balanced if, for any two different points $A$ and $B$ in $\mathcal{S}$, there is a point $C$ in $\mathcal{S}$ such that $AC=BC$. We say ...
0
votes
1answer
250 views

proof of real number between two real numbers

I need to prove that for any two real numbers that are not equal, you can find a real number between them. I have tried to add two random numbers together and show that it produces a real number.
1
vote
0answers
107 views

Continuous and Discrete summation

I have a continuous curve $f(x)$ say constant in interval $0$ to $P$ and area under the curve is unity. Alternately, $f(x) = 1/P$ for $ 0\le x \le P$. So I can calculate $G = \int_{0}^P f(x)sin(...
0
votes
1answer
63 views

Permuting letters within three-letter substrings of strings over $\{\mathsf{x},\mathsf{y},\mathsf{z}\}$ to yield a target “cyclic string”

Given a string made up of only letters $\mathsf{x}$, $\mathsf{y}$ and $\mathsf{z}$, we need to determine whether it can be changed into a string such that each three-letter substring of the string is ...
0
votes
2answers
80 views

problem related to pigeon hole principle

please help me to solve this using pigeon hole principle Suppose that S is a set of n integers. Show that one can choose a nonempty subset T of S such that the sum of all elements of T is divisible ...
4
votes
3answers
68 views

Interchanging order of summation mechanically

How can I interchange order of summation mechanically, without thinking? For instance, I had to interchange the sums below (assume $i$ is a constant where $i\gt 0$). $$\sum_{n\ge 1}\sum_{i\lt k \lt n}...
4
votes
6answers
320 views

Show that if n+1 integers are choosen from set $\{1,2,3,…,2n\}$ ,then there are always two which differ by 1

Considering n=5 i have $\{1,2,3,...,10\}$ .Making pairs such as $\{1,2\}$ ,$\{2,3\}$ ... total of $9$ pairs which are my holes and $6$ numbers are to be choosen which are pigeons .So one hole must ...
0
votes
1answer
64 views

Comparing 2 Big-O expressions

I have to solve the following problem: "Al and Bob are arguing about their algorithms. Al claims his $O(n*logn)-$ $time$ $method$ is always faster than Bob’s $O(n^2)-$ $time$ $method$. To settle the ...
1
vote
1answer
47 views

Confused about a quality of Existential Generalization and Instantiation

Let me preface the question with a "proof" $1. \exists yP(y) \quad Premise \\ 2. P(B) \quad \quad 1,E.I. \\ 3. \exists xP(x) \quad 2,E.G. $ However, I am not sure if it is to "safe" to say that ...
1
vote
1answer
36 views

Help explicit formula for a sequence

what would the explicit formula be for the sequence 0, -1/2, 2/3, -3/4, 4/5, -5/6, 6/7? I am having trouble locating a similar pattern between each term.
1
vote
5answers
93 views

If $n = 4k + 1$, does $4$ divide $n^2 -1$?

How would I show that $4$ divides $n^2 -1$ if $n = 4k+1$? Is there more than one way to solve this?
0
votes
1answer
24 views

Help with recurrence relation and interest rates

how would I create a recurrence relation for the amount of money in a saving account after $n$ months $a_n$ , if the interest rate is $.5\%$ interest per month and initially the account has $\$1000$? ...
1
vote
6answers
80 views

If $n$ is an integer then $n^2$ is the same as $0$ or $1\pmod 4$? [duplicate]

I have been stuck on this problem for awhile. How would i go about solving it, an explanation would be helpful as well. Show that if $n$ is an integer then $n^2 \equiv 0$ or $1 \pmod 4$?
0
votes
0answers
35 views

Recursive Algorithm proof by inductive hypothesis

For the program mean(A,n) if n = 1 then return A[n] else return A[n]/n+mean(A,n-1)*(n-1)/n end Show that if the recursive call to mean (A, n-1) ...
1
vote
1answer
73 views

$f : A \to B$ s.t. for all $x, y \in A, x R y \iff f(x) S f(y)$

Theorem. A relation $R$ on a set $A$ is reflexive and transitive if and only if there is a set $B$ with a partial order $S$ and a function $f : A \to B$ such that for all $x, y \in A, x R y \iff f(x)...
0
votes
0answers
51 views

Graduate schools that do not require letters of recommendation

I am applying for PhD in Mathematics. I have been surfing the internet to find grad schools that do not require letters of recommendation. Can anyone help me with suggestions on some schools I could ...