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.

learn more… | top users | synonyms

0
votes
1answer
11 views

What is the complexity of halving the size of an $n$-bit number every time.

I was discussing this question with my fiend the other day and was hoping to get some confirmation from someone if the logic I used is correct. Suppose that we have a number $N$ in base 2 ie ...
-1
votes
1answer
10 views

2 counting problems please help

Could you please help me answer these 2 counting problems. There is an office with 10 men and 12 woman. The company mandated that a cost-cutting committee be formed, but it did not specify the size ...
0
votes
1answer
18 views

How to use Peirce's arrow to express the logical operations

x↑y, x⇒y, and x⇔y. So I have really given my best, but all I could do is express the conjunction, disjunction, negation, and impilcation.
1
vote
1answer
15 views

Set of palindromes with induction

Let $A = \{a_1, a_2, ..., a_k\}$ be a finite alphabet. a. Define, using structural induction, set of all palindromes of A. b. Find the recurrent pattern which represents the number of all ...
1
vote
0answers
11 views

Coprime, commensurable integers

i really need help with proving this problem: For natural numbers k,n > 0 we define set M(k,n) = {k,2k,3k...nk}. Find out which elements are in following sets: a) M(i,n) intersection M(j,n), where ...
0
votes
0answers
15 views

Defining an example of a Boolean algebra (Discrete Math)

This question is listed in my textbook: Give an example of a Boolean algebra B and elements $x$, $y$, $z$ in $B$ such that $x + z = y + z$, but $x \neq y$. Now, I believe this means I have to ...
1
vote
0answers
15 views

Uniqueness of smallest element in poset

Prove that a smallest element, if it exists, is determined uniquely. This is follows directly for definition. An element $a \in X$ is called the smallest element of $(X, \preceq)$ if for every $x \in ...
0
votes
0answers
12 views

Explicit formula for Nth string of Gray Code.

From Wolfram MathWorld, we have: "A Gray code is an encoding of numbers so that adjacent numbers have a single digit differing by 1. The term Gray code is often used to refer to a "reflected" code, ...
0
votes
2answers
18 views

Merge Sort the sequence.

I have no idea how to do this problem. Can someone show me how to do this? The problem is I don't know how to do backward substitution. I can't seem to find resources on it, that pertain to discrete ...
0
votes
1answer
17 views

How to compute: $(89^{3} \pmod {79})^{4}\pmod{26}$?

How to compute: $(89^{3} \mod 79)^{4}\mod26$? It's easy to calculate it by evaluating $89^{3}$ first and then mod 79, but it seems stupid to do it this way. Do we have a faster way to evaluate it?
0
votes
1answer
25 views

Proof by contradiction with 9 boxes

How can i re-write for a better presentation if it is correct, if not what are the errors: Prove the following by contradiction: If 100 balls are placed in 9 boxes, some box contains 12 or more balls. ...
0
votes
1answer
17 views

If $a\equiv 4\pmod {13}$, a is integer, Find c ($0 \leq c \leq 12$) so that $c\equiv 9a\pmod {13}$

If $a\equiv 4\pmod {13}$, a is integer, Find c ($0 \leq c \leq 12$) so that $c\equiv 9a\pmod {13}$. I translated these into the form of definition: 13 | a-4 and 13|c-9a, then I got stuck on it. I ...
0
votes
2answers
28 views

Direct Proof even and odd

In trying to show that $n$ is even, is my final solution correct? First: If $n$ is even then $n^3+n$ is even. Since $n$ is even, then: $$n=2\cdot s$$ $$n^3+n = (2\cdot s)\cdot (2\cdot s)\cdot (2\cdot ...
2
votes
1answer
32 views

Show that the permutation [n, n-1,…, 2,1] has n(n-1) inversions

Show that the permutation $[n, n-1,..., 2,1]$ has $n(n-1)$ inversions How do I show that this is true? Why isn't $(n(n-1))/2$
0
votes
2answers
22 views

Probability CDF question on highest number of marbles pulled out

I'm kinda stuck on this problem. Here goes: An urn contains n marbles, numbered 1, 2, . . . , n. Suppose k < n marbles are drawn from it at random without replacement. Let X denote the highest ...
1
vote
2answers
21 views

Pigeonhole Principle Problem with a standard deck of cards

If I have a standard deck of cards, how man cards must I draw to ensure that I get three cards of the same kind. How many cards must I draw ensure that I get 5 cards of the same suit. I am new to ...
0
votes
1answer
15 views

Is there a mathematical way to know exactly how many substrings , prefixes , suffixes does a string have. for example w=“abbcc”

My trials were for prefixes and suffixes including the empty string for "abbcc" were equal to the (length_of_the_string + 1) but I couldn't figure out a way for calculating the number of substrings .
0
votes
0answers
26 views

Prove that 2 numbers in base n are equal, prove that $a_i$=$b_i$

Prove that if the numbers $a_k$$a_{k-1}$$a_{k-2}$...$a_1$$a_0$ and $b_k$$b_{k-1}$$b_{k-2}$...$b_1$$b_0$ in base n are equal, *it is not multiplication, they are digits. Where 0<=$a_i$< n and ...
0
votes
0answers
25 views

prove well-ordering of nonnull subset of positive ints using weak induction

Let $S\subseteq Z^+$. If $S$ has one element it must be the smallest element and hence it is well-ordered. Assume true for $S$ having $n$ elements. If $S$ has $n+1$ elements if the smallest is ...
-1
votes
1answer
21 views

Association, Commutation and Identity Elements on Binary Operations?

Is the following closed, associative or commutative? f(a, b) = (a+b)/2, where a, b ∈ Z. I found that it is not closed but I am not sure how to find whether or not it is associative (I was confused ...
0
votes
3answers
37 views

Multiplicative inverse of 5 modulo 8 [on hold]

Can someone help me with this? What is the multiplicative inverse of 5 modulo 8?
0
votes
2answers
32 views

Functions from a set of numbers to a set of letters?

Say I have two sets, $A = \{1, 2, 3\}$ and $B = \{a, b, c\}$. I know how to find regular functions with all numbers however how do I find a function that is $f: A\to B$?
0
votes
1answer
21 views

Is this function one-to-one and onto?

Let $$f : \mathbb{R} → \mathbb{R}, f(x) = 3^3 + 2$$ I know it's not onto actually, because it doesn't give all the real numbers. But is it one-to-one, even though we're not actually using the x ...
1
vote
2answers
20 views

how to know when a particular proof is appropriate for the given problem?

The main trouble I am currently having in math is knowing when the use cases are appropriate in a proof. I see many videos where they seem to choose a strategy like proof by contrapositive or proof by ...
1
vote
3answers
32 views

Proving a mod b < a/2 when a > b > 0

Suppose that $a \gt b \gt 0$. How can one prove that $a$ mod $b \lt a/2$? I understand why is that happening: if $a$ mod $b \gt a/2$ that means that $a/b \lt a/2$ and $a/b$ has enough "space" to ...
0
votes
1answer
35 views

Probability - Airplane overselling tickets

Few days ago, I came across a question for probability in one of the interview. Question : The same small commuter plane has 30 seats. The probability that any particular passenger will not ...
-3
votes
0answers
16 views

Use the Master Theorem to determine the big-oh for the following recurrence relation. [on hold]

Use the Master Theorem to determine the big-oh for the following recurrence relation. $\circ$ $T(n) = 4T(n/2) + n^2$ $\circ$ $T(n) = 2T(n/2) + n^3$ $\circ$ $T(n) = 7T(n/4) + n$ Help Please!!1 ...
1
vote
1answer
24 views

Proof of sum of binomials over upper index (induction)

How would you proof $$ \sum_{m=k}^{n}\binom{m}{k} = \binom{n + 1}{k + 1} $$ with $n \geq k$ and $n$, $k \in \mathbb{N}$ by induction? I had some approaches but wasn't sure if they were right, so I'd ...
1
vote
1answer
14 views

Linear Order relations

Im having a slight issue grasping the concept of Linear Orders among relations. It was made apparent to me that linear orders must first be partial orders(reflexive, anti-symmetric and transitive) ...
0
votes
0answers
55 views

Summation of product of two binomial probabilities

I am trying to find the closed form solution for this formula but got stuck: $\displaystyle\sum_{k=m}^{\infty}{\binom{k}{m}\cdot2^{-k}}$ Actually I try to compute the values of summation of product ...
0
votes
1answer
16 views

Prove sequence equivalence

$$ \forall \text{ } n \in \mathbb{P} , \text{prove } 1*2 + 2 * 3 + ... + n (n+1) = \frac{1}{3}n(n+1)(n+2) $$ Proof via Induction Base Case: n=1 $\implies 1(1+1)=\frac{1}{3}(1)(2)(3) \implies 2=2$ ...
0
votes
1answer
12 views

Bounded and Complete Lattices [duplicate]

Prove or disprove: Every bounded lattice is complete. It can be easily proved that every complete lattice is bounded. But is the converse true?
-3
votes
2answers
106 views

Compute largest integer power of $6$ that divides $73!$ [on hold]

I am looking to compute the largest integer power of $6$ that divides $73!$ I need to show working out also. Any help or hints appreciated
2
votes
2answers
38 views

Binomial theorem - a special case. Calculate sums.

I have just started my first course in discrete math and have some reflections. If I want to calculate the sum ${n \choose 0}+{n \choose 1}x+{n \choose 2}x^2+...+{n \choose n-1}x^{n-1}+{n \choose ...
0
votes
1answer
25 views

linear equations in a matrix form

Considering $$x_1 − x_2 + x_3 − x_4 = 2$$ $$x_1 − x_2 + x_3 + x_4 = 0$$ $$4x_1 − 4x_2 + 4x_3 = 4$$ $$−2x_1 + 2x_2 − 2x_3 + x_4 = −3$$ We have the following matrix $$ \begin{pmatrix} ...
3
votes
3answers
40 views

Prove that $6|(n^2 - 1)$ if $gcd(6,n) = 1$

I'm working through the problems in this book: Number Theory (Dover Books on Mathematics) and I came across this problem (title). here is my working $gcd(6,n) = 1 \implies 1 = nx + 6y$ for some ...
2
votes
3answers
50 views

What does 'any' mean in predicate calculus

I need to translate an English sentence into a well-formed predicate calculus formula. The sentence starts off as: Any tiger who chases every creature also chases itself. Does 'any' translate ...
0
votes
1answer
38 views

Understanding Mathematical Symbols in Algorithms

Just a quick question here. I am working on an assignment for algorithms involving dynamic programming. Don't worry, this isn't a question about my assignment, just a question about understanding a ...
0
votes
2answers
20 views

Differences of Probability Mass Functions

I'm bloody beginner in probability of math. and there are things that makes my mind confusing. what's the differences of those? and how i can read them? 1. $P[X|Y]$ 2. $P_{X|Y}[X]$ 3. $P_{X|Y}[x|y]$ ...
0
votes
1answer
26 views

General Behavior of Euler Totient Function

If we have two integer M and N such that $$GCD(M,N) = k$$ Then what is $$\phi(MN)$$ There is a famous identity which states: $$GCD(M,N)= 1 \rightarrow \phi (MN) = \phi(M)\phi(N)$$ And now I am ...
1
vote
1answer
21 views

Discrete math proof by contrapositive? [on hold]

Write a proof by contraposition of proposition stated below. If a, b, c are nonnegative real numbers and a^2 +b^2 =c^2,then a +b ≥c. I have a soultion online but I'm having a hard time following ...
0
votes
1answer
26 views

Show that Fibonacci and Lucas numbers satisfy the following equality for all n ≥ 2.

Fibonacci numbers F1, F2, F3, . . . are defined by the rule: F1 = F2 = 1 and Fk = Fk−2 + Fk−1 for k > 2. Lucas numbers L1, L2, L3, . . . are defined in a similar way by the rule: L1 = 1, L2 = 3 and ...
0
votes
0answers
24 views

Function Couting

I Have question, maybe You Can help :) (sorry, im don't understand method chain) X = {1, 2, 3, {1, 2}}; Y = {1, 2, a, b, c}. How much is the all functions f : X -> Y? How much is Injective ...
0
votes
1answer
24 views

Statıstıc problem

Will I use binomial distribution for this question? Can you help me please thnk you
0
votes
0answers
18 views

Statistic problem

Can you help me to solve this problem pls,I have exam and I am studyıng. What wıll I use, bınomial or Other thing ? Thank you
0
votes
0answers
11 views

What method to use to find a hypothesis of the solution of the recurrence relation?

Suppose that we want to find an asymptotic upper bound for a recurrence relation: $T(n)=aT \left ( \frac{n}{b}\right)+f(n)$ , $T(n)=c, \text{ when } n \leq n_0$, using the following method: We choose ...
0
votes
2answers
21 views

Statistic binomial dist

Can you help me to solve this question pls, I consider that I Will use binomial distrıbutıon but I couldnt
1
vote
1answer
22 views

how to find PMF of (X,Y)

Flip a coin twice. On each flip, the probability of heads equals $p$. Let $X_i$ equal the number of heads (either $0$ or $1$) on flip $i$. Let $W = 2X_1 – X_2$ and $Y = X_1 + 3X_2$ . Find ...
-1
votes
0answers
16 views

How to prove greedy algorithm optimality

Let S be a set of intervals (containing n number of intervals) of the natural numbers that might overlap and N be a list of numbers (containing n number of ...
3
votes
1answer
104 views

Using induction to prove an equality in harmonic numbers

Question: Prove that harmonic numbers satisfy the equality using induction $$ H_{1}+ H_{2} + · · · + H_{n} = (n + 1)H_{n} − n. $$ I have done the basis step: $(1 + 1)H_{1} − 1 = 1$. Correct. Done the ...