# Tagged Questions

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.

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 ...
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 ...
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?
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 ...
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$ ...
37 views

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 ...
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 ...
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: ...
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.
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\}$. ...
40 views

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 ...
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 ...
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 ...
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.
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?