0
votes
4answers
45 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
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 ...
0
votes
1answer
22 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
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
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
65 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
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) = ...
1
vote
1answer
38 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
25 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
15 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
65 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
34 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
23 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
22 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
40 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
45 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
42 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
50 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
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.
2
votes
2answers
73 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
91 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
84 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
142 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
33 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$$ ...
2
votes
1answer
104 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 ...
0
votes
5answers
158 views

Prove that if $B-C$ $\subseteq$ $A^c$then $A \cap B \subseteq C$

Let A, B and C three sets. Prove that if $B-C$ $\subseteq$ $A^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 ...
0
votes
1answer
61 views

Let A, B, C and D be four sets:

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 ...
1
vote
6answers
232 views

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 ...
3
votes
1answer
60 views

Proof by contradiction:

Prove by contradiction: If the sum of N natural numbers is less than N + 2 then each of these numbers is less than 3. ATTEMPT: I have to assume that the sum of N natural numbers is greater than N+2 ...
1
vote
3answers
65 views

proof by contradiction $A ∩ (B - A)= \varnothing.$

Use the method of proof by contradiction to prove that if A and B are sets, then $$A ∩ (B - A)= \varnothing.$$ It says I have to use contradiction, but contradiction is the one I have a problem with! ...
0
votes
1answer
113 views

Give proofs by induction for the following relation properties.

Let $R$ and $S$ be relations such that $R\subseteq S$. Prove that $R^n$ is a subset of $S^n$ for all positive integers $n$. Let $R$ be a symmetric relation. Prove that $R^n$ is symmetric for all ...
1
vote
2answers
47 views

Understanding induction proof with inequalities

I'm having a hard time proving inequalities with induction proofs. Is there a pattern involved in proving inequalities when it comes to induction? For example: Prove ( for any integer $n>4$ ): ...
0
votes
2answers
37 views
0
votes
1answer
51 views

Prove that the set $B = \{0,1\}^8$ forms a group

Prove that the set $B = \{0,1\}^8$ forms a group under the composition operator: $g \circ f$ is defined by $(g \circ f)(x) = g(f(x))$
1
vote
3answers
63 views

Prove that *BIG'* = *BIG* - *Little* (set difference) is uncountable.

Let BIG be an uncountable set and let Little be a countable one. Prove that BIG' = BIG - Little (set difference) is uncountable.
2
votes
3answers
81 views

Prove that if $a|b$ and $a|c$, then $a\mid(c-b)$.

I'm having trouble proving this one. I know its true. Any ideas? Here is what I have so far: If $a\mid b$, then there exists an integer $q_1$ such that $b = aq_1$. If $a\mid c$, then there exists an ...
0
votes
0answers
41 views

Is this GCD proof valid?

I came across this theorem and wrote a proof, but I'm not sure if I made any incorrect assumptions. I also know that this isn't the easiest way to prove it - I just want to know if it works and ...
0
votes
2answers
45 views

Prove that for every $x \in \mathbb{Z}$ for which $x \geq 3$, if $x \equiv 3 \pmod 4$ then $3^x - 2 \equiv 0 \pmod 5$

Prove that for every $x \in \mathbb{Z} \geq 3$, if $x \equiv 3 \pmod 4$ then $3^x -2 \equiv 0 \pmod 5$. I was trying to use induction: Base case $(x = 3)$: If $3 \equiv 3 \pmod 4$ then $3^3 - 2 ...
2
votes
1answer
116 views

Proving a Property of a Set of Positive Integers

I have a question as such: A set $\{a_1, \ldots , a_n \}$ of positive integers is nice iff there are no non-trivial (i.e. those in which at least one component is different from $0$) solutions ...
0
votes
0answers
24 views

Discrete Math Equation Proof (by induction?) [duplicate]

Consider the following description of a game. There are n people playing, one of whom leads the game. They are playing on a playing field with no obstacles. Everyone carries one water balloon. ...
0
votes
1answer
78 views

Strong induction definition clarification

I have a general question about strong induction: Assuming that the base case is 0, if I let my inductive hypothesis be that for all 0 <= k < n some statement is true, and if I prove that that ...
0
votes
1answer
38 views

prove that |a| < b if and only if -b < a < b

I know I'd have to prove both sides here so: ...
0
votes
2answers
51 views

Interesting question posted earlier by another user need help solving

I've been trying to solve a problem a user posted that I thought was interesting. Considered a lucky number, the Thai government decides to issue coins of 9 baht. Show that, forall suciently large ...
-1
votes
3answers
101 views

Prove $2^n > 10n^2$ for all sufficiently large integers n.

How do I prove $2^n > 10n^2$ inductively? I know you can prove this to be true using calculus (i.e. taking derivatives). But how would I do it inductively?
3
votes
4answers
165 views

$A \oplus B = A \oplus C$ imply $B = C$?

I don't quite yet understand how $\oplus$ (xor) works yet. I know that fundamentally in terms of truth tables it means only 1 value(p or q) can be true, but not both. But when it comes to solving ...
0
votes
2answers
351 views

Prove: Dividing an odd number by 2 always produces a remainder of 1

How would I go about proving that for all n belonging to the natural numbers, if any given odd number n is divided by 2, then the remainder is at least 1? I got a hint: Try to reduce the number of ...
2
votes
2answers
63 views

How do I prove that $(1+\frac{1}{2})^{n} \ge 1 + \frac{n}{2}$ for every $n \ge 1$?

How do I prove that $(1+\frac{1}{2})^{n} \ge 1 + \frac{n}{2}$ for every $n \ge 1$ My base case is $n=1$ Inductive step is $n=k$ Assume $n=k+1$ $(\frac{3}{2})^{k} \times \frac{3}{2} \ge (1 + ...