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

Inverse function table

I am required to create a table of values (like the one above) for h-1(x). Because x is ordered, i am just wondering, would the two tables would be identical? I just feel a little insulted that's ...
3
votes
2answers
22 views

show $\sum_{k=0}^n {k \choose i} = {n+1 \choose i+1}$

show for n $\geq i \geq 1 : \sum_{k=0}^n {k \choose i} = $ ${n+1} \choose {i+1}$ i show this with induction: for n=i=1: ${1+1} \choose {1+1}$ = $2 \choose 2$ = 1 = $0 \choose 1$ + $1 \choose 1$ = ...
0
votes
2answers
33 views

symmetry vs antisymmetry

So the problem I have is to write all the properties that a relation has (reflexive, symmetric, transitive, irreflexive, antisymmetric). The problem is the congruence relation on the set of triangles. ...
0
votes
1answer
22 views

Where does the root of this tree come from?

I am doing a practice question from Midterm Dynamic Programming The Problem : Consider a row of n numbers a1, ..., an. The numbers are all positive, and n is even. We play a game against an ...
0
votes
2answers
34 views

Solving characteristic equations…

Can someone explain to me what my teacher is doing? $x^2 - ax - b = 0$ ..? Isn;t he using the quadratic formula to solve this problem? If that's the case, then where is the $c$ at? Shouldn't he have ...
1
vote
1answer
32 views

Wouldn't this Greedy Algorithm achieve the highest possible of money in this situation?

I am doing a practice question from Midterm Dynamic Programming The Problem : Consider a row of n numbers a1, ..., an. The numbers are all positive, and n is even. We play a game against an ...
1
vote
1answer
27 views

Show $\#\{(A,B) \vert A \subseteq B \subseteq [n]\} = 3^n $

How to show that: $$ \#\{(A,B) \vert A \subseteq B \subseteq [n]\} = 3^n$$ for $n \geq 1$. That is, how can I show that there are $3^n$ pairs of subsets $(A,B)$ of a set with $n$ elements such that ...
-3
votes
1answer
30 views

Discrete Help. $A,B,$ and $C$ are Sets. Determine if the following statement is true or false.

$$|A-B| = |A| - |B|$$ It this saying $|2-2|=|2|-|2|$? so it would be true for all real numbers?
1
vote
1answer
23 views

Discrete Math Help. Identify whether its true or false.

This is what i have for part a but not sure if this is correct. a) There is a $x$ and $y$ for all integers, that $xy = y$. b) For every $x$ is an integer, there is a $y$ for all integers, that ...
0
votes
0answers
13 views

Find generating function for the numeric function.

The numeric function is: $$0\cdot5^0, 1\cdot5^1, 2\cdot5^2, \ldots, r\cdot5^r,\ldots$$ My solution is: $$\begin{align*} &\frac5{1-5z}=1+5z+(5z)^2+\ldots\\\\ ...
1
vote
1answer
19 views

Delannoy path problem

Let $f(m,n)$ be the number of paths from $(0,0)$ to $(m,n)\in \mathbb{N}\times \mathbb{N}$, where each step is of the form $(1,0)$, $(0,1)$, or $(1,1)$. a) Show that $\sum_{m\geq 0}\sum_{n\geq 0} ...
-5
votes
0answers
19 views

Compute the Laplace transform (and maybe other exercises too?) [on hold]

help please. Currently on the 2nd exercise, if you could write your steps and also could help with the other exercises it would be great, thanks!
0
votes
2answers
38 views

How to use the element method to prove the following sets are equal?

I have been asked to describe the following sets, and then prove my answers using the element method, but i am not sure how to do this. I am trying to prove that (b) is equal to $0$ as $i$ ...
0
votes
1answer
23 views

Discrete Math Validating Argument Using Deduction Method

I am lost trying prove that the expression below is a valid argument using the deduction method (that is using equivalences and rules of inference in a proof sequence). ...
1
vote
1answer
24 views

Discrete Math Predicate Logic with Balls

Attempting to use the predicate symbols shown and appropriate quantifiers, write each English language statement as a predicate wff. (The domain is the whole world.) I want to know if this is correct. ...
0
votes
1answer
27 views

How many different ways can $ 8 $ identical pens be distributed among $ 3 $ children if each child gets at least $ 2 $ pens and no more than $ 4 $?

I know the basic set up of this problem. Because each child gets at least two but no more than 4 pens for each child there is a factor equal to: $$(x^2+x^3+x^4)^3$$ Note that I included it raised to ...
1
vote
1answer
20 views

True or false, if function f : X → Y is onto, then $Codomain(f)\nsubseteq range(f)$

If function f : X → Y is onto, then is $Codomain(f)\nsubseteq range(f)$ ? I believe the answer is false, because the range is a set within the co-domain, so if anything, $range(f)\nsubseteq ...
1
vote
3answers
33 views

How to prove a Fibonacci inequality using Strong Induction?

Using strong induction I am trying to prove that $$F_n \geq \left(\frac{1+\sqrt{5}}{2}\right)^{n-2} \text{ for all } n \geq 2$$ for the Fibonacci Sequence defined by: $F_0 = 0$, $F_1 = 1$, and $F_n ...
3
votes
3answers
56 views

Wouldn't each addition take time $O(n)$?

I am going over the asymptotic runtime of regular matrix multiplication. Here is a lecture slide I am referencing(too much to type out, shown below), from Algorithms Everything makes sense up ...
-1
votes
0answers
32 views

Let $p$ be an odd prime, $D$ be an integer not divisible by $p$. show that $x^2 - y^2 = D (\text{mod } p)$ has $(p-1) $solutions [duplicate]

Let $p$ be an odd prime, $D$ be an integer not divisible by $p$. Show that $$ x^2 - y^2 = D \bmod p $$ has $p-1$ solutions Can somebody help with this problem? Thank you!
-2
votes
0answers
36 views

Solve the diophantine equation $n!=m^2-1$ where $n,\,m \in \mathbb{Z}_+$ [on hold]

Brocard's problem is a problem in mathematics that asks to find integer values of $n$ for which \begin{equation*} n!+1 = m^2, \end{equation*} where $n!$ is the factorial. It was posed by Henri ...
0
votes
1answer
19 views

General Solution of recurrence relation $x_{n + 1} = 3x_n + 8n$ [on hold]

Find the general solution of the recurrence relation $x_{n + 1} = 3x_n + 8n$. The answer is $x_n = -4n + A3^n$. I attempted to give an answer but it is wrong. Can someone give me the answer and the ...
-4
votes
1answer
34 views

Discrete math help ! quesion [on hold]

Using strong induction, prove that $F_n ≥ \phi^{n−2}$ for all $n \geq 2$ where $\phi = (1 + \sqrt{5})/2$ and $F_n$ is the Fibonacci sequence.
0
votes
1answer
46 views

group of functions $\Bbb N \to \Bbb N$

$F$ is the group of all functions fron $\Bbb N$ to $\Bbb N$, $S$ is a relation on $F$: for $f,g\in F: (f,g)∈K \iff$ for all $n\in\Bbb N, f(n)≤g(n)$. So what is $g$ or $f$ ? Are they the outputs of ...
1
vote
0answers
25 views

Proof that Paley Graphs are strongly regular with parameters $(p,\frac{p-1}{2},\frac{p-5}{4},\frac{p-1}{4})$

A Paley graph is strongly regular with parameters $(p,\frac{p-1}{2},\frac{p-5}{4},\frac{p-1}{4})$. I need to prove that, and obtain the parameters too. Proving it is regular valency $\frac{p-1}{2}$ is ...
0
votes
1answer
37 views

How to prove that $\mathcal{P}(A\cap B)=\mathcal{P}(A)\cap\mathcal{P}(B)$? (Powersets)

I am trying to wrap my head around set theory for university, but i am stuck at this problem: $$\mathcal{P}(A\cap B)=\mathcal{P}(A)\cap\mathcal{P}(B)$$ I know how to prove that two sets are equal, ...
0
votes
1answer
21 views

Identify common functions that has these properties

So I've gotten stuck on this problem: For each part below, identify a common function that has these properties: A) A function that is non-negative and concave up on (-infinity, infinity) ...
0
votes
2answers
21 views

How to find the number of words of length n with a specific rule.

I'm given the following problem: Consider a language that uses only {1, 2, 3}. The only rule this language has is that a '3' cannot follow a '3'. How many words of length n exist in this language? ...
1
vote
2answers
50 views

How to prove that the statement $ 4+10+16 + \cdots + (6n-2) = n(3n+1)$ for all $n \ge 1$ using mathematical induction?

I know you begin by establishing that it is true for $n=1$ which gives $6(1)-2 = 1(3\cdot1\cdot+1)$. Then I replace each $n$ for a $k$, and I suppose that is true for $6k-2=k(3k+1)$. But then the ...
0
votes
2answers
46 views

How to write a proof in Set Theory?

I am relatively new to Set Theory. I am trying to write a proof showing that $(A-B)^\complement = A^\complement \cup B$ But I don't even know where to start. If someone wouldn't mind ...
0
votes
1answer
20 views

Solving the nth number of this recurrence and cleaning it up using the binomial theorem.

Given this recurrence: an = an-1 – an-2 I was told to create a function that would solve for an. I thus came up with $a_n=\frac{\alpha^{n}-\beta^{n}}{i\sqrt{3}}$ Where ...
2
votes
0answers
36 views

Properties of Ackermann's function

I want to show the following properties of Ackermann's function: $A(x,y)>y$. $A(x,y+1)>A(x,y)$. If $y_2>y_1$, then $A(x,y_2)>A(x,y_1)$. $A(x+1, y) \geq A(x,y+1)$. $A(x,y)>x$. If ...
0
votes
1answer
40 views

Cantor-Bernstein Theorem proof help? [duplicate]

I know this problem has something to do with the Cantor-Bernstein Theorem, but how do I show that the set of natural numbers $\mathbb N = \{0,1,2,3,\dotsc\}$ has the same cardinality as the set of ...
2
votes
1answer
36 views

Infinite Pigeonhole Proof?

Suppose we arrange finitely many pigeons in infinitely many pigeon holes. How do I use the Infinite Pigeonhole Principle to prove that there are infinitely many pigeonholes that contain no pigeons.
1
vote
2answers
31 views

Recurrence relations help please? [on hold]

How do I solve this recurrence relation? $$ a_k = a_{k-1} + k $$ when $a_0 = 2$.
0
votes
1answer
22 views

How do I simplify this expression a $4\times 2^{k-1}$?

I know this can be very simple for many of you, I know the answer is $2^{k+1}$ but I don't know how that's the answer. and where can I see the rules for simplifying this kind of expressions.
3
votes
2answers
53 views

Solve the following recurrence relation: $S(1) = 2$; $S(n) = 2S(n-1)+n2^n, n \ge 2$

Solve the following recurrence relation: $$\begin{align} S(1) &= 2 \\ S(n) &= 2S(n-1) + n 2^n, n \ge 2 \end{align}$$ I tried expanding the relation, but could not figure out what the closed ...
1
vote
3answers
37 views

How to find the solution of $T(n,m) = T((n-1),m) + T(n,(m-1))$ in terms of big $O$ notation?

I would like to solve the recurrence $T(n,m) = T((n-1),m) + T(n,(m-1))$. I think the solution is $$O(2^{n+m})$$ because in every step you can reduce either $n$ or $m$ by one or not, but I can not ...
1
vote
1answer
22 views

Find number of circular arrangements possible

If 20 persons were invited for a party, in how many ways will two particular persons be seated on either side of the host in a circular arrangement? According to me the answer should be $17!.2!$. But ...
1
vote
3answers
28 views

For $x,y \in \mathbb R - {2}$, $x * y = xy - 2x -2y + 6$. Find the identity element.

I'm struggling to answer these kind of questions. In general, the way I set up these kind of problems is $a * e = a$, apply the particular operation to $a$ and $e$ and see if I can arrive at value for ...
1
vote
3answers
25 views

Find the function, f such that the graph of f contains the point () [on hold]

Okay so I recently ran into this problem and I have no idea how to do it. How do I solve for the following question? Find a function f such that the graph of f contains the point ( 1,2 ) and ...
3
votes
2answers
59 views

What is a good book for reviewing high school math, and preparing for university?

I'm signing up for University soon (Compsci program) as a mature student. It's been a long time since I've done any math, and I went as far as grade 11 in high school. So, I'm looking for a book that ...
3
votes
4answers
298 views

Prove that the graph is connected

I was wondering if someone can help me understand how prove that this graph is connected. Given a graph with n vertices, prove that if the degree of each vertex is at least $(n − 1)/2$ then the graph ...
0
votes
1answer
9 views

How to find out transient response of z-transform (discrete)

Given z-transform transfer function $H(z) = \frac{Y(z)}{X(z)}$, with the corresponding linear ODE, how does one find out transient response of such a transfer function given a certain input?
0
votes
1answer
27 views

Quadratic congruence prime numbers [on hold]

If $p$ is a prime number... a) show that $x^2 \equiv 1 \pmod{\!p}$ has only the following solutions: $x \equiv 1 \pmod{\!p}$ and $x \equiv -1 \pmod{\!p}$. b) show that $(p-1)! \equiv -1 ...
0
votes
4answers
64 views

if $f:X \to Y$ is 1-1 and $|X| = |Y|$, does that imply $f$ is onto?

Similarly, if $f$ is onto and both sets have the same cardinality, does that imply $f$ is 1-1? I'm pretty sure both statements are true but I'd rather not assume. Thank you for your time.
2
votes
1answer
30 views

How do I find nine messages which are unchanged by RSA encryption using the public key $(3869, 3)$.

I understand how RSA crytosystem works, however I am not sure how to apply it to answer these questions. Can someone explain please? Let $N=3869$ and be the product of two distinct unknown odd prime ...
-1
votes
1answer
53 views

Discrete math of $i^3$ [on hold]

Show that $$ \sum_{i=1}^n i^3=\frac{n^2(n+1)^2}4 $$ I don't understand how to do this, any help would be appreciated.
-1
votes
0answers
9 views

Get a given string by concatenation of the minimal number of given words [on hold]

Suppose you have an input string, say $s$, and a set of words $W$. The task is to find the minimal $N$ such that: $s = w_1 \cup w_2 \cup ... w_N$, where $w_i \in W$. Could you please name a handy ...
0
votes
0answers
22 views

How to use mobius-inversion to solve this problem?

Currently, I'm trying to solve this problem using mobius-inversion. the function f(d) means the number of (i, j, k) equals d, and function g(d) means the numbers that satisfying: d | (i, j, k). Then ...