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

Multiplicative inverse of 5 modulo 8

Can someone help me with this? What is the multiplicative inverse of 5 modulo 8?
0
votes
2answers
29 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
18 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
17 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
29 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
21 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
14 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
21 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
51 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
15 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
9 views

Bounded and Complete Lattices

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
80 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
35 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
24 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
34 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
49 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
25 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
20 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
23 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
15 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
103 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 ...
2
votes
2answers
20 views

Permutations/Integer Solutions to Equations

I'm pretty lost on this so I'd appreciate some feedback as to whether or not I'm on the right track. Find the number of integer solutions of $x_1 + x_2 + x_3 = 15$ subject to the conditions $0 \le ...
7
votes
3answers
631 views

Getting exactly one pair in a poker hand

I am not understanding this problem: In a deck of 52 cards, of 13 ranks, and 4 suits, how many different 5 card hand can we get such that, there is always exactly one pair. There is a similar ...
0
votes
4answers
31 views

Let $n$ be any positive integer

Let $n$ be any positive integer. Prove that there are positive integers $a$ and $b (a > b)$, such that $10 |(n^a − n^b)$. How would I start this proof? Would it be by induction or what?
-5
votes
1answer
27 views

Discrete Mathematics Helps [on hold]

Let $$f(x)=\ln\left(x+\sqrt{x^2+1}\right).$$ Show that $f(x)$ is an odd function. Find the inverse of $f(x)$.
3
votes
0answers
54 views

Propositions logic and problem solving

How can a question of this nature be approached: Two avid game players Alice and Bob play three different games. They are very competitive and so would do anything within the rules of the game to ...
0
votes
1answer
14 views

Help with Relation aRb if b =a^k

In the set X = {2, 3, 4, 5, 9, 16, 25, 27, 64, 81, 125} was introduced journal R is defined as follows: aRb exists a natural number k such that b = a^k. Draw a graph of the relationship. ...
0
votes
1answer
23 views

Prove that $d_n>(n-1)!$ for all $n\geq4$.

Problem: Prove that $d_n>(n-1)!$ for all $n\geq4$. $d_n$comes from the derangement where $$d_n=(n-1)(d_{n-1}+d_{n-2})=n!\sum_{m=0}^{n}\dfrac{(-1)^m}{m!}=n!\Bigg(1-\frac{1}{1!}+\frac{1}{2!}-\cdots ...
-1
votes
0answers
12 views

Discrete mathematics problem: canteens [on hold]

Now suppose you have one canteen of arbitrary volume filled with water and two empty canteens of arbitrary volume, where each volume is an integral number of cups and the empty canteens have less ...
-5
votes
0answers
61 views

How would you answer these complex variable questions? [on hold]

$1.$ Let $u(x, y) = x \sin(x) \cosh(y) − y \cos(x) \sinh(y)$. Show that $u$ is harmonic and find a harmonic conjugate $v(x, y)$. Express $u(x, y) + iv(x, y)$ in the form $f(z)$. $2.$ Find all ...
0
votes
1answer
34 views

True or false statements big O [on hold]

I am struggling with this question: Are these statements true or false and give a reason for your choice. $$2^{n+1} = O(2^{n})$$ $$2^{2n}=O(2^{n})$$ Any help is appreciated!
0
votes
2answers
20 views

Prove / Disprove function

Let $f(n)$ and $g(n)$ be arbitrary functions from $\mathbb{N}$ to $\mathbb{R}^{+}$. Prove or disprove the following: $$f(n)+g(n) = \Theta(\min\left \{ f(n), g(n) \right \})$$ Please help me prove (or ...
1
vote
0answers
34 views

How to solve a discrete system of differential equations?

I am working with discrete ODE systems. I have a $(2x2)$ system approximation to the well-known predator prey model. In this $(2x2)$ approximation system, the right hand side of the system is given ...
0
votes
1answer
39 views

Find a map $g: \mathbb{R}^2 \rightarrow \mathbb{R}$ to prove surjectivity for a given $f:\mathbb{R} \rightarrow \mathbb{R}^2 $

When the following is given: Let $f:\mathbb{R} \rightarrow \mathbb{R}^2 $ be given by $f(x)=(4x, -x)$ for all $x \in \mathbb{R}$ How to find a map $g: \mathbb{R}^2 \rightarrow \mathbb{R}$ ...
0
votes
0answers
19 views

Conditional Probability of components in series

I've two components arranged in series one after another. I've below information with me : ...
0
votes
0answers
20 views

Explaining of lost probalbity over random loss channel

I am reading a paper about packet loss probability over random loss channel. In this paper, the author give a equation about loss probability as $(1)$. However, I cannot understand the meaning of it. ...
1
vote
4answers
47 views

Prove that $1+4+7+…+(3n-2) = \frac{n}{2}(3n-1)$

Using induction prove that $1+4+7+...+(3n-2) = \frac{n}{2}(3n-1) \forall n \in \mathbb{N}$ Attempt: Let $n =1$ so $3(1)-2 = 1$ and $\frac{1}{2}(3(1)-1)=1$ Assume true at $n=k$ so $3k-2 = ...
1
vote
1answer
14 views

Prove that $\sum_{i=0}^n4^i$ = $1/3(4^{n+1} - 1)$

$\sum_{i=0}^n4^i$ = $1/3(4^{n+1} - 1)$ Attempt: Let $n =0$ $4^0 = 1 \text{ and } (4^{0+1} -1)/3 = 1$ Assume true at $n = k \text{ so we have} \sum_{i=0}^k4^i = 1/3(4^{k+1} -1)$ The part I'm stuck ...
0
votes
2answers
25 views

Step-by-step help using the distributive law in set theory

I need to prove the following set identity but I'm confused as to how to apply the set identities. $\left(A\cup C\right)\cap[\left(A\cap B\right)\cup\left(C'\cap B\right)]=A\cap B$ I tried doing the ...
0
votes
1answer
47 views

If $f(g(x))$ is one to one is $f(x)$ one to one?

From my understanding $g(x)$ would not be one to one because the different inputs for $g(x)$ could produce the same result like $x^2$. But what does it mean for $f(x)$?
0
votes
3answers
40 views

Prove that $S_n = 5^n - 1$

Use Strong Induction: $s_0 = 0 $, $s_1 =4$ and $s_n= 6s_{n-1} - 5s_{n-2}$ for all $n\in \mathbb{N} \setminus \{1\}$ Prove that $S_n = 5^n - 1$ In regards to the first step, can I start at n=2? Not ...