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

6
votes
2answers
80 views

${n}\choose {r}$ =$ 8$ Is there any way to find such $n$ and $r$?

Let ${n} \choose {r}$ = $8$. Is there any other choice of $n$ and $r$ except $8$ and $1$, $8$ and $7$ ? In general how to check that existence is guaranteed or not?
-1
votes
1answer
48 views

show $(x+1)^p = x^p$ + 1 (mod p) [closed]

for integer number a,b and p $\neq$ 0 is a=b (mod p) $\Leftrightarrow$ a-b is by p divisible. let f=$\sum \limits_{i=0}^n a_ix^i$ , g=$\sum \limits_{i=0}^n b_ix^i$ be polynomial so that f=g (mod p) ...
-1
votes
1answer
21 views

Distributing $n$ identical item to $k$ groups, each group must have at least one item

The problem is formulated as distributing $n$ pennies to $k$ children and each child is guaranteed at least one penny. The theorem is given as $\binom{n-1}{k-1}$ but I don't understand this theorem. ...
0
votes
2answers
29 views

Converting an NFA to DFA

I am atttempting to convert an NFA into an equivalent DFA. I did it, but i am not sure if it is correct. If anyone can please take a look at let me know if it is correct or if there is something wrong ...
1
vote
1answer
15 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
38 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
46 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
28 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
39 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 ...
2
votes
1answer
40 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 ...
0
votes
2answers
52 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 ...
1
vote
1answer
29 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
27 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
23 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} ...
0
votes
2answers
142 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
44 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
38 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
31 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
22 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
62 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
64 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!
0
votes
1answer
48 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
29 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
51 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
25 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
58 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
55 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
23 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
47 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
42 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
37 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
33 views

Recurrence relations help please? [closed]

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
65 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
45 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
24 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
29 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 ...
3
votes
2answers
72 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
317 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
20 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
35 views

Quadratic congruence prime numbers [closed]

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
48 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
54 views

Discrete math of $i^3$ [closed]

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.
0
votes
0answers
25 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 ...
3
votes
6answers
125 views

(14^2014)^2014 mod 60 without a calculator

Calculate without a calculator: $\left (14^{2014} \right )^{2014} \mod 60$ I was trying to solve this with Euler's Theorem, but it turned out that the gcd of a and m wasn't 1. This was my ...
1
vote
1answer
13 views

When can you not do a mapping composition?

Suppose I have $\alpha:\mathbb R^3 \to \mathbb R$ and $\beta:\mathbb R \to \mathbb R^+$. Looking over my notes, it says $\alpha \circ \beta$ can not be done but $\beta \circ \alpha$ can. What is the ...
1
vote
2answers
14 views

Are they using Vandermonde's Identity here?

Consider a set of $5$ men and $7$ women. Then there are $\binom 53 \binom 72$ groups consisting of $3$ men and $2$ women. What they are doing looks very much like this identity: $\binom {m + n}{k} = ...