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
32 views

Summation Sequence

I'm supposed to use Gauss' law to find the summation of $6k$ from $k=5$ to $n$. Here is my work: $$6(5)+6(6)+6(7)+⋯+6(n)\\+6(n)+6(n-1)+6(n-2)+...+6(5)$$ When these are added together I get ...
5
votes
2answers
264 views

Diophantine system of two equations with four variables

Find all integer solutions for the system: $$\left\{\begin{array}{rcl}xy + vw &=& 5 \\ xv - yw &=& 6\end{array}\right.$$ It's supposed to be solvable by 9-graders...
1
vote
1answer
38 views

Finding the equality of the natural logarithm to the limit and the infinite series (proof)

I'm trying to proof this equality which I found on this website: Euler-Mascheroni constant expression, further simplification $$\ln(n)=\lim_{M\rightarrow\infty}\sum\limits _{k=1}^{M}\sum\limits ...
1
vote
0answers
55 views

Can we interchange one row and one column in a determinant?

Can we swap the ith row and the ith coloumn in a determinant as an elementary operation? What happens when we do interchange them? Does the value of the determinant remain constant or does it change?
0
votes
1answer
78 views

Using Hall's Theorem to show something.

Suppose that there are five young women and five young men on an island. Each man is willing to marry some of the women on the island and each woman is willing to marry any man who is willing to marry ...
0
votes
1answer
48 views

Proof that minimum of sum of absolute differences is greater or equal of max value minus min value

Let's have an vector of natural numbers $[v_1, ..., v_N]$ my goal is to show that $$\sum_{i=1}^{N-1}|v_i - v_{i+1}| \ge v_{max} - v_{min}$$ where $v_{max} = \max_{i\in1...N}(v_i)$ and $v_{min} = ...
1
vote
0answers
51 views

Is this qual? $\ln n =\cdots$ and can I replace [] for ()?

We have $~\ln n~=~\displaystyle\sum_{k=1}^{\color{blue}\infty} \bigg[~\sum_{a=1}^{\color{red}{n-1}}\frac1{kn-a} - ({\color{red}{n-1}})\cdot\frac1{kn}~\bigg]$ Two questions: 1) is this equal? 2) can I ...
0
votes
1answer
45 views

Relations and Functions are they unique?

Let $X = \{1, 2, 3, 4\}$ and $Y = \{5, 6, 7, 8\}$. For each of the following problems, find a relation between $X$ and $Y$ that has all of the required properties. $R$ is not left-total, not ...
1
vote
1answer
43 views

Showing $(¬P\wedge¬Q)\vee(¬P\wedge Q)\equiv¬P\wedge(¬Q\vee Q)$ by distributive law(s)

I want to show that $$(¬P\wedge¬Q)\vee(¬P\wedge Q)\equiv¬P\wedge(¬Q\vee Q)$$ by one of the two Distributivity Laws: $$P\wedge(Q\vee R)\equiv(P\wedge Q)\vee(P\wedge R)$$ $$P\vee(Q\wedge R)\equiv(P\vee ...
1
vote
1answer
17 views

How many edges could a cross-section of a polyhedron have?

We know that the cross-section of a cube could have 3, 4, 5, or 6 edges. But there could be no more. This can be explained in many ways: (1) The number of edges of a cross-section can't exceed the ...
1
vote
2answers
68 views

Determining which number lies in sequence $1234567891011\ldots$ on the $10^{100005}$'th position

We have the infinite sequence made from concatenation of consecutive natural numbers: $123456789101112131415\ldots$ There is also a function $f$, where $f(n)=k$ if the digit on the $10^n$'th position ...
2
votes
1answer
34 views

Recursive equation with limit

Find $\alpha, \beta, \gamma$ for recursive equation: $$ \alpha a_{n+3}-3a_{n+1}+\beta a_n = 18n$$ $$a_0=0,a_1=\gamma, a_2=3 $$ $$\lim_{n\rightarrow\infty}\frac{3a_n+(-2)^{n}}{n^3}=3$$ Hey guys, ...
4
votes
2answers
60 views

Find All Solutions to System of Congruence

$$ \begin{cases} x\equiv 2 \pmod{3}\\ x\equiv 1 \pmod{4}\\ x\equiv 3 \pmod{5} \end{cases} $$ $ n_1=3\\ n_2=4\\ n_3=5\\ N=n_1 * n_2 * n_3 =60\\ m_1 = 60/3 = 20\\ m_2 = 60/4 = 15\\ m_3 = 60/5 = 12\\ ...
2
votes
2answers
66 views

Complicated factorial expression simplification

I have $$\binom{n}{k}\binom{n-k}{j}\binom{n-k-j}{i}$$ I have it now simplified to $$\frac{n!}{i!j!k!(n-k-j-i)!}$$ I was under the impression that the multinomial number was ...
0
votes
1answer
29 views

Solving number divisibility problem using cardinal number of sets!

How many natural numbers $n<10^6$ are divisible by $7$ but not with $10,12$ and $25$? Theorem: Let $n,k\in \mathbb{N}$ and $k\leq n$, then in the set $\{1,2,...,n\}$ we have exactly $\left \lfloor ...
1
vote
0answers
19 views

Recurence with multiple variables and functions

Is there an easy way to solve a recurrence given with two variables and three different functions? Actually I'm looking for the solution of: $$A(n,k)=A(n-2,k-1)+A(n-3,k-1)+R(n-2,k-1)+L(n-2,k-1) $$ ...
0
votes
0answers
23 views

Let P(n) denote some predicate. Suppose we prove the following premises:

Discrete math Let P(n) denote some predicate. Suppose we prove the following premises: P(0) P(1) P(n)-->P(n + 2) for n>=0. For what values of n can we conclude P(n) is true? I found this under ...
0
votes
3answers
34 views

Let $a, b, c, d$ be integers s.t $a|bc$ and $d=gcd(a,b)$. Prove $a|cd$.

From the assumption I was able to gather the following: $bc= ak_1$. Let $p=gcd(a,b)$ thus $p=dk_2$. Well since $p|a$ and $p|b$ I have the following, $a= pr_1$ and $b=pr_2$. I have been trying to ...
2
votes
2answers
86 views

Can I cancel out factorials in proofs?

I encountered the following question in a discrete math course: Prove that $ \binom{2n}{k-1} < \binom{2n}{k} $ for $k = 1, 2, \ldots , n$. Hint: This should be a very cleanly written ...
0
votes
2answers
29 views

Discrete Mathematics- Counting Bit Strings

So I'm a little bit stuck on how to continue about this problem. "How many bit strings of length eight do not contain six consecutive 0s?" So what I did first is I found the total amount of bit ...
4
votes
1answer
68 views

Maximum number of points you can put on grid $ n\times m$ with no equidistant?

Assume we have a grid of $n\times m$ points. and the distance between two rows or two columns is 1 ( unit ). I have a couple of questions related to this grid:- What is the list of possible length ...
1
vote
0answers
24 views

Chinese remainder - Error in my solution

I have the following congruence system: $x \equiv 1 \mod 5 \\ x \equiv 2 \mod 7 \\ x \equiv 0 \mod 8 \\ x \equiv 3 \mod 11$ I used the Chinese Remainder Theorem to get a solution, but it only ...
0
votes
0answers
77 views

Modifying Kruskal's algorithm for Maximum Spanning Tree

So in our class, we did a proof on Kruskal's algorithm for finding Minimum Spanning Tree. Now, based on that, I have to modify it to find me a Maximum Spanning Tree. I know the idea, taking ...
2
votes
1answer
81 views

How many subgraphs does a $4$-cycle have?

Question: How many subgraphs does a $4$-cycle have? I am trying to discover how many subgraphs a $4$-cycle has. I know that there will be $2^4=16$ subgraphs with no edges, but I am not sure how to ...
2
votes
2answers
68 views

How much knowledge of math do I need before taking bachelor of software engineering ?

I asked this question before, but now I knew who to form it correctly after doing some research for months. It always puzzles me what someone need to know before enrolling in bachelor of software ...
1
vote
2answers
30 views

Proof related to maximum degree of node in a graph

So I'm given this problem - Prove that in every graph with 25 vertices, in which holds that in every 3-subset of vertices, at least two of them are connected, there exists a node of degree at least ...
0
votes
2answers
121 views

Markov Chains Question

Markov chains are widely used in modeling several natural and social processes. Consider the following three-state Markov chain modeling the daily weather in Boston. Each day can be sunny, partly ...
1
vote
1answer
48 views

Tree-related problem, counting leafs

I am studying Graph Theory right now, and I have solved tons of problems so far. However, I got a tree-related problem, where it asks me to prove that a tree, in which maximum node degree is 6, the ...
1
vote
1answer
35 views

covering number and compactness

The following picture is what I extracted from the end of page 7 in http://www-personal.umich.edu/~romanv/papers/non-asymptotic-rmt-plain.pdf My confusion is on the blue part: in 1-dimensional ...
-1
votes
2answers
94 views

What is the algorithm to add binary numbers with boolean operations? [closed]

What is the algorithm to add up two binary numbers using only boolean operations (negation, conjunction, disjunction) in linear time? Also the program flow needs to be "linear" as well, meaning there ...
0
votes
3answers
57 views

Decrypt the following message that was encrypted using: Caesar’s cipher: WHVWWRGDB

Decrypt the following message that was encrypted using: (a) Caesar’s cipher: WHVWWRGDB I'm told to decrypt the message using Ceasar's cipher but they don't tell me the key shift so how in the world ...
0
votes
1answer
26 views

Changing the subject of a formula involving the floor.

I'm trying to prove if $3\left\lfloor \frac{x+1}{2}\right\rfloor$ is onto. But I cannot seem to be able to change the subject of my formula to $x$ from $y=3\left\lfloor \frac{x+1}{2}\right\rfloor$. I ...
1
vote
3answers
54 views

Total number of functions $f\colon S\to S$ where $S=\{1,2,3,4\}$

I missed a lecture on this topic and I'm having a hard time figuring out how this discrete function works. I'm given $S=\{1,2,3,4\}$ and $F =$ all functions from $S$ to $S$. What does this mean? I ...
1
vote
3answers
57 views

Modular Arithmetic with large exponents!

Decide whether each of the following is true or false without using a calculator: The problem is: $$11^{99}\equiv 1\pmod{5}$$ Now I know I can break the $11$ into $(10+1)^{99}$ and maybe rewrite it ...
1
vote
2answers
42 views

For $f: A \to B$ with $S, T \subset A $, show that $f(S \cap T) \subset f(S) \cap f(T) $.

Let $f:A\mapsto B$ be given and let $S\subseteq A$ and $T\subseteq A$. Show that, $$f(S\cap T)\subseteq f(S)\cap f(T)$$
1
vote
1answer
20 views

Problem with nonhomogeneous recurrence relations

I studying Discrete maths during this semester and I need your help. I have been trying to solve one non-homogeneous recurrence relation and read many-many guides how to do this, but I haven't found ...
2
votes
2answers
44 views

If $a, b, q, r \in \mathbb{Z}$ such that $a = bq + r$. Prove $\gcd(a,b) = \gcd(b, r).$

Here's what I have so far, I let $d_1$ divide $a$ and $b$ so I could write $a$ and $b$ as $a = d_1k$ and $b = d_1j$. After manipulation, I was able to achieve that $d_1 \mid r$ after substituting ...
0
votes
1answer
50 views

connectivity relation to find the transitive closure

Hello I am having difficulties with this question: Use connectivity relation to find the transitive closure of relation $R = \{(a, e),(b, a),(b, d),(c, d),(d, a),(d, c),(e, a),(e, b),(e, c),(e, e)\}$ ...
1
vote
1answer
64 views

Find the worst case time complexity of the selection sort algorithm

So, i haven't seen a question like this before, and my answer is one i got from a bunch of different sources online. Could someone verify that it is correct and explain how to answer similar ...
1
vote
1answer
48 views

discrete math-Complexity of algorithms

The best and worst case time complexity of an algorithm we are using is O(n \log_2 n) For an input of size n = 1000$ the algorithm ran in 25 seconds. Approximately how long should the algorithm run ...
6
votes
1answer
56 views

On an $h \times h$ square lattice, count all the paths from $(0,a)$ to $(h-1,b)$, $a,b \in [0,h-1]$, with diagonal moves allowed

Consider an $h \times h$ upright square lattice, where a point is defined by $(x,y)$, $x,y \in [0,h-1]$. A valid path starts from the left boundary, $(0,a)$, $ a \in [0,h-1]$ and ends to the right ...
0
votes
1answer
42 views

Quotient and Remainder of Numbers

May I ask what is the logic behind the quotient and remainder for numbers in such situation. ...
0
votes
1answer
37 views

Algorithm to generate a biased random bit

You find a fair coin in your pocket: This coin comes up heads (H) with probability 1/2 and tails (T) with probability 1/2. Show that this coin can be used to generate a biased random bit.Consider the ...
0
votes
0answers
13 views

Transforming continuous domain optimal problem to the one with discrete domain

I am now in the field of some algorithms which can be used to solve the problem with discrete domain. However, I want to apply these algorithms into the problem with continuous domain. I wonder which ...
0
votes
1answer
30 views

Performing one digit operation to compute the result.

Suppose we have $a_i, b_i, c_i \in \{0, 1, \dots , 9\}$ and $A=a_2a_1a_0, B=b_2b_1b_0, C=c_1c_0$. We want to perform the following operations with the restriction that only one digit operation is ...
0
votes
3answers
43 views

How do i evaluate a nested summation with fraction?

i have to evaluate this expression, but im not sure how to begin. $$\sum^{4}_{i=1}\sum^{5-i}_{j=2} \frac{(j+1)^2}{(2i-1)}$$
3
votes
1answer
25 views

Constructing a recursive definition.

I know a recursive definition is a function or procedure that is defined in terms of itself, for instance $f(n) = f(n - 1) + n$ or $f(n + 1) = f(n) + n + 1$. This makes sense to me in terms of ...
2
votes
1answer
70 views

Principle of mathematical induction

In his book “Introduction to Mathematical Philosophy” Bertrand Russell seems to reach the conclusion that mathematical induction is a definition and not a principle. In essence he states that ...
1
vote
3answers
33 views

How many different equivalence relations S on A are there for with R ⊆ S?

Suppose R is an equivalence relation on a set A, with four equivalence classes. How many different equivalence relations S on A are there for with R ⊆ S? I'm not too sure how to approach this ...
0
votes
2answers
43 views

Prove that relationship is symmetric and transitive

Prove that $xRy$ iff $4|(x+3y)$ is symmetric and transitive? The relation is defined on $\mathbb{Z}$. Symmetry Need to prove $4|(y+3x)$ \begin{align*} x + 3y & = 4k\\ y + 3x & = 4k - 2y + ...