# Tagged Questions

36 views

### Proving a Subset Identity

Working on part A of this problem: I worked out the first part like this: 1) If $A$ is a subset of $B$ then $\forall~x~[x\in A \implies x\in B]$ 2) Same goes for $C$ being a subset of $D$ (If ...
39 views

### Proof Verification for Discrete Math Class

Prove that $n^2$ is even iff $n$ is even. I proved it like this: Case I: $n$ is even 1) $n = 2a$ $(a\in Z)$ 2) $n^2 = 4a^2 = 2(2a^2)$ 3) $2a^2 = K$ $(K \in Z)$ 4) $n^2 = 2K$ Case II: $n$ is ...
95 views

### Find the problem with this proof.

The following attempts to prove that if $n^2$ is even, then $n$ is even. Suppose $n^2$ is even. Then $n^2$ = 2$k$ for some integer $k$. Let $n$ = 2$m$ for some integer $m$. This shows that $n$ is ...
64 views

### Prove $A = (A \setminus B) \cup (A \cap B)$

Prove $A = (A \setminus B) \cup (A \cap B)$ Logically, this is clearly true. I can explain why: start with $A$, remove all elements in $B$ and then add in any elements in both $A$ and $B$, which ...
30 views

### Contrapositive proof using rule of divisibility

Suppose $x,y,z$ are integers and $x \neq 0$ if $x$ does not divide $yz$ then $x$ does not divide $y$ and $x$ does not divide $z$. So far I have: Suppose it is false that $x$ does not divide $y$ and ...
88 views

### Proof by induction that $(1^3 + 2^3 + 3^3+\cdots+n^3) = (1 + 2 + \cdots + n)^2$

I'm sitting with the proof in front of me, but I do not understand it. $$A = \{n \in Z^{++} \mid (1^3 + 2^3 + 3^3+\cdots+n^3) = (1 + 2 + \cdots + n)^2\}$$ The first step of proof by induction is ...
13 views

### How do I derive a contradiction from an assumption that is “not asymmetric”

Let $R$ be a transitive relation on a set $A$. Define another relation, $S$, such that, for any $x,y \in A$, $Sxy$ iff $Ryx$. Moreover, let $S$ be irreflexive. Prove: $S$ is asymmetric on $A$. ...
42 views

### equivalence classes of ∼ are left cosets of H in G - my attempt

Let $H$ be a subgroup of G, and define a relation $∼$ on G by the rules that $x∼y$ mean $x^{-1}y\in H$. Show that $∼$ is an equivalence relation and its equivalence classes are the left cosets ...
136 views

### Is this a mathematical statement?

Is this a mathematical statement: Suppose this statement is false. I know what a mathematical statement is: it's either true or false. But the suppose is what's confusing me.
20 views

### Equivalence relations proof

I need to prove that if $R_1$ and $R_2$ are equivalence relations on the set $A$, then $R_1\cap R_2$ is an equivalence relation. Problem is I dont know how. Please help!
31 views

### Combinatorics Proof

I am having trouble with a combinatorics proof. I need to prove that if $r$ <= $n$ then the number of $r$ - subsets of {1,...,n} is $n!$/$(n-r)!$*$r!$ I really struggle with writing proofs and ...
27 views

### Discrete Math Proofs, Partial Orders and Equivalence Relations

I am horribly stuck on $3$ proofs for my discrete math class. Any help would be greatly appreciated. Prove that if $R$ is a partial order, then $R^{-1}$ is a partial order Prove that if $R_1$ and ...
53 views

### Proofing a Reachable Node Algorithm for Graphs

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
51 views

### Proof using addition and multiplication axioms

I'm working on addition and multiplication axioms of integers for discrete math. I'm trying to prove (k - m) + (m - n) = k - n. The first step I took was this ...
45 views

### Prove the following Statement is a tautology

I need to prove the following statement is a tautology [¬Q∧(P→Q)]→¬P So far this is what i have but now i am stuck any advice on further finishing this problem would be helpful. ...
43 views

### Prove by Induction that: $1+nx\le (1+x)^n$?

$1+nx\le (1+x)^n$, for all real numbers $x>-1$ and integers $n\ge 2$. Can you please also explain a little of the basic step and the inductions step. Thank you in advance.
41 views

### one to one positive integers and positive rationals

How would you go about proving that there is a 1 : 1 correspondence between the set of positive integers and the set of positive rationals. I know there are a lot of ways to do this but I am looking ...
39 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 ...
82 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 ...
48 views

### direct proof of combination

Prove that $(^{n}_{2}) = 1+2+3+...+(n-1)=\sum^{n-1}_{k=1}k$ for $n \ge 2$ After some time flipping through notes I think I should use the sum of the 1st n natural is ...
95 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 ...
39 views

### Proving two cosets are either equal or disjoint

I have a proof that I must produce, but I'm a little unsure of how to structure it, as I don't have a great deal of practice in forming rigorous proofs. We have, G the group of 2x2 invertible ...
31 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: ...
33 views

### Show the equivalence: $ab|c \iff a|c$ and $b|c$

Let $a,b \in \mathbb{Z}$ \ {$0$} with $gcd(a, b) = 1$ and let $c \in \mathbb{Z}$. Show the equivalence: $ab|c \iff a|c$ and $b|c$ Also give an example of numbers $a,b \in \mathbb{Z}$ \ {$0$} and ...
35 views

### How would I prove for all a that a divides zero

I'm trying to prove for all a such that a divides zero. I can explain verbally why it works but I can't seem to be able to write it down in "proof" form. Could someone help me out?
157 views

### Proving a function is a one to one correspondence

I understand that to show a function is a one to one correspondence, you have to show that the function is both one to one and onto. Proving a function is one to one seems simple enough. However for ...
99 views

30 views

### Proving some number is a subsequential limit

Let $X_n$ be a sequence of real numbers. Suppose that for every $\epsilon>0$ and for every $m\in{N}$, there exists $n\geq m$ with $|x_n|<\epsilon$. Prove that 0 is a subsequential limit of the ...
16 views

### Question involving bounded sets and sequences

Let B be a bounded, nonempty subset of real numbers. Prove that there exists a sequence $X_n$ of real numbers such that for all $n\in{N},x_n\in{B}$ and $x_n\rightarrow\sup B$ My approach so far is ...
66 views

### Proving very basic statements.

I'm just talking about (b), (c) and (d) in this question. The way I see it, (b) is asking to prove that: $$n \mod m = n \mod m$$which is like asking to prove that $1 = 1$. (c) is also asking to ...
64 views

### Prove that $a \equiv b \pmod{m_1m_2}\implies a \equiv b \pmod {m_1}$

So, I have this problem: if $$a \equiv b \mod(m_1m_2)$$ then (show) $$a \equiv b \mod(m_1)$$. I have to do a proof, but I have no idea where to begin the proof. Can someone help? Proof (Edit): ...
41 views

### Proving convergence to a certain limit

Suppose that the sequence $(X_n)$ has the following property: there is a real number $a$ such that there are infinitely many $n$ for which $X_n = a$. Prove that, if $X_n$ converges at all, its limit ...
24 views

### Proof using sets and infinimums

Let $S$ and $T$ be nonempty sets of real numbers, bounded below. Prove that $$\inf(S\cup T) = \min \{\inf S,\inf T \}$$ So the answer almost seems obvious here, I get that obviously the inf of the ...
21 views

### Question with nonempty bounds and sets

Let $A$ and $B$ be nonempty sets of real numbers, bounded above and below. Prove that if $A\cap B$ is also nonempty, then $infB\leq supA$. So my train of thought goes like this: I'm picturing that ...
23 views

### Linear Algebra Proof with one-dimensional subspaces

Suppose that V is finite dimensional, with $dimV=n$. Prove that there exist one-dimensional subspaces $U_1,...,U_n$ of $V$ such that $$V = U_1 \oplus\dotsb\oplus U_n$$ My linear algebra is rusty, very ...
44 views

I've been stuck on this question for a few days, please help me with this contra positive proof! Suppose that $x$ and $y$ satisfy $\frac 1 2 x + \frac 1 3 y = 1$. Prove that $x^2 + y^2 > ... 2answers 51 views ### Finding a real number c for polynomial (proof) The question is to find a real number c for which$ x\ge c%+$implies $$x^4-4x^3+7x-9 \ge1000$$. I was given the hint that$x>10$, then$4x^3<0.4x^4$, so$x^4-4x^3>0.6x^4$. Problem is, I'm ... 1answer 46 views ### Math Proof Question similar to reverse triangle inequality Prove that for any real three numbers x,y,z, $$|x-y||z| \le |y-z||x| + |z-x||y|$$ I am way overthinking this, there must be an easier solution to this. Any thoughts? 2answers 63 views ### How to prove this is a partial order?? Let$R$be the partial order on$\mathbb{N}$(set of all natural integers) defined by: $$n \leq m \iff m = (2^k)\cdot n \;\text{ for some }k \in\mathbb{Z},\, k \geq0.$$ I know the basic idea on how ... 3answers 75 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. 2answers 79 views ### Induction: Show:$\frac{1}{2} \times \frac{3}{4} \times \frac{5}{6} \times … \times \frac{2n-1}{2n} \leq \frac{1}{\sqrt{3n+1}}$The question: Show by using induction that:$\frac{1}{2} \times \frac{3}{4} \times \frac{5}{6} \times ... \times \frac{2n-1}{2n} \leq \frac{1}{\sqrt{3n+1}}$for all$n\inZ_+$My attempt at a ... 3answers 107 views ### Proving that Spec(α) and Spec(ß) partition positive integers iff α and ß are irrational and 1/α + 1/ß = 1 From Concrete Math, problem 3.13 asks: "Let α and ß be positive real numbers. Prove that Spec(α) and Spec(ß) partition positive integers if and only if α and ß are irrational and 1/α + 1/ß = 1" The ... 1answer 90 views ### Stuck on writing a proof. I am taking a discrete math class, and am still really new to writing proofs. I was wondering if anyone could help me with a problem. I am pretty confused on what it is even asking. Here is the ... 2answers 184 views ### Prove that the sum of two positive integers is positive? [closed] On a practice final exam for my Discrete Math class, I've been asked to prove that the sum of two positive integers is positive. I've been pulling my hair out over how to prove this, as it seems so ... 2answers 35 views ### Prove$(\forall n \in \Bbb N)[\gcd\left(n,(16n+1)^3\right)=1]$Prove$(\forall n \in \Bbb N)[\gcd(n,(16n+1)^3)=1]$Knowing that$\gcd(a,b)=\gcd(a,b+a\times k)$with$k \in \Bbb Z$$$\gcd\left(n,(16n+1)^3\right)=\gcd\left((16n+1)^3,n\right)=d$$ ... 1answer 144 views ### Discrete Math Proof By Cases Confusion I am currently finishing up my Discrete Math course, and I just wanted to clear something up that has confused me for the past few days. My teacher posts answer keys to assigned homework problems ... 5answers 159 views ### Prove that if$B-C\subseteqA^c$then$A \cap B \subseteq C$Let A, B and C three sets. Prove that if$B-C\subseteqA^c$then$A \cap B \subseteq C$Im trying to prove this with sheer logic and not making use of De Morgans laws etc. Let$y \in ...
Prove that if $A \cup B$ $\space\subseteq$ $\space C \cup D$, $A \cap B$=$\emptyset$ and $C\subseteq A$, then $B \subseteq D.$ I tried working around with this for a while and reached this ...
### Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers.
Let $m$ and $n$ be two integers. Prove that if $m^2 + n^2$ is divisible by $4$, then both $m$ and $n$ are even numbers. I think I have to use the contrapositive to solve this. So I assume \$\neg ...