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
3answers
71 views

Finding conjugates of all z $\in$ C that satisfy $z^3$

$$ z^3 = \frac{16e^{i\frac{3\pi}4}}{(1-\sqrt3)+\sqrt6e^{i\frac\pi4}} $$ Anyone know of a good way to simplify this expression?
2
votes
2answers
56 views

Every element of the empty set has three toes true or false? [duplicate]

This is a bonus question that we have and I cannot figure it out. Any help would be great! Is the proposition Every element of the empty set has three toes true or false? Explain your answer
1
vote
1answer
61 views

Why is $(\log n)^3\in O(\sqrt n)$?

Comparing the order of growth of the two functions by taking a limit and using l'hospitals rule, it seems that $\sqrt{n}$ should be O($log^3n$). Here are the steps I took: $$\lim_{n \to ∞} ...
3
votes
2answers
37 views

Graph theory - inequality

I'm having troubles solving the following problem which is about proving an inequality in the field of graph theory. We consider G = (V,E) a graph with n a natural ...
-1
votes
0answers
27 views

Is the relation RA a function? [duplicate]

Recall that, given any set A, we denote by 2A the powerset of A, i.e., the set (of sets) that consists of all the subsets of A. Given an arbitrary set A, let RA be the relation defined on A × 2 A ...
3
votes
1answer
31 views

How many password combination?

How many password combinations if you can have up to 8 letters, uppercase or lowercase, with only letters and no numbers or special characters? My attempt: $$52+52^2+52^3+52^4+52^5+52^6+52^7+52^8$$ ...
3
votes
3answers
142 views

Discrete Mathematics for someone who has already done Analysis/Algebra?

I graduated with an undergraduate mathematics degree this past May, but I had never taken a Discrete Mathematics course. I took the usual years' worth of Algebra and Analysis. I am interested in a ...
1
vote
2answers
27 views

Proof by Induction: for all integers n $\ge$ 0, $12\mid8^{2n+1}+2^{4n+2}$

I'm working on a homework problem for my discrete math class, and I'm stuck. (Note: I made a post about this earlier, but I read the problem incorrectly, thus the work was wrong, so I deleted the ...
1
vote
2answers
70 views

Algorithm: Scheduling of Overlapping Intervals

I'm reviewing algorithms, and I've come across this problem. At first, it seemed like an interval scheduling problem to me, but now I think it is a dynamic programming problem. I'm not sure how to ...
-1
votes
1answer
35 views

Factorize a number into coprime numbers

I want to know if there is a way to factorize a number into coprime numbers; for example $N = a_1 \cdot a_2 \cdot a_3 \cdots a_i$ And $a_i$ and $a_j$ are coprime for any $i \ne j$ Thanks
0
votes
1answer
38 views

search algorithms performance

A company database has 10,000 customers sorted by last name, 20% of whom are known to be good customers. Under typical usage of this database, 60% of lookups are for the good customers. Two design ...
1
vote
0answers
25 views

Adding a factor to a ranking?

I have a ranking of 10 items from best to worst. Let's assume that the best is ranked 1 and the worst is ranked 10. Each item is ranked according to some rules that we cannot know so all we get is the ...
0
votes
0answers
22 views

Calculating the nested area

I wanted to compute the white area within the following circle (I.e., the circle area minus the area of two hashed areas, or \piR^2 - (|A_1| + |A_2|)). In fact, the area of hashed areas is unknown. I ...
0
votes
2answers
51 views

Recurrence Relations Q

A sequence $S_0,S_1,S_2...$ is defined recursively as follows $S_0:=3$ $S_n:=S_{n-1}+2n$ for $n\ge 1$ Calculate a few terms and conjecture a formula for $S_n$ as a function of $n$. Prove the ...
4
votes
1answer
106 views

$0=\frac{13+13^2+13^3+\cdots}{1+2+3+\cdots}$ using infinite sums?

This is not homework, just curiosity. My question arose from the apparent absurdity that $\zeta(-1)=-\frac{1}{12}$, even though $\sum_{n=1}^\infty \frac{1}{n^z}$ only makes sense when $Re(z)>1$. ...
0
votes
1answer
12 views

Probability that certain $k$ cells are not empty

Let $M$ cells and $N$ identical balls. What is the probability that certain $k$ cells are not empty? The answer is $\frac{(M-k)^N}{M^N}$. Why?
1
vote
1answer
56 views

Increase by one all edges, Min-Cut, changes or not?

My Friends, as i ask a new question recently, Increase by one, Shortest path, changes the edges or not? i want to ask a related question as a new post Suppose we have a Graph G in which weight ...
1
vote
2answers
27 views

Increase by one, Shortest path, changes the edges or not?

as i read the following text : "Let P be a shortest path from some vertex s to some other vertex t in a graph. If the weight of each edge in the graph is increased by one, P will still be a shortest ...
0
votes
1answer
55 views

Is $f : A \to P(A), a \mapsto \{a\}$ injective or surjective? [duplicate]

Given an arbitrary set $A$, let $f:A \to P(A)$ be the function defined for all $a \in A$ by "$f(a) = \{a\}$". How would you prove that $f$ is injective or surjective?
0
votes
1answer
58 views

Find all the roots of this complex equation

Let $C$ be the set of complex numbers and $j$ the imaginary unit. Find all the roots(in $z$ $\in$ $C$) of the following equation: $$ 2z^7 + 6z^4 = z^3e^{-j{\frac π7}} + 3e^{-j{\frac π7}} $$ ...
2
votes
1answer
94 views

Contradicting statements about the Riemann zeta function at positive odd integers

I have found two contradicting statements about the value of $\zeta(k)$ when $k=2n+1$ and $n\in\mathbb{Z_0^+}$. Which one is correct? "The Riemann zeta function for odd integers has no known ...
0
votes
0answers
34 views

Big Theta Proofs

a) Show that 3x+7 is Θ(x). b) Show that 2x^2 +x -7 is Θ(x^2) c) Show that ⎣x+.5⎦ is Θ(x) d) Show that log10(x) is Θ(log2(x)) My professor gave the definitions as follows: big Omega: Let f and g ...
0
votes
1answer
16 views

Product of maxterms

Please help me break the ice in understanding how we derive a product of maxterms, say, for: $xy+x'z $ I could be missing some concept here in this but be patient with me. I have also done SOP and ...
2
votes
3answers
61 views

Given that a and b are integers, a ≡ 4 (mod 13), and b ≡ 9 (mod 13). Find c where c ≡ 9a (mod 13).

The Problem I had my first exposure to number theory today. Trying to work on some problems in hope that it will start to make more sense. Here is the problem (part a) I'm stuck on right now. My ...
0
votes
0answers
12 views

Cobweb economy analysis

Consider a traditional Cobweb economy in which a firm produces a product at period t with output $q_t$. The market inverse demand is $p_t=D(q_t)$, where $p_t$is the price. The cost of the production ...
0
votes
1answer
13 views

Proof by Induction Question - as part of Russo Dye Theorem

I began with $x_{n+1} = \displaystyle \frac{x+x_n}{2}$ and did the first few iterations to find that it follows this pattern: $\displaystyle \frac{(2^n-1)x+x_0}{2^n}$. How can i show this is true for ...
2
votes
3answers
46 views

summation of $\sum^n_{k=0} (n-k)^2$

I'm trying to find the recurrence of $$ T(n) = T (n-1) + n^2$$ After following the steps, $$T (n) = T (n-1) + n^2 = T (n-2) + (n-1)^2 + n^2 $$ $$T (n) = T (n-2) + (n-1)^2 + n^2 = T(n-3) + (n-3)^2 ...
-1
votes
2answers
42 views

Logical Proofs involving powersets [duplicate]

I have no idea how to work on the following proof. Any Suggestions? Prove that for any sets A and B, if P(A) ∪ P(B) = P(A ∪ B) then either A ⊆ B or B ⊆ A. Thanks
1
vote
2answers
39 views

Prove that it is a tautology

Let $P$, $Q_1$, $Q_2$ be some well-formed propositional formulas. Show that if $P\vee Q_1$ and $\neg P\vee Q_2$ are tautologies then $Q1\vee Q2$ is a tautology.
1
vote
1answer
64 views

Sums of consecutive odd integers, positive or negative

While supervising a student competition, my colleague and I ran across an interesting problem. Deobfuscated, it boils down to this Given a limit value $M$, which integers in the range ...
0
votes
0answers
38 views

Discrete maths - Recursion, formula and induction question

A sequence $S_{0},S_{1},\ldots$ is defined recursively as follows: $$ S_{0} = 3\,,\quad S_{k} = S_{k - 1} + 2k\quad\mbox{for}\quad k \geq 1 $$ Calculate a few terms of the sequence and conjecture a ...
1
vote
3answers
25 views

A formula for a number of combinations

Say that you are selecting three numbers in the range $[1,n]$. What formula easily determines the number of combinations where one of the possible numbers (n for example) is selected exactly once? ...
-1
votes
0answers
12 views

Recurrence relations - Substitution [duplicate]

Given T0 = 0 and Tn= T n-1 + n for all natural numbers, n>= 1 use the method of repeated substitution to derive an explicit formula for Tn.
3
votes
1answer
23 views

Prove that any amount of money of at least 14c can be made up using 3c and 8c coins

I am reading a book on Discrete Mathematics, and I am on the chapter of mathematical induction. The first problem is the fairly common example of 1+2+...+n = n(n+1)/2, which I didn't have trouble ...
5
votes
1answer
190 views

Closed-form formula for the $n^{\rm th}$ term of ${1,1,1,1,\ldots, 1}, {2,2,2,2,\ldots, 2},\ldots, {k-1, k-1}, k.$

Let $k$ be a positive integer. Consider a finite sequence $L_k(n)$ given by $$\underbrace{1,1,1,1,\ldots, 1}_{k\text{ terms}}, \underbrace{2,2,2,2,\ldots, 2}_{k-1\text{ terms}},\ldots, ...
-1
votes
1answer
36 views

need the steps on how to do this recurrence relation question

Given $T_0=0 $ and $T_n=T_{n−1}+n \forall n\in \mathbb N$ use the method of substitution to derive an explicit formula for $T_n$. Prove the validity if your formula.
1
vote
0answers
46 views

Combinatorial search by testing sets with fixed number of elements

I am struggling to see the complexity of the following combinatorial search problem. Could anyone help me? Consider a set $I$ of $n$ items known to contain $d$ defectives or less. Assume $d < ...
0
votes
1answer
34 views

How to justify the statement that a graph is connected?

Is the graph connected? Justify. Because there is a path connecting all pairs of vertices, this graph is therefore connected? Is that right?
-2
votes
3answers
26 views

recurrence relation stairs problem

Find a recurrence relation for S(n) the number of ways to climb n stairs if the person climbing can take one stair or two stairs at a time. What are the initial conditions?
-2
votes
3answers
54 views

recurrence relation question need help

Given $T_0=0$ and $T_n=T_{n-1}+n$ for all natural numbers $n\geq1$ use the method of substitution to derive an explicit formula for $T_n$. Prove the validity if your formula.
0
votes
1answer
37 views

Graph Theory: Discrete Math

I am a student from Iraq studying Graph to get in to a college in Georgia. I have trouble understanding this question. Show that the two definitions below are logically equivalent. Definition 1. A ...
0
votes
0answers
18 views

How to prove by induction/stromg induction [duplicate]

i have a question that i need to prove by induction or strong induction and I really dont know how to approach it let there be n a natural number. and a serial of numbers a1, a2,....ak of natural ...
1
vote
1answer
38 views

Proof of easy matching condition for Hall's theorem

I was studying with the recitations provided in the course 6.042 "Mathematics for Computer Science" of MIT OCW and while studying the proof of Hall's marriage problem, I understood the first proof ...
1
vote
2answers
33 views

52-Deck 3 Cards Drawn Possible Combinations Question

I have a HW problem I'm trying to pin down and I think I'm confusing myself... Question: In a card game w/ a standard 52 card deck, a hand is a set of 3 cards. Count the # of hands that are... a) ...
1
vote
1answer
49 views

Relation between $(a\bmod b)\bmod c$ and $a\bmod c$

Will (a%b)%c be equivalent to a%c? Given $b>c$ and $b$ is a prime number? If not is there any other equality that will hold? ...
0
votes
1answer
10 views

How do you create an operation for circular indices of a vector?

So I am trying to construct a way to find the next X letters (using the ASCII codes). But it is circular such that the next letter after Z is A. So Z+1 would be A. So basically it is an array (or ...
3
votes
3answers
48 views

Show that $11^n ≡ 6 \pmod{5}$ for every natural number $ n$

This is what I have : By induction Base case: $n=1$ where it is true Inductive hypothesis: Assume there exists a natural number k where this is true for $k<n$ Show for $k+1$, $11^{k+1} ≡ 6 ...
1
vote
1answer
28 views

Proving set equality

Prove that the two sets A and B below are equal. $A = \{ 7m − 5 : m \in \mathbb{Z} \}$ $B = \{14k + b : k \in \mathbb{Z}, b \in \{2,9\} \}$ Following an example I was given, my first step was to do ...
0
votes
2answers
27 views

Operations on congruence equations?

I have to do back substitution for my homework, and I have to modify x ≡ 1 (mod 5) to x=5t+1, which I understand. What I don't understand is when I put this into the next equation which becomes 5t + 1 ...
-3
votes
1answer
35 views

Proof By Induction - Factorials

$\left(\forall n \in \mathbb{N}\right)\left((n + 1)! = (n + 1) \cdot n!\right)$ Prove the following statement by induction: for all $n \in \mathbb{N}$ $\sum_{k=0}^{n}(k \cdot k!) = (n + 1)! − 1$ ...