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

1
vote
1answer
97 views

Show binomial coefficient for $x^n$ in the expansion $(1+x)^r(1+x)^s$

Show that the binomial coefficient for $x^n$ in the expansion $(1+x)^r(1+x)^s$ is $\sum_{k=0}^{n}\binom{r}{k}\binom{s}{n-k}$. I dont know how to reach that. What i see is that: ...
1
vote
4answers
607 views

Prove by induction(divisible by 9) [closed]

I dealt with this problem but I couldn't resolve. Prove by induction that $10^n+3\times4^{n+2}+5$ is divisible by $9$ for all non-negative integers $n$.
1
vote
3answers
887 views

Book on modular arithmetic

I am searching for some good book which section is devoted to modular arithmetic. I am self learner so I strongly prefer that book has exercises best with answers or solutions. I have CS background ...
1
vote
2answers
90 views

Combinatorics Question: Alphabet of $16$ letters, $8$ slots, arbitrary blanks

If I have an alphabet of $16$ characters and $8$ slots that are filled with any combination of characters (no duplicates except blanks), how do I calculate the total number of combinations? Edit for ...
1
vote
2answers
96 views

Proof - Bipartite Graphs

Let $G$ be an arbitrary, unknown graph with at least two vertices. Suppose you are given the subgraphs in the set $S = \{G - v | v \in V(G)\}$, but the vertices in the subgraphs are not labeled, and ...
1
vote
3answers
107 views

Applying Fermat's Little Theorem: $6^{1987}$ divided by $37$

Find the remainder when $6^{1987}$ is divided by $37$. Because 37 is prime we have: $6^{36}$ mod $37 = 1$. I tried to get a nice combination like: $1987 = 36 * 55 + 7$, so we would have ...
1
vote
3answers
92 views

How many solutions are there?

The problem from some math competition (multiple-choice test): Consider an equation $\lfloor\sqrt{12}x\rfloor=\lfloor\frac{7}{2}x\rfloor$, where $\lfloor x\rfloor$ denotes integer part of $x$ ...
1
vote
1answer
130 views

Diophantine equation $11\cdot 2^y-3x^{10}=2014$

Ok so I have a trouble figure out here For the Diophantine equation $11\cdot 2^y-3x^{10}=2014$, either find all integer solutions, or show that there are no integer solutions.
1
vote
1answer
129 views

Eight-bit two’s complement question

Consider an 8-bit two’s complement register R. What are the least and greatest decimal integers that can be stored in R? Help would be much appreciated.
1
vote
2answers
34 views

Counting problem about housing

suppose there are 3 rooms in a dormitory: one single, one double, and one for four students. How many ways are there to house 7 students in these rooms? The answer is 7$\times$(5+4+3+2+1), but I ...
1
vote
3answers
53 views

Find m and n in the given equation:

Sorry new to this forum and don't know how to format: If $m,n\in\Bbb N$ satisfy $6^{2m+2}\cdot 3^n=4^n\cdot 9^{m+3}$, then $n$ and $m$ must be ... what? This is for my discrete mathematics ...
1
vote
2answers
62 views

How many blue balls must you choose to guarantee that you have at least $3$ light blue balls?

A bag contains $4$ light blue balls, $5$ dark blue balls, and $10$ sea blue balls. How many blue balls must you choose to guarantee that you have at least $3$ light blue balls? My first reaction ...
1
vote
3answers
469 views

Proving n is a multiple of 3 if and only if 2n is a multiple of 3

I want to prove that for all natural numbers $n$, $n$ n is a multiple of 3 if and only if $2n$ is a multiple of 3. I started by writing: $$x\equiv n=3k$$ $$y\equiv 2n=3k'$$ (where $k$ and $k'$ is any ...
1
vote
2answers
47 views

How would I get this number in base -3?

I want to find 4655 in base -3. Does this mean I would first find it in base 10 or is that already in that? In that case I have tried to find out what it is and I got this as my number "-64". Is my ...
1
vote
2answers
406 views

system of linear congruences when moduli are not coprime

$\begin{cases}x\equiv 1 \pmod{3}\\ x\equiv 2 \pmod{5}\\ x\equiv 3 \pmod{7}\\ x\equiv 4 \pmod{9}\\ x\equiv 5 \pmod{11}\end{cases}$ I am supposed to solve the system using the Chinese remainder ...
1
vote
3answers
53 views

Help with sequence: $a_k = 5*3^k + 7*2^k$ - Induction

Let $a_k$ be a sequence, where $a_0 = 12$, $\;$ $a_2 = 29$ and $a_k = 5a_{k-1} - 6a_{k-2}$ , $k\geq 2$ . I need to prove, using induction, that $a_k = 5\times 3^k + 7\times 2^k \; , k\geq 0$ . ...
1
vote
1answer
883 views

Maximum number of edges in a simple graph?

I found that the maximum number of edges in a simple graph is equal to $$\sum\limits_{i=1}^{n-1} i$$ Where $n$ = # of vertices. For example in a simple graph with 6 vertices, there can be at most 15 ...
1
vote
2answers
164 views

Proving by induction inequalities that lack the variable on the right side.

Doing proof by induction exercises with inequalities, I got stuck on one that is a bit different from the others. There is no $n$ term on the rightmost part of the inequality: Prove that the ...
1
vote
2answers
309 views

How many solutions are there to the equation $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 29$?

How many solutions are there to the equation $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 29$$ where $x_i , i = 1, 2, 3,4,5, 6$ are nonnegative integers such that a) $x_i > 1$ for $i = 1, 2, 3, 4, 5, 6$? ...
1
vote
3answers
236 views

Existence of uncountable set of uncountable disjoint subsets of uncountable set

"Can you to any uncountably infinite set $M$ find an uncountably infinite family $F$ consisting of pairwise disjoint uncountably infinite subsets of $M$?" Intuitively, I feel like it should be ...
1
vote
2answers
263 views

Discrete Mathematics - Recursion

Given the following question by my professor: Recursively define the set of natural numbers divisible by 3. My answer: ...
1
vote
1answer
142 views

Induction: base step in proving $\sum_{j=0}^n\left(-\frac12\right)^j=\frac{2^{n+1}+(-1)^n}{3\cdot 2^n}$

The other day I learn't about Induction, and though I have a good understanding of it, I have come to a problem in an assignment. To be clear I am not looking for an answer. Also the actual question ...
1
vote
3answers
77 views

Proving an inequality by induction, how to figure out intermediate inductive steps?

I'm working on proving the following statement using induction: $$ \sum_{r=1}^n \frac{1}{r^2} \le \frac{2n}{n+1} $$ Fair enough. I'll start with the basis step: Basis Step: (n=1) $$ \sum_{r=1}^n ...
1
vote
2answers
197 views

Finding the fixed point and the suitable range

I have to find the fixed point of x$^3$-x$^2$-1=0.Then x=(1/x$^2$)+1 where I chose g(x)=(1/x$^2$)+1 .Then I tried to find a fixed point for g(x).Since I don't know the range of x,I chose ...
1
vote
2answers
78 views

Which is the mathematical theory that talks about these structures?

Let's define $\sigma(n)$ as the sum of the digits of the integer $n$ modulo $9$, having posed that $\sigma(9) = 9$. Now consider 2 number $a$ and $b$ in the set $\{1, \cdots, 9\}$. Which is the value ...
1
vote
1answer
51 views

Completion of the square

Prove that for all $r \in \mathbb{R}$ $2^r + 3^r + 6^r - 4^r - 9^r \leq 1$ I have stared at it for quite sometime.. My prof suggested to use the completion of the square.
1
vote
2answers
84 views

If There are four 2's three 1's and two 0's how many was can you arange them in a 9 Digit number!

If There are four 2's, three 1's and two 0's, in how many was can you arrange them in a 9 Digit number! Using Permutations only. Show your answer is corrrect by counting it in three different ways and ...
1
vote
3answers
231 views

combinatorics implementation in real life problems

How many ways there are to organize $7$ men in a row, if two insist on not standing next to each other? How do I approach this?
1
vote
3answers
693 views

Discrete Mathematics Notation

I am having difficulty understanding the notation of discrete math. ...
1
vote
2answers
650 views

If $R,S$ are reflexive relations, so are $R \oplus S$ and $R \setminus S$?

Suppose $R$ and $S$ are reflexive relations on a set $A$. Prove or disprove each of these statements. a) $R\oplus S$ is reflexive. b) $R\setminus S$ is reflexive. I think both of a) and ...
1
vote
1answer
499 views

How to prove these using natural deduction

I'd like to prove the following logical equivalence by using natural deduction: $$(\exists x)(p(x) \implies q) \dashv\vdash (\forall x)(p(x)) \implies q.$$ As far as I'm concerned to show that two ...
1
vote
5answers
424 views

Solutions to $x+y+z=31$ and $x+2y+3z=41$

For the equations $$x+y+z=31$$ $$x+2y+3z=41$$ is there a elegant way or method to find all the positive solutions in integers? Thus far, I have been using trial and error (which is time consuming). ...
1
vote
2answers
115 views

$123^{561}$ find last $2$ digits Modular Exponentiation mod $100$?

$123^{561}$ Find the last $2$ digits Can't I work this out using modular exponentiation working mod $100$? $123^2 = 29\pmod{100}$ $123^4 = (123^2)^2 = 41\pmod{100}$ $123^8 = (123^4)^2 = ...
1
vote
2answers
159 views

Combinatorial Bijection?

I have the following problem, which seems pretty easy, but I'm not sure as to what exactly is meant by a combinatorial bijection. I know what a 'normal' bijection is. The problem and my work follows ...
1
vote
2answers
2k views

Prove: Dividing an odd number by 2 always produces a remainder of 1

How would I go about proving that for all n belonging to the natural numbers, if any given odd number n is divided by 2, then the remainder is at least 1? I got a hint: Try to reduce the number of ...
1
vote
1answer
57 views

discrete mathematics relations question 2

I am a little confused by this relation R3 is a subset of Z×Z defined by (x,y) in the set R3 if and only if x>2y is it reflexive? Symmetric? antisymmetric? or transitive? i say its NOT reflexive ...
1
vote
1answer
71 views

Prove of distinct a and b given a set

Given a positive integer $n$, suppose $S$ is a subset of $(1, 2,..., 2n)$ with $|S| = n + 1$. Prove that there are distinct $a$,$ b$ in $S$ such that $a$ divides $b$. So i know that we have a set of ...
1
vote
3answers
175 views

Proof by Math Induction

I have 3 math induction proofs I have been struggling with for a while. I understand how to do summation proofs but these ones, I can't find a general pattern to solve. Please help. 1) $D(n) = ...
1
vote
1answer
242 views

Prove that every lattice homomorphism is order preserving but converse is not true.

If $(L,*,+)$ and $(S,\cdot,\vee)$ are two lattices, a mapping $g\colon L\to S$ is called a lattice homomorphism from $L$ to $S$ if for any $a,b \in L$ we have $g(a*b) = g(a) \cdot g(b)$ and $g(a+b) = ...
1
vote
4answers
134 views

How to solve a recursive equation

I have been given a task to solve the following recursive equation \begin{align*} a_1&=-2\\ a_2&= 12\\ a_n&= -4a_n{}_-{}_1-4a_n{}_-{}_2, \quad n \geq 3. \end{align*} Should I start by ...
1
vote
3answers
1k views

Finding a minimal number of charging stops along the route

The question is: Your electric car needs to be charged every X kilometres. You are doing a road trip from Toronto to Vancouver and have a list of every charging station on the highway between Toronto ...
1
vote
1answer
98 views

Question about using the modus ponens and modus tollen

How would i solve the following. Use the following premises to show the conclusion is t. $p\vee q$ $q-r$ $p\wedge s-t$ $\neg R$ $\neg Q-U \wedge S$ $-$ for if then in this question. I did the ...
1
vote
2answers
31 views

Does the Quantifier apply to all?

I have the following question: Let $f(x, y, z) = x^2y+z^3$, where $x, y, z \in \mathbb{Z}$. For each of the following determine its truth value. Justify your answers. (a)$\exists x, y, z: ...
1
vote
3answers
108 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 ...
1
vote
2answers
79 views

Induction on a sum

The left hand side has terms involving $\binom{n}{m}= \dfrac{n!}{(n-m)!m!}$ $$1+\dfrac{1}{2}\binom{n}{1} +\frac{1}{3}\binom{n}{2}+...........+\frac{1}{n+1}\binom{n}{n} = \dfrac{2^{n+1}-1}{n+1}$$ ...
1
vote
2answers
177 views

How to express “exactly one” in the universe of discourse?

Lets say we have a proposition: There is exactly one car parked out side that is black. How can I express this in the universal discourse?
1
vote
1answer
60 views

Find generating function of given problem?

please help me to find the generating function of this problem $a_k = ( k + 1) for  k=0,1,2,3,...$
1
vote
2answers
279 views

A counting donuts problem involving combinatorics

A store carries three types of donuts: Strawberry, Chocolate and Glazed Suppose you bought $4$ of each kind and in addition, you have the option to apply sprinkles on your donuts. How many ways are ...
1
vote
3answers
722 views

Prove that any partition induces a unique equivalence relation.

Given any partition $D$ of $A$, $\exists !$ equivalence relation on $A$ from which it is derived. Can someone please help me solve this problem? thanks.
1
vote
1answer
222 views

Eccentricity in corona product

I was studying about graph operation on wiki. Corona product of graphs $G_1$ and $G_2$, is the graph which is the disjoint union of one copy of $G_1$ and $|V_1|$ copies of $G_2$ ($|V_1|$ is the number ...