1
vote
2answers
74 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
26 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
36 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
35 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
16 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
20 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
41 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
14 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
26 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
28 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
44 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
29 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
62 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
107 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
63 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
74 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
121 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
53 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
35 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
72 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 ...
1
vote
1answer
40 views

Prove $A $ \ $B $ = $A \cap B^c $

I see the use of $A $ \ $B $ = $A \cap B^c $ being used in bigger problems but how do you prove this? Is the proof as simple as: $A $ \ $B $ $\iff$ $ x \in (A \setminus B) \iff x\in A \cap ...
1
vote
1answer
81 views

Is proving both sides of iff necessary?

I have always been taught to prove both ways of an "if and only if" statement in a formal proof, but if the opposite way is very similar to the proof of the first way. Can you just leave a note and ...
-1
votes
4answers
50 views

Help with a proof in discrete math.

I have been trying to figure out this problems to no avail. Problem $1$: Show that there are infinitely many natural numbers $x,y,z$ such that $$\frac{1}{x} + \frac{1}{y} = \frac{1}{z}.$$ Thank ...
0
votes
1answer
83 views

Prove or disprove the following statement. $7 \ | \ (x^3 + x^2 + x + 2)$, where $x$ is an odd integer

We're learning about modulus and division (Discrete mathematics and proofs course). I'm not exactly sure how to tackle this sort of problem, is there some sort of property of cubic functions ...
3
votes
2answers
42 views

Strong Induction - Understanding the lateral conditions.

I dont want the proof of this statement unless it is necessary for my questions, I just want some clarification. If cr = 1 would cr-1 = 0? How is cj 1 or 0? I understand cj is an arbitrarily ...
1
vote
1answer
491 views

Prove that between every two rational numbers a/b and c/d that there is a rational number and there are an infinite number of rational numbers [duplicate]

So the full problem is Prove that between every two rational numbers $a/b$ and $c/d$ that: There is a rational number There are an infinite number of rational numbers I am having ...
1
vote
3answers
52 views

Suppose x and y are coprime integers and z is a natural number. Prove that If xy is a zth power then x and y are both zth powers. [duplicate]

I'm supposed to use a prime factorization somewhere, and that the fundamental theorem of arithmetic is to be applied as well.
1
vote
1answer
53 views

Proof concerning Latin squares

I'm asked to solve this problem : Let $R$ be an $r\times c$ partial Latin rectangle using the numbers $[n]= \{1,2,...,n\}$. Suppose that $r < n$ and $c < n$, and let $N(i)$ be the number of ...
1
vote
4answers
53 views

Let x and y be integers, let x and y be greater than 0. Prove that the gcd (x/gcd(x,y) , y/gcd(x,y) = 1

Very confusing, not really sure how I'm supposed to deduce what $\gcd (x,y)$ is and how $$\gcd \left(\frac{x}{\gcd(x,y)} , \frac{y}{\gcd(x,y)}\right)$$ can be $1$?
1
vote
3answers
73 views

Suppose $X$ and $Y$ are greater than $0$. Show that $\gcd(X,Y)$ is $1$ iff $\gcd(X^m,Y^m)= 1$

Please help with the above I have no idea whats going on. An explanation would be nice.
0
votes
1answer
43 views

Greatest Common Divisor Proof

If $d = \gcd(a,n)$, must $\dfrac ad$ and $n$ be relatively prime? Prove or disprove. Do I show that they need to be relatively prime and then the inverse that they do not need to be relatively ...
2
votes
4answers
94 views

Show Pascal triangle properties

I need to prove two pascal triangle properties: 1) $\sum_{k=0}^{n}\binom{p+k}{k}=\binom{p+n+1}{n}$ 2) $\sum_{k=0}^{n}\binom{k}{p}=\binom{n+1}{p+1}$ I need some advice on how to approach to this ...