For questions about the writing of proofs. But instead of focusing the mathematics behind the proof, these questions ask about the details and implementation of the proof.

learn more… | top users | synonyms

0
votes
3answers
65 views

If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$.

If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$. Also... $a,b$ and $n$ are natural numbers. I feel I should begin with EEA to multiply out the gcd's, but I don't know where to go from ...
0
votes
1answer
60 views

Showing that $E[X|X<x]$ is smaller or equal than $E[X]$ for all x

I would like to show that: $\hspace{2mm} E[X|X<x] \hspace{2mm} \leq \hspace{2mm} E[X] \hspace{2mm} $ for any $x$ X is a continuous R.V. and admits a pdf. I'm guessing this isn't too hard but I ...
0
votes
2answers
67 views

Bi-implication theorem proving

While proving a theorem, i came across a situation like as follows (P has a property) $\leftrightarrow $ $(x=y)$ (P has a property) $\leftrightarrow $ $(y=z)$ Now can i infer the following fact ...
0
votes
5answers
45 views

How to prove this is true?

The question is: Show that $$\log_2(n!)\in O(n \log_2(n)).$$ I'm guessing I'll have to use principle of simple induction for this one. But how would I go about writing the proof for this? Should I ...
1
vote
1answer
84 views

How we got $z\cdot(x+y)=x\cdot y$

This is from "Test of math at 10+2 level": A vessel contains $x$ gallons of wine and another contains $y$ gallons of water. From each vessel $z$ gallons are taken out and transferred to the other. ...
0
votes
1answer
114 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 ...
2
votes
2answers
48 views

How would I go about proving this?

Question is: Let $n$ represent a positive integer. Describe the largest set of values $n$ for which you think that $2^n < n!$ I'm not sure I get this question. For $n > 3$, it seems like ...
1
vote
3answers
75 views

Show that $(x_n)$ is decreasing and find its limit.

Let $0<x_1<1$. For $n \in \mathbb{N}$, let $x_{n+1}=1- \sqrt{1-x_n}$. Show that $(x_n)$ is decreasing and find its limit. I did: $$x_{n+1} = 1- \sqrt{1-x_n}$$ $$x_{n+1} - x_n= 1- \sqrt{1-x_n} - ...
1
vote
2answers
50 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$ ): ...
1
vote
2answers
116 views

proof that $\sum_{k=2}^{\infty} \dfrac{H_k}{k(k-1)} $ where $H_n$ is the sequence of harmonic numbers converges?

How to prove that $$\displaystyle \sum_{k=2}^{\infty} \dfrac{H_k}{k(k-1)} $$ where $H_n$ is the sequence of harmonic numbers converges and that $\dfrac{H_n}{n(n-1)}\to 0 \ $ I have already proven by ...
1
vote
1answer
45 views

Proof with $\Theta$

I am having a hard time proving the following statement: Suppose that the functions $f_1, f_2, g_1, g_2 : \mathbb{N} \rightarrow \mathbb{R}^{\ge 0}\ are \ such \ that \ f_1 \in \Theta (g_1) \ and ...
0
votes
0answers
57 views

How to prove a statement that involves max and big theta?

If we have 4 functions. a,b,c,d Considering that a is in Θ(c) and b is in Θ(d) I need to prove that (a + b) is in Θ(max{c, d }). What approach do you recommend? Do I have to prove this ...
3
votes
1answer
109 views

Type Theory (Proof tree)

Suppose $B(x)$ set $(x:A)$ is a family of sets and $D$ is a set. Prove $(\Sigma x:A)B(x) \times D \to (\Sigma x:A)(B(x) \times D)$. Using the so called Curry-Howard correspondence one may ...
3
votes
2answers
83 views

Is this how you prove by induction for inequalities?

the question is here: http://cpsc.ualr.edu/srini/DM/chapters/examples/ex2.3.2.html My solution is as below:
0
votes
3answers
88 views

Proving $n^n \ge n!$, is induction necesary?

I am trying to prove that: $n^n \geq n!$ is valid for a $x$ set of numbers. So, I am trying an inductive process. However, case $P(0)$ doesn't seem to work because I have read somewhere that $0^0$ ...
2
votes
1answer
94 views

Generalized distributive laws proof feedback

I'm currently learning proofs and elementary set theory. I would like to have feedback on my proof since I'm self-studying. Are some part superfluous or unclear? My proof goes as follows: I will ...
1
vote
3answers
145 views

Prove that $\sqrt[n]{n!}$ is increasing and diverges

I have to prove that $a_n$ is (strictly) increasing and diverges $a_n = \sqrt[n]{n!}$ ; n $\in$ $\ \mathbb{N}$ From sequence I see that $a_n$ increasing to infinitive. $\sqrt[1]{1!}=1 ,\ ...
3
votes
0answers
79 views

Interchange of finite sum with convergence sequences.

Hi everyone I'm wondering if the following proof is correct (to be honest at the beginning I have some troubles to understand what the sequences of the sums of convergent sequences has to be, but I ...
0
votes
1answer
67 views

Proving a statement using simple induction.

I have this statement: Which I represent using the predicate P(n). In order to prove this I have to provide a 'first' case which satisfies this expression. Which in this example is 4. Because every ...
1
vote
2answers
146 views

Primitive Roots Proofs

I am stuck on how to prove these two questions: (1) Let r be a primitive root of the prime $p$ with $p$ congruent to $1$ modulo $4$. Show that $-r$ is also a primitive root. (2) Let n be a positive ...
1
vote
1answer
48 views

Prove or refute: $A_1,\ldots,A_n\vdash_{CPL} B \iff (A_1 \wedge \ldots \wedge A_n)\vdash_{CPL} B$

Need to prove or refute: $A_1, \ldots, A_n \vdash_{\rm CPL} B \iff A_1 \land\dots\land A_n \vdash_{\rm CPL} B$ Since we have $\iff$ operator, we have to deal with to directions. Let's begin from ...
2
votes
2answers
66 views

Prove or refute contingent: If A implies B is contingent, then B is too

The question is: If $A, A \to B$ are contingent, then so is $B$ $A, A \to B$ (implies) is a contingent, but how exactly to show «so is $B$»? If I'm using a truth table, how should I show that ...
1
vote
5answers
152 views

Given that $\alpha$ and $\beta$ are acute angles, show that $\alpha+\beta = \pi/2$ if and only if $\cos^2{\alpha} +\cos^2{\beta} = 1$.

This question is from an exam paper: Given that $\alpha$ and $\beta$ are acute angles, show that $\alpha+\beta = \pi/2$ if and only if $\cos^2{\alpha} +\cos^2{\beta} = 1$. I want to do it in ...
1
vote
1answer
42 views

If $S_n=\left[-\frac{n}{n+1},\frac{n}{n+1}\right]$ then $\bigcup\limits_{n\geq1}S_n=(-1,1)$

I was self reading Mathmatics for Economists by Simon and Blume. Consider the closed sets $S_n=\left[-\frac{n}{n+1},\frac{n}{n+1}\right]$ for $n\geq1,n\in\mathbb N$. Then ...
3
votes
1answer
151 views

Prove that there does not exist a surjective function from the set of rationals to reals.

Prove that there does not exist a surjective function f: $\mathbb{Q}\rightarrow \mathbb{R} $. I think a proof by contradiction would work which means we want to prove $$\neg (\forall{y}\in ...
2
votes
2answers
96 views

Proving a BIG-O statement? Logarithmic expressions. Simple Induction.

I have to write a proof for the following statement. $$\log_2(n!)\in\mathcal O(n\log_2(n))$$ What approach would you recommend. I am kind of LOST trying to figure this out. I transformed the ...
1
vote
2answers
68 views

How can the following mathematical statements be proven?

I have these two mathematical statements: 1) $e^{i\pi}=-1$ and 2) $\ln(-1)=i\pi$. Now I want a proof of these statements. Can anyone help me proving these statements?
4
votes
2answers
79 views

Using Results in Sobolev Spaces

I have two questions about using results in Sobolev Spaces and a last one on an inequality involving Holder spaces: 1.The Gagliardo-Nirenberg-Sobolev Inequality states the following: Assume $1 \leq p ...
1
vote
1answer
49 views

Proofs using vectors

I am entirely new to proofs, never done them for year 12, so I'm wondering how to solve these questions? This isn't homework, im preparing for an undergrad math olympiad on my own, so if you could ...
3
votes
2answers
41 views

Prove/refute: Every tautology is contingent

I'm asking to prove/refute the following statement: Every tautology is contingent. According to definition of contingent: A statement that is neither self-contradictory nor tautological is ...
1
vote
2answers
37 views

Reasoning why the implication $t - \epsilon \le x \le t + \epsilon$ for $\epsilon \ge 0 \Rightarrow x = t$ holds using sequences.

In texts I've seen the following reasoning used several times: Suppose $t - \epsilon \le x \le t + \epsilon$ holds for $\epsilon \ge 0$. Then it in particular holds for $t - \frac 1 n \le x \le t + ...
1
vote
1answer
44 views

Linear algebra: Matrix multiplication problem

I need to prove something in my homework I just don't know how to approach it and need some guidance. "Show that for a matrix $A$ ($n \times m$) and a vector $\vec{x}$ ($m \times 1$) it applies that: ...
1
vote
1answer
72 views

prove that if $L(f,P)=U(f,P)$ then $f$ is constant on $[a,b]$

Suppose that $f$ is a bounded function on $[a,b]$ and there exists a partition $P $of $[a,b] $such that $L(f,P)=U(f,P)$. Prove that $f$ is constant on $[a,b]$ I know that $L(f,P)=U(f,P)$ meaning $f$ ...
2
votes
6answers
66 views

Is the following True of False?

Provide a proof if true or a counterexample if false: Let a,b be two integers (not both zero), then the gcd(a,b) divides ay+bx for all for x,y ∈ Z. I tried with several cases such as gcd(5,10) = 5 ...
0
votes
3answers
46 views

Prove that if $F: A \rightarrow B$ and $F^{-1}$ is a function, then $F$ is one-to-one

Prove that if $F: A \rightarrow B$ and $F^{-1}$ is a function, then $F$ is one-to-one Proof: Suppose $F$ is not one-to-one. Then there exist $x_{1}, x_{2} \in A$ such that $F(x_{1}) = F(x_{2})$ where ...
0
votes
2answers
359 views

proving whether a function is one-to-one/onto

1) f(n) = 2n + 1 from set of integers to set of integers 2) f(n) = 2[n/2] from set of integers to set of integers [] is floor Could someone demonstrate how I ...
1
vote
1answer
75 views

Does $(\neg R\to R)\to R$ give rise to a proof strategy?

Take for example proof by contradiction, it can be viewed as a certain deduction in logic which can be used outside of logic to prove many interesting propositions. My question is: can we use $(\neg ...
1
vote
1answer
93 views

prove that $\int(f(x)+g(x))dx= \int f(x)dx+\int g(x)dx$

Let $f,g$ be two functions defined on $A$. Supposed that $F$ and $G$ are anti-derivative of $f$ and $ g$. Prove that $\int(f(x)+g(x))dx= \int f(x)dx + \int g(x)dx$ Here is what I got. Let $H(x)$ ...
2
votes
4answers
62 views

How do I prove a basic and obvious-looking set relations?

I'm a beginner in set theory, but the exercises asking for proof for intuitively obvious set relations like $A\cap A=A$. I don't know where to start. It will be appreciated if there is an example. ...
1
vote
0answers
63 views

Proving lower bounds from algorithmic game theory paper (specifically, price of anarchy is lower bounded by 3/2 for $m$ links)

This question is similar to Understanding proofs from paper on Game Theory (Price of Anarchy) This question is about the same proof: proving the lower bound that the price of anarchy (sometimes ...
1
vote
1answer
58 views

Prove that if $F : A \rightarrow B$ and $F^{-1}$ is a function, then $F$ is Injective

Statement: if $F : A \rightarrow B$ and $F^{-1}$ is a function, then $F$ is $1-1$ Proof: If $F$ is not $1-1$, then there exist $x_{1}, x_{2} \in A$ where $x_{1} \neq x_{2}$ and $F(x_{1}) = F(x_{2})$. ...
2
votes
0answers
41 views

Prove that $f: \mathbb{N} \rightarrow \mathbb{N}-\left \{ 1 \right \}$ given by $f(x) = x+1$ is $1$-$1$ and onto

$f: \mathbb{N} \rightarrow \mathbb{N}-\{1\}$ given by $f(x) = x+1$ is $1$-$1$ and onto. Proof: ($1$-$1$) Suppose $f(x_{1}) = f(x_{2})$ for $x_{1}, x_{2} \in \mathbb{N}$. Then $x_{1} + 1 = x_{2} + ...
0
votes
1answer
55 views

Proof by induction; simplify when adding k+1th term. Understanding induction.

I want to prove: $$(-\frac{1}{2})^0 + (-\frac{1}{2})^1 + \cdots + (-\frac{1}{2})^k + (-\frac{1}{2})^{k+1} = \frac{2^{k+1}+(-1^k)}{3\cdot2^k} + (-\frac{1}{2})^{k+1}$$ How do I simplify the last bit, ...
1
vote
2answers
43 views

Prove that if f is increasing on an interval I, then f is one to one on I.

How do I even begin to do this problem? I don't know where to even begin. The professor of the class tried to give us hints (as this is a redo to our homework) and said "The contrapositive is 'If f ...
0
votes
0answers
53 views

Help to understand manipulations on limits and integrals - $\int_a^b \! c \, \mathrm{d}x=c(b-a)$

I'm reading this proof from here: and I don't understand how to reach $$\lim_{n \to \infty} \left(\sum\limits_{i=1}^{n}c \right)\frac{b-a}{n}$$ Specifically, why are we allowed to take out ...
2
votes
4answers
70 views

Prove that for $n\ge 8$ there are nonnegative integers x and y s.t $3x+5y=n$

Prove that for every integer $n\ge 8$ there are nonnegative integers $x$ and $y$ such that $3x+5y=n$ Attempt: First of all I want to make it clear whether zero is a nonnegative integer. It ...
1
vote
1answer
58 views

Do this algorithm terminates?

Let $x \in \mathbb{R}^p$ denote a $p$ dimensional data point (a vector). I have two sets $A = \{x_1, .., x_n\}$ and $B = \{x_{n+1}, .., x_{n+m}\}$. So $|A| = n$, and $|B| = m$. Given $k \in ...
1
vote
1answer
134 views

Prove by minimum counterexample that $2^n>10n$ for $n>5$

Prove by minimum counterexample that for all integers $n>5$ the statement $2^n>10n$ is true. Attempt: Let $S$ be a set of counterexamples, $S=\{n \in \mathbb{Z_+}: 2^n \le 10n, \space ...
1
vote
3answers
58 views

When do two functions differ by a constant throughout an interval (Fundamental Theorem of Calculus)

I'm reading the proof of the Fundamental Theorem of Calculus here and I don't understand the following parts (at the bottom of page 2): I don't know how to conclude that $G(x)-F(x)=C$ for a $x \in ...
2
votes
1answer
49 views

What's the symbolic definition of the maximum value of a domain?

Lets say we have a domain S Maximum value of domain S = {S | ? ? ? ? ? ? } How could one define the possible maximum value of a set of values, symbolically?