1
vote
2answers
26 views

If $R$ is a transitive realation, then $R\circ R\subseteq R$

Here's the question I'm struggling with: Let R be a transitive relation on a set A. Prove the R composed with R is a subset of R. I'm kind of lost on how to prove this. I've started with saying: ...
0
votes
3answers
37 views

How do I reduce this induction problem at the k+1 step

Show that $2^n > n^2$ through induction and so far I got to the $k+1$ step, but I am stuck. I have $2^{k+1} = 2 +2^k$, but I don`t know how the book turned it into $k^2 +k^2$. The book then ...
1
vote
4answers
50 views

Direct proof using modular arithmetic

Give a direct proof of $8\mid (3^n + 5^n)$ for all odd natural numbers. I know how to prove this by induction, I am not sure how to go about it using a direct proof. I would start by saying that ...
2
votes
3answers
188 views

Wheel of Fortune Problem

The Summation formula is $$\sum_{i=1}^ni =\frac{n(n+1)}2$$ How is it that we know the integers $1,2,...36$ appear exactly $3$ times. And why do we multiply the sum by $3$ in the last part of the ...
4
votes
1answer
39 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 ...
2
votes
1answer
42 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 ...
0
votes
3answers
98 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 ...
3
votes
2answers
69 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 ...
1
vote
2answers
35 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 ...
2
votes
2answers
90 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 ...
0
votes
1answer
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$. ...
3
votes
2answers
43 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 ...
0
votes
2answers
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.
0
votes
1answer
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!
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
54 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). ...
1
vote
1answer
59 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 ...
0
votes
2answers
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. ...
0
votes
1answer
44 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.
1
vote
2answers
42 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 ...
1
vote
1answer
43 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
1answer
85 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
4answers
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 ...
1
vote
4answers
103 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 ...
0
votes
1answer
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 ...
0
votes
0answers
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: ...
1
vote
2answers
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 ...
0
votes
2answers
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?
0
votes
3answers
173 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 ...
0
votes
4answers
99 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) = ...
1
vote
1answer
40 views

show that for any $n \in \mathbb{Z}$ gcd($n^2 - n + 1, n +1)$ is either $1$ or $3$.

show that for any $n \in \mathbb{Z}$ gcd($n^2 - n + 1, n +1)$ is either $1$ or $3$. My Work: I considered the case where $n =-1$ , and the case $n \not= 1$. So when $n\not= -1$ we can let $n^2 - ...
0
votes
3answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
4
votes
4answers
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): ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
2answers
45 views

Contrapositive Proof: Specific Question! Need help!

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 > ...
1
vote
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 ...
1
vote
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?
0
votes
2answers
66 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 ...
1
vote
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.
2
votes
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$ $\in$ $Z_+$ My attempt at a ...
4
votes
3answers
108 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 ...
0
votes
1answer
91 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 ...
1
vote
2answers
185 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 ...
0
votes
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$$ ...