For questions about approaches and techniques for discovering a proof, as opposed to writing it down clearly (which involves (proof-writing)). Should not be used unless the focus is on the technique of the proof instead of the solution.

learn more… | top users | synonyms

3
votes
1answer
33 views

Partitioning a totally ordered set into three subsets according to the order

Consider a set $S$, and a total order $R$ over that set. Part (a) Given some element $e \in S$, explain why it is possible to partition $S$ into the following three sets: $$S_1 = \{ x \in S ...
4
votes
0answers
76 views

How to find $f$ and $g$ if $f\circ g$ and $g\circ f$ are given?

The question is: Let $f:\mathbb R\rightarrow \mathbb R$ and $g:\mathbb R\rightarrow \mathbb R$ be two functions such that $(f\circ g)(x)=4x^2+4x+1$ and $(g\circ f)(X)=x^2+2x+2$. Find $f(x)$ and ...
-2
votes
1answer
45 views

Set Theory Proof [closed]

How can I prove that $A \cup B = A \cup (A'B)$ It is a useful identity when proving : $ P(A \cup B) = P(A)+P(B)-P(AB)$ But I don´t know where that identity comes from. Is there an analytical proof ...
1
vote
4answers
132 views

If $G$ is a non-cyclic group of order $n^2$, then $G$ is isomorphic to $\mathbb{Z_n} \oplus \mathbb{Z_n}$

I've independently come up with a question (I know it's been asked before, but I can't find the question online) involving the external direct product, non-cyclic groups and isomorphisms. So, is the ...
32
votes
5answers
2k views

Examples of “Non-Logical Theorems” Proven by Logic

I am still an undergraduate student, and so perhaps I just haven't seen enough of the mathematical world. Question: What are some examples of mathematical logic solving open problem outside of ...
4
votes
2answers
145 views

Prove that $\sqrt{n} \le \sum_{k=1}^n \frac{1}{\sqrt{k}} \le 2 \sqrt{n} - 1$ is true for $n \in \mathbb{N}^{\ge 1}$

I'm trying to solve these induction exercises proposed by the department of mathematics of Oxford University. I don't know how to give a valid proof for the third one which says the following: ...
0
votes
3answers
26 views

A property regarding intervals

While I was solving a problem on TopCoder I used the following assumption. I have n intervals: $ [a_1,b_1], [a_2,b_2],...,[a_n,b_n]$ and a number $T$ such that: $$ a_1 + a_2 + ... + a_n \leq T \leq ...
0
votes
1answer
55 views

A question about the proof of an obvious result

This is obviously true that a local homeomorphism is a continuous map. I tried to prove it this way : Suppose $f:X \to Y$ is a local homeomorphism, then $f$ is continuous if for each $x\in X$ and ...
1
vote
0answers
13 views

Finding posterior of normal distributions and logistic regression.

$P(w_0 | x) = \frac{1}{1 + e^{-log\frac{P(x|w_0)}{P(x|w_1)}-log\frac{P(w_0)}{P(w_1)}}}$ Note: x = $[x_1, \dots, x_d]^T$; a $d$ dimensional vector. $w$ can take on one of two values: $w_0$ or $w_1$. ...
0
votes
0answers
45 views

A question related to the Descartes-Frenicle-Sorli conjecture on odd perfect numbers

Good day to everyone! I apologize in advance for the somewhat long post, but I had to put in all the details into a single question to communicate what I believe to be a viable approach to odd ...
1
vote
1answer
60 views

Proof that ordinary multinomial coefficients rise monotonically to a maximum and then decrease monotonically

While most computations of ordinary multinomial coefficients for the following case require recursive summations, I found here a closed-form solution: $$(1+x+x^2+\cdots+x^q)^L = \sum_{a \geq 0} ...
6
votes
1answer
79 views

Alternative proof for the fact that a continuous function on a closed interval attains its boundaries.

Let $f:[a,b]\to \mathbb{R}$ be a continuous function. We are interested in showing that $\exists \beta \in [a,b]$, such that $f(\beta) = M$, where M is its upper boundary. I have managed to proof ...
7
votes
4answers
197 views

Let $a_n$ be the $nth$ term of the sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, \dots$

Question:Let $a_n$ be the $nth$ term of the sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6\dots$, constructed by including the integer $k$ exactly $k$ times. Show that $a_n = ...
0
votes
1answer
79 views

Quick question about $\epsilon -\delta$ proofs

There is one step in $\epsilon - \delta$ proofs that I hope somebody could bring clarity to for me. Say we wanted to show $\displaystyle \lim_{x \to 2} x^2 = 4 $. Somewhere along the proof we would ...
2
votes
3answers
53 views

Considering $\epsilon$ intuitively in limit proof

I'm having rather difficult time in trying to use $\epsilon$ argument appropriately. For example here is my simple $\epsilon$ proof in one question. The question is as follow: Prove if $s_n \geq 0$ ...
1
vote
2answers
88 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: ...
1
vote
2answers
84 views

Better proof that $n \leq 2n$ for all natural numbers?

I tried proving via induction on naturals that $n \leq 2n$ for each natural $n$. Obviously, $0 \leq 2(0)$, and then assuming for any given $n$, $n \leq 2n$, you just show that $n + 1 \leq 2(n + 1).$ ...
0
votes
1answer
31 views

Prove $\alpha: \mathbb{Z_n} \rightarrow \mathbb{Z_n}$ defined by $\alpha(s)=rs\mod{n}$ is an automorphism.

I'm working on proving the following claim: "Let $r \in U(n)$ and $\forall s \in \mathbb{Z_n}$, $\alpha: \mathbb{Z_n} \rightarrow \mathbb{Z_n}$ defined by $\alpha(s)=rs\mod{n}$ is an automorphism." ...
1
vote
2answers
53 views

Discrete Mathmatics Proof

Here is the question: $a$ and $b$ are any two integers. $c$ is any prime. Prove that if $c$ divides $ab$, then $c$ divides $a$ or $c$ divides $b$ (or both, as in it can divide either or both, i.e. ...
0
votes
2answers
33 views

Proof d-regular graph has an equal number of vertices in its bipartition

Let $G$ be a $d$-regular graph. Suppose that $G$ is bipartite with bipartition $(A,B)$. Prove that if $d>0$ then $|A| = |B|$. Also why is this statement false when $d=0.$ I'm not sure how to show ...
0
votes
1answer
46 views

How to show $f(x,y) \leq \theta f(x,y) + (1-\theta)f(x,y)$ for $\theta \in [0,1]$?

Let $\theta \in [0, 1]$. Let $f(x,y)$ be a function. Is there a way I could prove that $f(x,y) \leq \theta f(x,y) + (1-\theta)f(x,y)$? I have tried to start with $f(x,y) = 2f(x,y) - f(x,y)$ or ...
3
votes
2answers
348 views

How to find the period of the sum of two trigonometric functions

I want to know if there exists a general method to find the period of the sum of two periodic trigonometric function. Example: $$f(x)=\cos(x/3)+\cos(x/4).$$
0
votes
2answers
52 views

Proof exercise: finding hypothesis and conclusion in a statement

I am starting learn mathematical proofs and I was doing some exercise that needed to identify the hypothesis and the conclusion in a given statement. And I'm having trouble trying to figure it out in ...
2
votes
1answer
59 views

Proof: $(\sup(A) - \epsilon)^n<y<(\sup(A)+\epsilon)^n$

Prop.: let be $y \in \Bbb{R}_{>0}$, $n \in \Bbb{N}_{>0}$, and $A \subseteq \Bbb{R}$, then: $$A=\{x| x \in \Bbb{R}_{>0}\wedge x^n \leq y \} \Rightarrow (\sup(A) - \epsilon)^n< ...
6
votes
1answer
133 views

Coming up with short “magical” proofs

I was reading the solution to this problem: Prove that $f(n) = 2n$ is the only non-constant solution to $2f (m^2 + n^2 ) = (f (m))^2 + (f (n))^2 .$ The solution used these identities, pulled out of ...
1
vote
1answer
25 views

Solutions depending on something continuously

Let $V$ be a a real Banach space, $K \subset V$ a closed convex set, $A: K \rightarrow V^{*}$ a (nonlinear) operator and $F \in V^{*}$. Then the variational inequality is the following problem: find ...
0
votes
3answers
171 views

Proof by contradiction using counterexample

Why can't we use one counter example as the contradiction to the contradicting statement? Example: Let a statement be A where a-->b. We can prove A is not true by finding a counter example. Now, in ...
2
votes
3answers
39 views

Proof involving lcm and biconditional statement.

Suppose $a,b\in\mathbb{Z}$. Then $a = \operatorname{lcm}(a,b)$ if and only if $b\mid a$ Unsure of how to approach this problem.
2
votes
0answers
63 views

Can we always give a direct proof? [duplicate]

This is something I was wondering about for quite a while. Is it possible to construct a statement that can only be proven by using 'proof by contradicition' or contraposition? Or to put it ...
0
votes
3answers
38 views

Proof for a non-conditional statement

I'm having a bit of trouble doing this proof. If $a\in\mathbb{Z}$, then $a^3 \equiv a \pmod 3$. I know how to do proofs if there were conditional statements but not sure how to prove this with ...
0
votes
1answer
41 views

proving{$\neg(\forall x)\alpha \rightarrow \alpha$}$\models$$(\forall x)\alpha$

prove {$\neg(\forall x)\alpha \rightarrow \alpha$}$\vdash\space(\forall x)\alpha$ Im not sure what is the convention, so to be clear I am talking about proving the formula from the seven axiom ...
4
votes
1answer
81 views

how to solve this elementary induction proof: $\frac{1}{1^2}+ \cdots+\frac{1}{n^2}\le\ 2-\frac{1}{n}$

this is a seemingly simple induction question that has me confused about perhaps my understanding of how to apply induction the question; $$\frac{1}{1^2}+ \cdots+\frac{1}{n^2}\ \le\ 2-\frac{1}{n},\ ...
1
vote
1answer
52 views

Why does secant method converge

Assume $f$ is continuous and twice differentiable on $[a,b]$ such that $f'(x)>0$ and $f''(x)>0$, $x \in [a,b]$. If $f(b)>0$ and $f(a)<0$ and I choose $x_0=a$,why are we gauraunteed ...
0
votes
1answer
29 views

Largest $k$ such that $(p-k) = \lceil \sqrt{(p-2k) p} \rceil$

Assume $p \in \mathbb P.$ Assume $0<p-2k<p$ and the next square larger than $p(p-2k)$ is $(p-k)^2$. It is trivial to show that $p(p-2k)+k^2$ is a square. Simply $p(p-2k)+k^2 = (p-k)^2.$ ...
0
votes
2answers
171 views

Proof of application of Mean Value Theorem

Two bicyclists begin a race at 8:00AM. They both finish the race 2 hours and 15 minutes later. Prove/explain that at some point during the race, the bicyclists are traveling at the same velocity. So ...
1
vote
1answer
46 views

Proving the Well-Ordering Property

My textbook states the Well-Ordering property as following: If $A$ is any nonempty subset of $\mathbb{Z}^+$, there is some element $m \in A$ such that $m \le a$, for all $a$ in $A$ ($m$ is called ...
2
votes
2answers
66 views

Number of conjugacy classes in finite groups

Let $G$ be a finite group. Let $C_1,C_2,\dots,C_k$ be its conjugacy classes. We denote by $C_{j\ '}=\{g^{-1}|\ g\in C_j\}$ the conjugacy class inverse to $C_j$. Set $$a_{rst} = ...
5
votes
1answer
159 views

To prove this complex polynomial has all zeros on unit circle

I'm trying to prove a self-inversive polynomial $P(z) = \sum\limits_{n=0}^{N-1}a_nz^n$ has all its roots on the unit circle. The coefficients are such that $ a_n = e^{j(n-\frac{N-1}{2})\pi u_0} - ...
1
vote
1answer
49 views

Is this sufficient for linear independence proofs??

I've been doing all of these proofs the same basically, I just want to make sure I'm doing them right, I didn't include all the details but I have the outlines of my proofs here. 1) U and W are ...
1
vote
0answers
68 views

Prove: $a^m\cdot a^n \cdot a^p=a^{m+n+p}$

How can I prove the following: Prop.: let be $m,n,p \in \Bbb{N}$ and $a \in \Bbb{R}$ then $$a^m\cdot a^n \cdot a^p=a^{m+n+p}$$ ??? I thinked by induction and I must prove: 1) $a^0\cdot a^0 \cdot ...
1
vote
2answers
49 views

Invertible Proof with transposed matrices

Let A, B, C be square matrices that are invertible. Say I want to express X with no inverses Say $$ (A^{T}A)^{-1}(X +B^ {T})(C^{-1}B^{-1})^{T} = I. $$ I know that $A^{T}A$ = $I$, but where can I go ...
0
votes
3answers
197 views

Sum of invertible matrices proof

If we have two square matrices, $A$ and $B$. Assume that $A + B$ is invertible. Would that mean that $A^{-1} + B^{-1}$ is invertible too?
0
votes
2answers
30 views

Matrix chain product

I’m Reading a book , and I’m stuck at a property of a product of matrix chain , it says that given $$A_{i..k }=A_{i}\times A_{i+1}\times A_{i+2} \times ...A_{k}$$ where every matrix is a ...
2
votes
2answers
42 views

Proof About Division of Integers

Here is a problem I just finished working on: Prove that if $n$ is composite then there are integers $a$ and $b$ such that $n$ divides $ab$ but not $n$ does not divide either $a$ or $b$. One ...
2
votes
4answers
466 views

Proving 7n+5 is never a cubic number?

This is from a question that starts with: An arithmetic progression of integers an is one in which $a_n=a_0+nd$, where $a_0$ and $d$ are integers and n takes successive values $0, 1, 2, \cdots$ Prove ...
1
vote
2answers
77 views

How to deal with equivalences in proofs?

There is a part I need clarification on regarding the use of equivalence and its symmetry. From what I understand in regards to symmetry is that: $ (p \equiv q) \equiv (q \equiv p) $. Given p and q ...
1
vote
4answers
349 views

Proof that arithmetic mean is greater than geometric mean? [duplicate]

I have to prove that $\frac{x + y}{2}> \sqrt{xy}$ algebraically for any $x,y \in \mathbb{R}$ such that $x,y \ge 0$ and $x\ne y.$ I'm fairly confused as to how to solve this problem algebraically, ...
4
votes
2answers
109 views

Suppose $f: X \rightarrow Y$, and is one-to-one, and let $A \subseteq X$, prove that $f^{-1}[f[A]] = A$. [duplicate]

Suppose $f: X \rightarrow Y$, and is one-to-one, and let $A \subseteq X$, prove that $f^{-1}[f[A]] = A$. EDIT: Actually, this identity should hold even if $f$ is not one-to-one (injective), right? ...
1
vote
0answers
47 views

Real Hardy space question

Please see this related question for the definition of the grand maximal function and the class of normalised test functions $\mathcal{T}$. I will refer to them in this question. Let $f\in ...
3
votes
3answers
64 views

Prove that $2n+1 \leq 2^n$ for $n \geq 3$ using mathematical induction.

Question: $2n+1 \leq 2^n$, for all $n \geq 3$ I've tried: Basis: $P(3) = 7 \leq 8 $, so basis step is valid Pick an arbitrary value from the universe, $k \geq 3$ Inductive Step: $2k + 1 \leq ...