0
votes
0answers
29 views

How to write a formal proof of the statement: For all integers p, m, n, if p|m and p|n then p|(m+n)

Prove: For all integers $p$, $m$, $n$, if $p|m$ and $p|n$ then $p|(m+n)$ Proof: Let $p,m,n \in \mathbb{Z}$. Suppose $p|m$ and $p|n$. Then $\exists x,y\in \mathbb{Z}$ such that $m = px$ and $n = ...
0
votes
4answers
41 views

How to write a formal proof of the statement: For all integers n, if n is a multiple of 5 then 3n is a multiple of 5.

Prove: For all integers $n$, if $n$ is a multiple of $5$ then $3n$ is a multiple of $5$. Proof: Assume $n$ is a multiple of $5$. Then $n$ must have the form $5k$ where $k \in \mathbb{Z}$. We have ...
0
votes
1answer
78 views

Predicate Logic and Logic Proofs(Review & Homework Questions)

I'm working on some homework questions and I am struggling very hard with the logic proofs. I might have an incorrect answer for 1 of the predicate questions but I think my question makes some sort of ...
1
vote
4answers
54 views

Prove this by induction?

I'm trying to do homework problems and for the most part I've been getting the results. For this one though, I am having some trouble since its $2^n$ and I can't relate it properly: So obviously, the ...
0
votes
1answer
92 views

Proof Question involving Binary Strings & Sets

I'm just wondering about this question I've been working on for my review homework. I tried to solve it on my own and I feel my proof makes decent sense but not the best sense. Please try to give any ...
0
votes
0answers
72 views

Let Cn denote the number of ways of writing a valid list of open and closed parentheses of length 2n

(a) Let Cn denote the number of ways of writing a valid list of open and closed parentheses of length 2n (valid means that at any point along the list, the number of open parentheses must be greater ...
1
vote
1answer
44 views

Disproving the statement “$x^2\ne x$ for all $x\in\mathbb R$”

I am learning discrete mathematics in school and one of the practice question says: Find a counterexample for these quantifiers, where the domain for all variables consists of all real numbers. ...
0
votes
1answer
67 views

Prove this recurrence relation? (catalan numbers)

$$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots + C_kC_{n−k} + \cdots + C_nC_0\text{ ?}$$ Where Cn denotes the number of ways of writing a valid list of open and closed parentheses of length ...
1
vote
1answer
42 views

Segner's Recurrence Relation [closed]

Why is Segner's Recurrence Relation formula valid. Does anyone know how to prove it? I can't seem to understand why this formula works/is true. $$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots ...
1
vote
1answer
98 views

Proof of recursive formula for Catalan numbers, and their interpretation as the number of paths

If $C_n$ is the $n$th Catalan number, then show that they satisfy the following recurrence: $$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots + C_kC_{n−k} + \cdots + C_nC_0\text{ ?}$$ I tried ...
2
votes
1answer
217 views

Pigeonhole Principle

Let $X = {x_0, x_1, · · · , x_m}$ be a subset of ${1, 2, · · · , n}$, where $m > n/2$, and $x_0$ is the smallest number in $X$. Use the pigeonhole principle to show that $X$ contains two numbers ...
1
vote
3answers
62 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
163 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
26 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
40 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
31 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
44 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
52 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
196 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
47 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
46 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
101 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
81 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
37 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
91 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
16 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
47 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
139 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
22 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
47 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
55 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
113 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
51 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
46 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
57 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
112 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
51 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
152 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
43 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
292 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
116 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
67 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 ...