1
vote
3answers
58 views

Explanation for the number of partitions of $\{1,\dots,n\}$ into $k$ parts

A partition of the set $\{1, 2, . . . , n\}$ into $k$ parts is a way of writing the set as a disjoint union of $k$ subsets. For example $\{1, 2, 3, 4, 5\} = \{1, 4\} \cup\{2, 3\} \cup \{5\}$ is a ...
0
votes
2answers
160 views

Help showing that every walk of length $k$ from $x$ to $y$ in a graph is a path.

If I were to suppose $x$ and $y$ are two vertices in the same connected component of a graph, and let $k$ be the distance between them, how would I prove that every walk of length $k$ from $x$ to $y$ ...
1
vote
1answer
25 views

To prove these sets are equal without using modulo arithmetic.

Prove $\{3t : t \in \mathbb Z\} \cup \{3t + 1 : t \in \mathbb Z\} \cup \{3t + 2 : t\in \mathbb Z\} = \mathbb Z.$
0
votes
2answers
37 views

Proving that any common multiplication of two numbers is a multiplication of their least common multiplication

Im trying to prove that if there are to numbers $n,m$ (natural numbers), and their smallest common multipe is $k$, so that $k = n·i$ and $k = m·j$ for some $i,j$ natural numbers, any common multiple ...
1
vote
2answers
27 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
2answers
42 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
191 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
40 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
43 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
99 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
72 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 ...
0
votes
2answers
36 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
15 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
45 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
21 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
37 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
37 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
78 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
47 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
45 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
43 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
49 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
93 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
50 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
117 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
40 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
217 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
105 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
27 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
47 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
52 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
47 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
69 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 ...
0
votes
3answers
78 views

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

Problem 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 what's going on. An explanation would be nice.
2
votes
0answers
84 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}}$ [duplicate]

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 ...