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
2answers
44 views

Irreducible polynomial Mod $2$

would the polynomial $x^5+x^3+1$ Mod $2$ be irreducible? I've tried factorizing, however, can't seem to find any factors? if it is irreducible how can i conclude this?
3
votes
2answers
53 views

Prove that if $a \mid n$ then $a^2\mid (n + 1)(n − 1) + 1$

I have this review question for an exam and I was hoping someone can help me solve it: Prove that if $a \mid n$ then $a^2\mid (n + 1)(n − 1) + 1$ this is what I have so far, not sure if it is ...
0
votes
2answers
104 views

Irreducible factorization

I fully understand the concept of irreducible factorization, however, is there a method in order to find the irreducible factors? For example if we have the polynomial $$x^{12}-1$$ in mod $2$
1
vote
2answers
72 views

Why is it that no bipartite graphs contain a triangle?

I know it has something to do with the vertices belonging to two differnt sets without intersection but I'm not exactly sure of a concrete explanation. Thanks in advance.
1
vote
1answer
57 views

Why does there not exist a 3 regular graph of order 5?

Because the lines of a graph don't necessarily have to be straight, I don't understand how no such graphs exist. Can anyone shed some light on why this is?
4
votes
4answers
183 views

Bound on size of subset of $\{1,2,\ldots,2n\}$ where no member is a multiple of another

Use mathematical induction given a set of n+1 positive integers, none exceeding 2n,there is at least one integer in this set that divides another integer in the set. I can't understand why when n= 1 ...
0
votes
0answers
29 views

Binary block code

I don't fully understand how i would construct binary block codes? As far as I know we have a code, say, $(5,4,3)-$code, then $5$ would represent the length, $4$ would represent the number of codes ...
1
vote
1answer
64 views

Switching lights in a matrix

I'm interested in papers and articles on the following problems (not necessarily solutions). At least is there a name to these that I can lookup ? Say that $a_{ij} \in \{-1, +1\}$ for $1 \leq i, j ...
0
votes
2answers
56 views

Analysis of Algorithms - Big O Notation Equivalences - Limits

Please see below block question from review for test. True Or False? Justify Your answers A) is 2^(n+1) = O($2^n$) B) is 2^2n = O($2^n$) C) is log($n^2$) = O(logn) D) is ...
5
votes
2answers
118 views

$\binom{n}{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
54 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) ...
0
votes
1answer
60 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
105 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
224 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 ...
2
votes
2answers
56 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
107 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
34 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
52 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
67 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
63 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
54 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
365 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
56 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
347 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
276 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
198 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
150 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
60 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
133 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
95 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 ...
0
votes
1answer
54 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
1answer
98 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
53 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
34 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
87 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
90 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
69 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
33 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
97 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
67 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
53 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.
2
votes
2answers
35 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
23 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
101 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
71 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 ...
2
votes
1answer
34 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
41 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
189 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 ...
4
votes
4answers
1k 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
150 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?