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
2answers
15 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
40 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
40 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
18 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 ...
0
votes
0answers
21 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
34 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 ...
1
vote
1answer
20 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.
0
votes
2answers
25 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
21 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.
2
votes
2answers
41 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
36 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
20 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
54 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
291 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
0answers
7 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
26 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
63 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
27 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
51 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
8 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 ...
3
votes
6answers
99 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
12 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
13 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} = ...
0
votes
1answer
16 views

Find $x$ for $[809x] = [214]$ in $\mathbb Z_n$ where $n= 5124$ s.t $0 \le x < 5124$.

The following is dealing with equal classes under congruence modulo $n$. I was told to use my answer for $[809x] = [1]$ in $\mathbb Z_n$ where $n=5124$ s.t $0 \le x < 5124$, so basically it's ...
0
votes
1answer
8 views

Choosing subsets out of a set by using lists

Suppose we need to choose sets of size $2$ out of $\{A, B, C\}.$ The answer is given by $\frac {n!}{ (n - k)! k!}$. So, $n! = \{\text {ABC ACB BCA BAC CAB CBA}\}.$ What lists do $(n - k)!$ and $k!$ ...
-1
votes
3answers
85 views

Use mathematical induction to prove a statement [on hold]

Use mathematical induction to prove that: $$A\cap\left(\bigcup_{i=1}^nB_i\right) = \bigcup_{i=1}^n\left(A\cap B_i\right)$$
0
votes
1answer
24 views

Infinite Decision Problems [on hold]

How can I prove that there are infinitely many decision problems of natural numbers that cannot be soved?
1
vote
1answer
14 views

proving property of polynomial that is composite

Show that $a^m+1$ is composite if $a$ and $m$ are integers greater than 1 and $m$ is odd. [$Hint:$ Show that $x+1$ is a factor of the polynomial $x^m+1$] So I tried doing it and got a result which ...
0
votes
2answers
39 views

Prove by induction that for a natural number a there exists integers $x, y$ where $a = 7x + 2y?$

I am trying to get my head around induction at the moment and found this problem in a textbook. I think that I should be doing induction on a, but I can't even see where to start the proof.
3
votes
5answers
46 views

Sets $A,B,C$ with $B\subseteq C$, prove that $(A-B)-C=A-C$

Ran across this and couldn't figure out how you would give a formal proof. It seems intuitive, in that $(A-B)-C$ is the elements in $A$ but not in $B$, and then also remove the elements from $(A-B)$ ...
0
votes
2answers
31 views

Find the probability that an integer selected between 1 and 5000 is divisible by at least one of 3, 5 and 7

I'm having a hard time finding the solution. I can find integers that are divisible by only one of them, but there are many that are divisible by two of them. That's the problem. Find the probability ...
2
votes
0answers
21 views

Hasse Diagram Correct?

I've had to make Hasse Diagrams before, but they've always been, for lack of a better word, pretty. The lines haven't had any complicated back and forth or the like. The jump that 4 and 6 have to do ...
1
vote
1answer
24 views

Prove that there exists a 2 by 2 sub square with odd number of white cells (i.e. 1 black, 3 white cells). [on hold]

I had previously asked a question similar to this but was told the question had an error, so this is the modification. Given a 200 by 200 board containing black and white squares prove there exists ...
6
votes
1answer
47 views

Generalized way to solve $x_1 + x_2 + x_3 = c$ with the constraint $x_1 > x_2 > x_3$?

On my example final exam, we are given the following problem: ...
3
votes
1answer
44 views

Number of hairs of inhabitants and the population of a city

There is a town T where the population is greater than the number of hairs of each inhabitant. That is, if we count the number of hairs on the head of any inhabitant of the town, the amount will be ...
1
vote
2answers
21 views

Are Cartesian Product and Multiplication (kind of) equivalent?

Example(not trying to prove anything): $|\{X, Y, Z\}| \times |\{A, B\}| = |\{XA, XB, YA, YB, ZA, ZB\}| = 3 \cdot 2 = 6.$
-2
votes
2answers
41 views

Hamiltonian cycle from adjacency matrix [on hold]

I'm finding it quite hard to answer this question I found; any help would be great. Find a Hamiltonian cycle in the graph G whose adjacency matrix is $$\begin{bmatrix} ...
2
votes
1answer
48 views

Discrete Mathematics

I am having great difficulty trying to understand a question I have found and am keen to finding the solution and would appreciate any help. "Suppose that ten computer programs have been submitted ...
0
votes
1answer
29 views

Discrete Mathematics Sets Help

Hi i'm having difficulties working this question out I found, any help would be appreciated :) Let $A = \{1,2,4\}$ and $B = \{1,2,3\}$. Define the function $f: A\to B$ by the rule. What is the ...
0
votes
1answer
12 views

Bijection between lists and sets

Multiplication Principle as given in my textbook: Consider two element lists for which there are $n$ choices for the first element, and for each choice of the first element there are $m$ choices ...
0
votes
1answer
30 views

Cardinality multiplication in counting problems

Multiplying things seems to be my weakest point, so I am trying to understand as much as possible. Consider $\sum^k_{j = 0} \binom mj \binom n{k - j}$. It's the answer to the question: "from a class ...
2
votes
2answers
44 views

Experiment: Roll three 6-sided dice.

Are the following probabilities correct? I'm not very confident with probabilities and would just like these double checked please. Thank you. Experiment: Roll three 6-sided dice. a) Find the ...
0
votes
2answers
14 views

Lattice orders and number of elements in a set

My discrete mathematics lecture notes give the following definition of a lattice order: A 'Partial order R is a lattice order if the set of lower bounds for any two elements $x, y ∈ X$ has the ...
-5
votes
1answer
19 views

Finding a solution to a recurrence relation [on hold]

Here is the setting of my problem $(a_k)$ is a sequence of numbers verifying : $a_k=4a_{k-1}+5$ for all integers k greater than or equal to 1. Initial condition: $a_0=2$. I need to find a close ...
1
vote
3answers
36 views

Suppose $k$ is even and $4 \nmid k$, please explain why $k/2$ is odd

Assume integer $k$ is even and $k>2$. In order for $k/2$ to be odd, $k$ cannot be divisible by $4$. Can someone please explain why this is true, or point me in the right direction? I don't need to ...
0
votes
0answers
5 views

Find minimum number of uniformely colored rectangles in a colored grid

I have an MxN grid. In each square of the grid there is color taken from a set of color C. I can describe the whole grid with MxN statements that say something like: the square (Mi,Nj) has the color ...
4
votes
3answers
84 views

Inductive Proof that $k!<k^k$, for $k\geq 2$.

Call $P(k): k!<k^k$, for $k\geq 2$ Test it out with 2, and it's true ($2<4$). Assume that $P(k)$ is true for some $k\geq2$. Then show that $P(k+1)$ is true. $P(k+1): (k+1)!<(k+1)^{k+1}$ ...