0
votes
0answers
21 views

prove splits compatible if and only if edge-split

"Prove that if $e_A$ and $e_B$ are distinct edges of a binary $X$-tree $T$ and $C=A\Delta B$(symmetric difference), then the splits $\sigma(A), \sigma(B)$ and $\sigma(C)$ are compatible if and only if ...
0
votes
1answer
49 views

Proving that these two sets are denumerable.

(a) $S_k=\{A\subset\mathbb{N}: |A|=k\}$ for $k\in\mathbb{N}$ (b) $S = \bigcup_{k=1}^\infty S_k$ Work: For (a), I am not too sure about what approach I should use. I think finding a bijective ...
0
votes
1answer
27 views

Prove a statement for the infinite matrix

We are given infinite two dimensional matrix $\{a_{i,j}\}_{i,j=1}^\infty$. And we know that matrix contain only natural values and each number appears in the matrix exactly 8 times. Task is to prove ...
-2
votes
0answers
31 views

Discrete Mathematics Recursion Question [on hold]

Function $f$ is defined recursively by $f(0)=f_0, f(1)=f_1$, and $f(n+2) = f(n)+f(n+1)$ for $n \geq 0$. (a) For $n \geq 0$, let $c(n)$ be the total number of additions for calculating $f(n)$ using ...
0
votes
1answer
33 views

Induction Proof of: Find $f(n)$ when $n=2^k$, where $f$ satisfies the recurrence relation $f(n)=f(\frac{n}2)+1$ with $f(1)=1$

How can I proof this using regular induction and strong induction? $$f(2^k)=f(\frac{2^k}2)+1=f(2^{k-1})+1$$ $$f(2^{1-1})=f(2^0)=f(1)=1$$ $$f(2^{2-1})=f(2^1)=f(2)=f(1)+1=2$$ ...
0
votes
0answers
21 views

How many different messages can be transmitted in n microseconds using three different signals…

How many different messages can be transmitted in n microseconds using three different signals if one signal requires 1 microsecond for transmittal, the other two signals require 2 microseconds ...
0
votes
2answers
93 views

Every planar graph has a vertex of degree at most 5.

I am trying to prove the following statement, any help!? Prove that every planar graph has a vertex of degree at most 5.
-1
votes
1answer
87 views

Cut Edges Question [on hold]

I am having somewhat difficulty proving this: Show that every graph has an edge cut $[S, V \setminus S]$ such that $|[S, V \setminus S]| \geq \dfrac{|E(G)|}{2}$. Thank you for your time!
-3
votes
3answers
54 views

Graph Theory - Proof - Isomorphism [on hold]

If anyone can help me prove the following: Suppose that $G$ is a plane graph which is isomorphic to its dual. Prove that $G$ has $2n-2$ edges. I thank you for your time!
-2
votes
0answers
49 views

Graph Theory - Lower bounds [on hold]

I am trying to solve for the following problem: Find (and justify) a lower bound for 0(G) in terms of X'(G) and E|(G)| and alpha'(G). (where alpha'(G) represents the maximum size of a matching in ...
0
votes
0answers
47 views

Number of edges of a plane graph isomorphic to its dual [on hold]

I am having trouble proving the following statement: Suppose that $G$ is a plane graph which is isomorphic to its dual. Prove that $G$ has $2n-2$ edges.
0
votes
0answers
12 views

Representing trees in Set builder notation?

Is there a way to represent graphs and minimum spanning trees using set builder notation? e.g. I have a weighted graph of n nodes, all connected to each other in a mesh network manner. I am to ...
0
votes
0answers
5 views

some past paper questions in Discrete Time Systems i couldnt solve.

I am working on past papers of my exam which is in two days, there was one particular year , 2009, which I could not solve quite a lot of its questions... i only could solve 5 out of 10, can anyone ...
1
vote
1answer
34 views

Expected number of rolls when repeatedly rolling an $n$-sided die

Suppose I roll an $n$-sided die once. Now you repeatedly roll the die until you roll a number at least as large as I rolled. What is the expected number of rolls you have to make? I know the answer ...
1
vote
1answer
39 views

feedback on my answer regarding set intersections.

Prove or find a counter-example to the claim that for all sets $A,B,C$ if $A\cap B = B \cap C = A \cap C = \emptyset$, then $A \cap B \cap C=\emptyset $. the above statement is not true so i need a ...
0
votes
3answers
44 views

proving or providing counter example in disrete mathematics

Prove or find a counterexample: The product of any three consecutive natural numbers is divisible by 6. if we take a few consecutive natural numbers such as 1 ,2 ,3. and multiply i get 6 which is ...
0
votes
2answers
40 views

finding a boolean function with specific property

The problem I am trying to solve is: Prove that not every boolean function is equal to a boolean function constructed by only using $\wedge$ and $\vee$. My solution is $$\left(p\wedge\thicksim ...
0
votes
1answer
45 views

What is the statement |x+y|≤|x|+|y| saying

|x+y|≤|x|+|y| I know that |x| means the cardinality of x for example. But it looks to me like its saying the cardinality of x plus y is less then or equal to the ...
0
votes
1answer
13 views

Proving Boolean Function

Can anyone help me if I am right....!! The Question Reads: Prove that not every boolean function is equal to a boolean function constructed by only using ^ and v. This is my answer by the double ...
0
votes
5answers
53 views

Find the solution to the recurrence relation: $a_n=3a_{n-1}+1; a_0=1$

$$a_n=3a_{n-1}+1; a_0=1$$ The book has the answer as: $$\frac{3^{n+1}-1}{2}$$ However, I have the answer as: $$\frac{3^{n}-1}{2}$$ Based on: Which one is correct? Using backwards substitution ...
0
votes
0answers
26 views

Determine LUB and GLB

How do I resolve the following question. "Let S be the subset where $S={(2,2),(2,3)}$,determine the LUB & GLB of $S$." I'm totally out of idea on what does the question need us to do. Someone ...
1
vote
2answers
26 views

How do I calculate variance for sum of dice?

I'll post my work, but I'm not sure how to calculate variance. The question asks for the expected sum of 3 dice rolls and the variance. I think I got the expected sum. Any help would be awesome :) ...
1
vote
1answer
51 views

Finding Truth Values Of Nested Quantifiers

I'm looking at for example, $∃x∀y,P(x≥y+1)$ I'm told in order to prove that this is true I can us the technique that follows: Find one value of $x∈X$(only needs to be one) that has the property that ...
1
vote
3answers
54 views

Finding the limit of a sequence by diagonalising a matrix

Consider the sequence described by: $\frac11 , \frac32 , \frac75 , ... ,\frac {a_{n}}{b_{n}}$ where $ a_{n+1} = a_n +2b_n $ and $b_{n+1} = a_n+b_n$ Find a matrix $A$ such that ...
2
votes
1answer
138 views

Spelling has deteriorated by the year of 2075, how many spellings are possible?

By the year 2075, spelling has deteriorated such that the dictionary now defines the spelling of the word “RELIEF” to be any combination (with repetition allowed) of the letters F, L, R, I and E ...
1
vote
2answers
46 views

Draw a finite state machine which will accept the regular expression $(a^2)^* + (b^3)^*$

Draw a finite state machine which will accept the regular expression: $(a^2)^* + (b^3)^*$ In particular, I am confused by the $+$ sign, what does it exactly mean? Most literature I could find about ...
1
vote
1answer
56 views

Number theory, proving or finding counterexample.

Prove or find a counterexample: The product of any three consecutive natural numbers is divisible by 6. Answer True, because product of three consecutive natural numbers can be divisible by 6. Thus, ...
1
vote
0answers
40 views

Number theory, proving or finding counterexample

Prove or find a counterexample: The product of any three consecutive natural numbers is divisible by 9. Answer False,since 1 x 2 x 3 = 6 which is not divisible by 9. Thus, 9∤6 .
1
vote
2answers
35 views

How to prove the divisors of 15 form a Boolean algebra

This from Exercise 3.1 in "A Beginner's Guide to Discrete Mathematics" Let B be the set of all positive integer divisors of 15, that is B = {1, 3, 5, 15}. Prove that B forms a Boolean algebra with ...
1
vote
2answers
68 views

Proof that 2 and 3 are the only siamese twins that exist!

Let us say that two prime number p and q are siamese twins if |p-q|=1. List all the siamese twins that exist, and prove your list is complete. Proof: 2 and 3 are prime numbers and 3-2=1. Therefore 2 ...
0
votes
2answers
35 views

I'm not quite sure I understand my book's reasoning for the answer

I have the following homework problem: Does there exist a graph, $G$, with 28 edges and 12 vertices, each of degree 3 or 4? First, my solution. $$ \sum deg(v_i) = 2 \cdot |E| \\ |E| = 28 ...
1
vote
1answer
31 views

Proving the harmonic number

For $n \in \mathbb N^{+}, H_n = \sum_{i=1}^n \frac{1}{i}$ is called the $n$-th harmonic number. (a) Prove: $$\forall{n \in \mathbb N}: 1+ \frac n2 \le H_{2^n} $$ This is one of my homework questions ...
0
votes
1answer
35 views

How's my proof?

Prove that not every boolean function is equal to a boolean function constructed by only using $∧$ and $∨$. If p,q = (0,1) (p$∧$q)$∨$q = (0$∧$1)$∨$1 = 1 (p$∧$q)$∨$~q = (0$∧$1)$∨$~1 = 0 Therefore ...
1
vote
1answer
38 views

Boolean function proving contradiction ,tautology or neither

Determine whether $((p \Rightarrow q) \Rightarrow r)\Leftrightarrow (p \Rightarrow(q \Rightarrow r))$ is a tautology, a contradiction, or neither. $$\begin{array}{cccc} ...
0
votes
1answer
20 views

Find a sequence $a$ so that $a_n = s \Delta a_n $.

Let $s$ be a real number $ s \ne 0 $. Find a sequence $a$ so that $a_n = s \Delta a_n $ and $a_0 = 1$. Any help with this question will be great. This is my first time doing recurrence relations ...
0
votes
2answers
45 views

Two sequences $a$ and $b$ for which $\Delta a_n = \Delta b _n$

Find two different sequences $a$ and $b$ for which $\Delta a_n = \Delta b_n$ for all of $n$. This is my first time doing recurrence relations, so if anyone could provide some thorough and clear ...
0
votes
1answer
48 views

Roll 2 dice adding and rolling one die, probability of being equal

Roll two dice, add the results, call the number x. Roll one die call that number y. What is the probability that x and y are equal? Help please.
0
votes
0answers
45 views

proving Boolean function apart from 'and' and 'or' [duplicate]

Prove that not every Boolean function is equal to a Boolean function constructed by only using 'and' and 'or'. ...
1
vote
2answers
47 views

Coefficients of this generating function

For the first part of a problem, I solved the generating function to be $F(x) = \frac{x^3}{(1-x)^2}$ Now it's the easy part that has me a little confused. What would the coefficients be in this case? ...
0
votes
0answers
53 views

Alternating permutation exponential generating function

A permutation pi is alternating if pi_1 > pi_2 < pi_3 > pi_4 <….Let a(n) be the number of alternating permutations of size n. (a) Find a recurrence relation for a(n). (b) Evaluate the ...
0
votes
1answer
76 views

Round table exponential generating function

Let $r(n)$ be the number of different ways to seat $n$ people around a round table. Find the exponential generating function for $r$. I believe $r(n)$ is just equal to $n!/n = (n-1)!$. So then I ...
0
votes
0answers
14 views

(L1* ∩ L2*) = (L1 ∩ L2)* for all languages L1 and L2 over the alpabet Σ={A,B} Is it true or false and why?

plz answer me Determine whether each of the following statements is true or false. If a statement is false, give a counterexample..... 1- $(L_{1}^{*} \cap L_{2}^{*}) = (L_{1} \cap L_{2})^{*}$ for ...
0
votes
0answers
25 views

Calculating the number of elements in a sparse set, and finding the condition under which $\mathbb P_n$ is separated into two sparse sets

$\mathbb I_n={1,2,3,4,5,...,n}$, $\mathbb P_n=$ {$\frac m{\sqrt{k}}$|m $\in \mathbb I_n$, $k\in \mathbb I_n$ }, $n\in \mathbb N^+$ Question: 1)Compute the number of element in the set $\mathbb P_n$, ...
1
vote
1answer
22 views

Relations of functions

I am doing an assignment and I want to make sure I understood my definitions can someone check my table and if I went wrong please tell me where and why. Original question Determine whether the ...
0
votes
3answers
18 views

Prove that a function is a bijection?

I am having trouble with this problem: Prove that the function $f(x)=x^2-2x+3$ with domain $x\in(-\infty, 0)$, is a bijection from $(-\infty, 0)$ to its range. Work: Basically, I try to use the ...
0
votes
1answer
28 views

Help with Functions in Discrete Mathematics

I am having trouble solving this problem: let $p$ be a positive prime number and let $f:Z_p -> Z_p$ be defined as $f([x])=[x^2]$. Show that $f$ is a function. Give examples of how it is not ...
1
vote
2answers
51 views

Algebraic proof for the following identity

Give an algebraic proof that $\binom{n+1}{m+1} = \sum_{k=m}^{n} \binom{k}{m}$. I've tried using Pascal's rule and looking for a telescopic sum, but I can't find one. Any help is appreciated.
0
votes
0answers
11 views

Help with Integer Modulo Proof

I am stuck on this problem for a while and need some help: Prove that for any prime $p$, if $[a]*[b]=[0]$, does it follow that $[a]=[0]$ or $[b]=[0]$? Work: I do not know where to start. I was ...
0
votes
2answers
19 views

Let $A_1, A_2, \ldots, A_n$ be sets (where $n \ge 2$). Suppose for any two sets $A_i$ and $A_j$ either $A_i \subseteq A_j$ or $A_j \subseteq A_i$

Let $A_1, A_2, \ldots, A_n$ be sets (where $n \ge 2$). Suppose for any two sets $A_i$ and $A_j$ either $A_i \subseteq A_j$ or $A_j \subseteq A_i$. Prove by induction that one of these $n$sets is a ...
1
vote
1answer
44 views

How do I find the probability of specified events from a permutation of the 26 english letters?

I found a similar problem here, but I don't really understand the explanation to their solution and can't apply it. Question: What is the probability of the following even when we randomly select a ...