0
votes
2answers
24 views

Proving that $S_k = \{A \subset \mathbb{N} : |A| = k\}$ for $k\in\mathbb{N}$ is denumerable. [duplicate]

I am having trouble with this problem for quite some time. I posted this question before but I still can not figure out this problem. So far,from the suggestion of user134824, I have tried to define ...
5
votes
0answers
39 views

How can I better solve proofs requiring the introduction of algebraic assumptions?

Today I decided to binge on discrete mathematics after a three year hiatus. I tackled three proofs, and all of them required the introduction of assumptions that seemed to not be found in the givens ...
1
vote
1answer
13 views

commutative ring and unity elements proof

So this is a review problem in our book I came across and i really want to understand it but I am just not having any luck, I did some research and found a guide on solving it but that's not really ...
2
votes
2answers
54 views

Prove $\gcd(ka,kb) = k*\gcd(a,b)$

For all $k > 0,\ k\in \Bbb Z$ . Prove $$\gcd(k*a,\ k*b) = k *\gcd(a,\ b)$$ I think I understand what this wants but I can't figure out how to set up a formal proof. These are the guidelines we ...
0
votes
1answer
27 views

proof with divisibility

this is the original question prove: $\forall c \in Z, a\neq 0 $and b both $ \in Z$ $a|b \iff c\cdot a|c\cdot b$ Then he corrected himself by saying for problem 1: to show that ca | cb implies a | b ...
0
votes
2answers
88 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
79 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
50 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
47 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
44 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.
1
vote
2answers
58 views

Graph Theory - Proof

I am need help to Prove the following statement: Let G be a $k$-regular graph with $n$ vertices and $k \geq 1$. Prove that $G$ does not have an independent set of size greater than $\dfrac{n}{2}$. ...
0
votes
1answer
60 views

Graph Theory - Complete graphs [on hold]

I am having trouble with this question... Find the expected number of copies of $k_k$ in $G(n,1/2)$. Can anyone help!?
1
vote
2answers
79 views

How to prove a function from $\mathbb N\times \mathbb N$ to $\mathbb N$ is bijective. [duplicate]

I am having trouble with this problem: $f\colon \mathbb N\times \mathbb N \rightarrow \mathbb N$ is defined by $f(i,j)=\dfrac{(i+j-1)(i+j-2)}{2}+i$. How do you prove that $f$ is a bijection from ...
0
votes
2answers
28 views

Proving that a set is denumerable without using a particular theorem

this question may seem like a duplicate of another one that I asked, but it is not. In this question, I am not allowed to use the Theorem which states: Every infinite subset of a denumerable set is ...
0
votes
0answers
37 views

Proving that the set of irrational numbers is uncountable [duplicate]

Work: Assume that the set of irrational numbers is countable. Since $Q$ is infinite, it is therefore denumerable. Therefore, there exists a bijective function $f: N \rightarrow Q$. From here I am ...
1
vote
1answer
36 views

Proving that $f: N\times N \rightarrow N$ is surjective [duplicate]

I am having trouble proving that the function $$f: N\times N \rightarrow N, \ \ f(i,j)=2^{i-1}(2j-1)$$ is surjective. Work: I know that using the theorem in which $n$ is the product of prime numbers ...
1
vote
1answer
17 views

Help with composite identity functions in discrete mathematics

I am having trouble with the following problem: For nonempty sets $A$ and $B$ and functions $f : A \rightarrow B$ and $g: B \rightarrow A$ suppose that $g \circ f = i_A$, the identity function on ...
0
votes
0answers
21 views

Discrete Math identity function proof

Hi I am having trouble with this question: For nonempty sets $A$ and $B$ and functions $f:A\rightarrow B$ and $g:B\rightarrow A$ suppose that $g\circ f=i_A$, the identity function on $A$. How do ...
1
vote
1answer
28 views

Help with identity functions in discrete mathematics

I have trouble with trying to solve the following problem: For nonempty sets $A$ and $B$ and functions $f:A\rightarrow B$ and $g:B\rightarrow A$ suppose that $g\circ f=i_A$, the identity function on ...
-1
votes
3answers
43 views

Proving functions are injective and surjective

I am having trouble with the following problem: For nonempty sets $A$ and $B$ and functions $f:A \rightarrow B$ and $g:B \rightarrow A$ suppose that $g\circ f=i_A$, the identity function of $A$. ...
0
votes
1answer
15 views

Proving Integer Modulo is Well-Defined

I have trouble figuring out this problem: $h: Z_4 \rightarrow Z_6$ by $h([a])=[3a]$ for each $a\in Z$. Prove that h is well-defined thus it is a function and that h is neither injective nor ...
1
vote
2answers
27 views

$K$ events that are $(K-1)$-wise Independent but not Mutually/Fully Independent

I had the following question: Construct a probability space $(\Omega,P)$ and $k$ events, each with probability $\frac12$, that are $(k-1)$-wise, but not fully independent. Make the sample space as ...
1
vote
1answer
38 views

Proving a Bound for Oddtown-Eventown or Clubtown

Suppose we have a town with a set of residents $V$, where $|V| = n$. The residents like forming clubs, and we have clubs $C_1,C_2,\ldots,C_m \subseteq V$. We are interested in the maximum number of ...
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 ...
1
vote
2answers
23 views

Help with Discrete Math Functions and Bijections

I have trouble with the following 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: I tried to first prove ...
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 ...
1
vote
4answers
45 views

proof by induction: sum of binomial coefficients

Question: Prove that the sum of the binomial coefficients for the nth power of $(x + y)$ is $2^n$. i.e. the sum of the numbers in the $(n + 1)^{st}$ row of Pascal’s Triangle is $2^n$ i.e. prove ...
1
vote
1answer
30 views

Proving modulo equation with x-power

I'm trying to prove following equation: $$ (g^{y} \mod n)^x \mod = g^{xy} \mod n $$ I tried many multiple approaches, all of them failed, and there is waaay too much of them to write them here, so I ...
0
votes
2answers
31 views

Proof by Induction $4^n \geq 16n^2$

Prove that for an integer $n \geq 4$, $4^n \geq 16n^2$ Base Case: For $n = 4$, $4^4 \geq 16(4)^2$ $256 = 256$ Induction Hypothesis: Suppose this statement hold up to $4^k > 16k^2$ Then: ...
1
vote
1answer
39 views

How would I solve this mathematical induction proof? I am stuck after the first part of the induction.

$$1 + 5 + 5^2 + \ldots + 5^n = \frac{5^{n+1}-1}{4}$$ Basis case $n= 0$: $1^0 = 1 \;\;\;\;\;\;\;\;\;\;\;\; \frac{5^{1+1}-1}{4}=1$ Assume true for $n=k$: $$1 + 5 + 5^2 + \ldots + 5^k = ...
2
votes
4answers
40 views

Help with discrete math proof?

I am having trouble proving the following: If $x\in R$ and $x > 0$, then $x^4+1 \geq x^3+x$. Work: I tried to rearrange the equation as $x^4-x^3-x+1 \geq 1$, but that does not really help. I ...
0
votes
2answers
18 views

Show that for any $s \in S$ where $S = $ {$s \in \mathbb{N} | \exists m,n \in \mathbb{Z}$, we have $d|s$ where $d$ is the smallest element

Explain why the set $S = $ {$s \in \mathbb{N} | \exists m,n \in \mathbb{Z}, s = ma+ nb $} has a smallest element, call it d, so we know there exists $x,y \in \mathbb{Z}$ such that $d = ax + by$, and ...
0
votes
0answers
28 views

Prove that $s \not= \emptyset $ by showing that at least one of $|a|$ or $|b|$ is an element of $S$.

. I'm trying to show an alternative proof to Bezout's Lemma (let $a, b \in \mathbb{Z}$, then there exists $x,y \in \mathbb{Z}$ such that $gcd(a, b) = ax + by$). Heres one of the steps in proving it: ...
-1
votes
2answers
70 views

Quotient-Remainder Theorem Proving [closed]

This theorem is obviously correct. Now I try to prove it by well-ordering principle. But I don't know where to start the proving....
2
votes
1answer
64 views

Proving a statement about prime numbers

Let $p_1,p_2,p_3,\cdots$ be all the primes sorted in an increasing order. Is $p_1p_2p_3\cdots p_i + 1$ is always prime? Why? How can I prove that?
1
vote
0answers
121 views

Can I use Strong Induction to prove graph theory? - Hamilton Path/Tournament Graphs

I am working on the below proof. I am still new to proves so I am wondering if you guys can answer the following questions: 1) Did I use the inductive hypothesis correctly here? (By the inductive ...
1
vote
1answer
64 views

Another proof by strong induction problem

I am trying to solve the following problem using proof by strong induction. the problem is: Assume that a chocolate bar consists of n squares arranged in a rectangular pattern. The entire bar, or any ...
0
votes
1answer
23 views

In-degree and out-degree of two distinct vertices in a directed graph

I need to prove or give a counterexample that for all $n\ge2$ there exists a directed graph of order $n$ such that every pair of distinct vertices have different out-degrees and same in-degrees.
0
votes
4answers
76 views

Show {$ ax + by | x, y \in \mathbb{Z}$} = {$n$ gcd$(a,b)|n\in \mathbb{Z}$}

I have the following problem: Let $a, b \in\mathbb{Z}$. Show that {$ ax + by | x, y \in \mathbb{Z}$} = {$n$ gcd$(a,b)|n\in \mathbb{Z}$} I understand that the Bezout's lemma says that $gcd(a,b) = ...
0
votes
0answers
17 views

proving a recurrence relation

I'm trying to prove that the recurrence $T(n) = T(\alpha n)+T((1-\alpha)n)+n$, where $0<\alpha<\frac{1}{2}$, has an order of growth $T(n)= an$ log $n$ $\in \Theta(nlog(n))$ where $a$ is a ...
0
votes
1answer
38 views

Prove or disprove for any real number

Prove or disprove for any real number $x^2 < x$ , considering $0.5^2 = 0.25, 0.25 < 0.5$
0
votes
3answers
81 views

Derive Closed form sum of N^2

Can anyone explain to me how you would derive this ? I have this question asked in a CS class and can't figure out how to derive it. it has to be derived as you would with sum of N ex ...
2
votes
2answers
50 views

How to prove $n^3 < 4^n$ using induction? [duplicate]

It's true for all Natural numbers. What I've got so far: Prove $P(0) \to $ base case: Let $n = 0$ $(0)^3 < 4^0 = 0 < 1$ Then $P(0)$ is true. Part Two: Prove $P(n) \Rightarrow P(n + 1) ...
0
votes
5answers
38 views

help solving this proof with remainders

For all $n\ge3\in \mathbb N$, if $n \equiv 3 \pmod{4}$ then ${3^n} \equiv 2 \pmod{5}$. I tried to set $n = 3+4k$ but it doesn't help. Any hints first please?
3
votes
3answers
122 views

Prove that, for any positive integer n: $(a + b)^{n} \leq 2^{n-1}(a^{n}+b^{n})$

Prove that, for any positive integer n: $(a + b)^{n} \leq 2^{n-1}(a^{n}+b^{n}) $ I tried induction theorem, when $n = 1$ it is obviously right. But, say $n=k$, It does not make sense since I cannot ...
1
vote
3answers
54 views

Show that “$\Gamma \models S \Rightarrow \Gamma \vdash S$” entails “if $\Gamma \nvdash P \And \sim P$ then $\Gamma$ is satisfiable”

Show that "$\Gamma \models S \Rightarrow \Gamma \vdash S$" entails "if $\Gamma \nvdash P \And \sim P$ then $\Gamma$ is satisfiable" I'm primarily confused with the notation being used here. In ...
0
votes
1answer
38 views

The set of all real numbers $\epsilon$ with $0 < \epsilon < 1$ is equinumerous with the set of all sets of positive integers

How is a proof like this normally conducted? I know that Cantor's theorem may prove useful here, but I'm having trouble extending the definition to problems that are (seemingly) unrelated.
0
votes
1answer
28 views

Show that the set of all subsets of an infinite enumerable set is not enumerable

I know this problem involves using Cantor's theorem, but I'm not sure how to show that there are more subsets of an infinite enumerable set than there are positive integers. It seems like a lot of ...
0
votes
2answers
77 views

Tough Turing machine multiple choice questions

I'm having a tough time deciding whether my answers for these questions are correct. Can anyone help me agree on something? They seem pretty easy, but I've found that they're actually difficult. ...
2
votes
5answers
57 views

Prove that $A\setminus (B\setminus C) = (A\setminus B) \cup (A\setminus C^c)$ for sets $A,\ B,\ C$ in some Universal Set $U$.

I'm working on this proof for some students I am tutoring and I've gotten a little stuck. I want to show them how to do a proof in complete, extravagant detail and get them familiar with ''element ...