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
1answer
64 views

Usually, main results are called theorems, while smaller results are called propositions. Is there a name for super-immediate results?

In mathematical papers, main results are called theorems, while less central results are called propositions. But sometimes, there is a result that is so immediate, it doesn't even deserve to be ...
1
vote
0answers
58 views

Translation/proof of elementary argument of Chebyshev

My question is whether the following proof is correct and how it might be better presented. This was an exercise to translate/shorten Chebyshev's argument that $\hspace{80mm} (1)$ $\hspace{55mm}\log ...
2
votes
1answer
142 views

Why is it so difficult to prove that the discrete Fourier transform (DFT) cannot be calculated in faster time than $N \log N$?

As the title says, why is it so difficult to prove that the discrete Fourier transform (DFT) cannot be calculated in faster time than $O(N \log N)$? This is a famous open problem in ...
3
votes
0answers
64 views

Is there a proof reading website where users can submit their problems and upload their proof documents to be reviewed?

I'm just looking for a proof reading website that would allow a user to post her/his problem to be proved and her/his scanned documents to their claimed proof to the problem. I was just about to post ...
1
vote
3answers
297 views

Proving statement - $(A \setminus B) \cup (A \setminus C) = B\Leftrightarrow A=B , C\cap B=\varnothing$

I`m trying to prove this claim and I need some advice how to continue, $$(A \setminus B) \cup (A \setminus C) = B \Leftrightarrow A=B , C\cap B=\varnothing$$ what I did is: $$(A \setminus B) \cup (A ...
0
votes
2answers
76 views

Logic proof help

Can someone give me a proof that, No true claim can derive a contradiction in a consistent system of axioms, With out using a proof by contradiction
3
votes
4answers
213 views

What's $P$ and what's $Q$ in this classic proof of the irrationality of $\sqrt 2$?

In this proof extracted from the Wikipedia A classic proof by contradiction from mathematics is the proof that the square root of 2 is irrational. If it were rational, it could be expressed as ...
1
vote
0answers
42 views

Writing proofs with information-exchange basis

I am trying to write a proof that a certain algorithm cannot be calculated faster than some limit I have found experimentally (by comparing input size against the time taken by the algorithm to ...
0
votes
4answers
2k views

Proof of the statement “The product of 4 consecutive integers can be expressed in the form 8k for some integer k”

I am slowly diving into simple number theory and learning how to craft direct proofs. I needed to proof the statement "The product of 4 consecutive integers can be expressed in the form 8k for some ...
0
votes
3answers
370 views

Prove that every integer is either prime or composite

In the book I'm reading, the following proof is given for the stated theorem: Let n be any integer that is greater than 1. Consider all pairs of positive integers $r$ and $s$ such that $n = rs$. ...
3
votes
3answers
93 views

Is there a better way to write it?

I'm writting something. However I'm not good at English writting. Suppose that $X=D^\mathfrak c$. I want to express this : Let $x$ be the unique point of $X$ such that $x(\gamma)=1$ and for ...
4
votes
1answer
50 views

Inequality on Shannon's entropy

Let $P$ be a set of probabilities s.t. $\sum_{p_i \in P} p_i = 1$. Moreover, let $H(P)$ the Shannon's entropy of the set of probabilities $P$: $$ H(P) = -\sum_{p_i \in P} p_i \log_2 p_i $$ I define ...
1
vote
1answer
564 views

“Direct Proof” of the Steiner-Lehmus Theorem

The Steiner-Lehmus Theorem is famous for its indirect proof. I wanted to come up with a 'direct' proof for it (of course, it can't be direct because some theorems used, will, of course, be indirect). ...
2
votes
1answer
96 views

Equality of sets when minimizing Shannon's Entropy

Let $P = \{p_1, \ldots, p_n\}$ be a set of probabilities, i.e., $0 \leq p_i \leq 1$. $P$ is such that $\sum_{p_i \in P} p_i = 1$. I have a set of actions $\mathcal{A} = \{a_1, \ldots, a_N\}$ that can ...
0
votes
0answers
226 views

Optimality proof for greedy algorithm

Let $\mathcal{A} = \{a_1, \ldots, a_N\}$ be a set of actions that can be performed on a system $S$. Each action $a_i$, if performed, produces a gain $g_{a_i}(S)$. Moreover, the actions in ...
1
vote
3answers
200 views

Proof by Cases: $\operatorname{max}\{x,y\} + \operatorname{min}\{x,y\}=x+y$

So I'm told to "[u]se proof by cases to prove that $\operatorname{max}\{x,y\} + \operatorname{min}\{x,y\}=x+y$ for all real numbers $x$ and $y$." What does this mean?
2
votes
2answers
458 views

Discrete Mathematics: $x\leq y+\epsilon \implies x\leq y$

Let $x$ and $y$ be real numbers. Prove that if $x\leq y + \epsilon$ for every positive real number $\epsilon$, then $x\leq y$. I would like a hint as to how to prove this. Thank you. Pictorial ...
0
votes
1answer
247 views

Proof of the continuous function having tangent plane has directional derivatives

Suppose that the continuous function $f: \Bbb R^2 \to \Bbb R$ has a tangent plane at the point $(x_0, y_0, f(x_0, y_0))$ Prove that the function $f$ has directional derivatives in all directions at ...
2
votes
4answers
956 views

How to prove that $n\log n = O(n^2)$?

How to prove that $n\log n = O(n^2)$? I think I have the idea but need some help following through. I start by proving that if $f(n) = n \log n$ then $f(n)$ is a member of $O(n\log n)$. To show this ...
1
vote
0answers
235 views

Prove the Correctness of Horner's Method for Evaluating a Polynomial

I am currently studying the Skiena `Algorithm Design Manual' and need a little help with a proof of correctness. The problem goes as follows: Prove the correctness of the following algorithm for ...
2
votes
3answers
65 views

Proving that all the sets in a sequence are different

This is an example that seems to be pretty obvious but I have no idea on how to write a proof: Prove that the sets $\emptyset, \{\emptyset\}, \{\{\emptyset\}\}, \{\{\{\emptyset\}\}\},..., \{...\{ ...
1
vote
3answers
108 views

Please critique these proofs on function theorems

Let $f:A \to B$ and $C,D\subset A$ then we have the following properties: $ \space i)\space f(C\cup D)=f(C)\cup f(D)$ $ii)\space f(C\cap D)=f(C)\cap f(D)$ I tried to prove the first property with ...
0
votes
3answers
50 views

If $G$ is disconnected and the vertices $x,y$ are adjacent in $G$, then there is a vertex that isn't adjacent to $x$ and isn't adjacent to $y$.

I'm just starting graph theory and I'm trying to prove the following: Let $G$ be a simple disconnected graph with vertex set $V(G)$ and edge set $E(G)$. If $x,y\in V(G)$ and $xy \in E(G)$, then ...
1
vote
2answers
89 views

Need help with a simple math proof

Imagine an infinitely long sequence of squares where one of these squares contains a frog, and another square contains a fly. For simplicity, let's number all of the (infinitely many) squares by ...
13
votes
2answers
498 views

Proofs from the “Ugly Book”

There is a famous saying in mathematics from Paul Erdős: "You don't have to believe in God, but you should believe in The Book." "The Book" is an imaginary book in which God had written down the best ...
5
votes
1answer
289 views

What is wrong with my induction proof?

The Fibonacci sequence is defined by $a_1 = 1, a_2 = 1$ and for all $n \ge 2, a_{n+1} = a_n + a_{n-1}$. Thus the sequence begins $$1,1,2,3,5,8,13,21,...$$ prove that for all $n \ge 1, a_n < ...
3
votes
2answers
146 views

Is there a logic of sufficiency? Or goals?

This question has been substantially rewritten. Thank you to Peter Smith for pointing out some issues in the original. I hope this version is less ambiguous. In classical logic, one may argue as ...
4
votes
2answers
619 views

Is there a better alternative to the phrase, 'it holds that'?

The following phrases abound in my writing: There exists [whatever] such that [whatever]. For all [whatever] it holds that [whatever]. Lately, I've been feeling that the phrase 'it holds that' is ...
0
votes
4answers
83 views

Show that $5^n + 6^n = 0 \pmod{11}$ for all odd $n$

show that $5^n + 6^n = 0 \pmod{11}$ for all odd number $n$, but not for any even number $n$. I was not sure about this question. Do I have to pick numbers for $n$? Until I get odd number?
2
votes
2answers
131 views

Is there a way to prove a boolean operator isn't universal?

In boolean algebra, I could prove an operator is universal by implementing a NAND or NOR gate with it. But is there a way to prove a boolean operator isn't universal? I would like to know a general ...
4
votes
3answers
279 views

Coverings of Heine-Borel.

Here is an extract from https://math.uc.edu/~halpern/calc.1/Ho/Heineborelthm.pdf Some words and sentences were cut and modified to avoid wordiness Theorem: Let $\mathcal F$ be a family of open ...
1
vote
2answers
690 views

Proof Help: In a group $G$, there exists a $g$ such that $g^2 = e$ [duplicate]

I'm working through an Abstract Algebra book to teach myself, and came across the problem: Prove: If $G$ is a finite group of even order, then there exists a $g\in G$ such that $g^2 = e$ and $g ...
1
vote
1answer
56 views

Need a more elegant solution to proof

I've been working on a proof and this issue came up. Let's say I've made a claim that $ 7 \nmid 6x^2 + 13x - 5 $. It follows then that $ 7 \nmid (3x -1)(2x+5) $. But does it follow that $ 7 \nmid ...
5
votes
5answers
548 views

Prove that $(a-b) \mid (a^n-b^n)$

I'm trying to prove by induction that for all $a,b \in \mathbb{Z}$ and $n \in \mathbb{N}$, that $(a-b) \mid (a^n-b^n)$. The base case was trivial, so I started by assuming that $(a-b) \mid (a^n-b^n)$. ...
3
votes
0answers
110 views

Proving $\left\| \frac{\vec{v}}{\|\vec{v}\|}\right\| =1$, $\vec{v}\ne \vec{0}$ [duplicate]

I've been trying to prove that $\left\Vert\dfrac{\vec{v}}{\Vert\vec{v}\Vert}\right\Vert=1, \quad \vec{v}\ne \vec{0}$. This is my attempt: \begin{align} \vec{v}&\in \mathbb{R}^n, \quad ...
0
votes
1answer
77 views

Finding the ratio of two sides of a triangle with known angles

I wondered what the ratios between the sides of a triangle is, when the angles are known. So basically: $\triangle ABC$ has angles $\alpha, \beta \text{ and } \gamma$. Find $\frac{\lvert AB ...
3
votes
1answer
152 views

Divisibility by a prime number

I have been struggling with this question. It would be great if somebody can really help me out with this question: Prove that for any Prime number P > 5, there exists a K such that 1111....11 ...
0
votes
1answer
60 views

Help on Proof involving integrals

Good night. I'm starting to learn proofs and I'm facing the following question. Given the linear function $f(x)$, prove that $[\int_{0}^{1} f(x)\,dx]^2 < \int_{0}^{1}[f(x)] ^2dx$ As $f(x)$ is a ...
1
vote
3answers
451 views

Prove that $d^n(x^n)/dx^n = n!$ by induction

I need to prove that $d^n(x^n)/dx^n = n!$ by induction. Any help?
4
votes
3answers
111 views

Proof that $n \in \mathbb{N}$ by combinatorial analogue?

(Disclaimer: I'm a high school student, and my highest knowledge of mathematics is some elementary calculus. This may not be the correct terminology.) A while ago, I saw the following problem: prove, ...
11
votes
6answers
2k views

Proof that there are infinitely many positive rational numbers smaller than any given positive rational number.

I'm trying to prove this statement:- "Let $x$ be a positive rational number. There are infinitely many positive rational numbers less than $x$." This is my attempt of proving it:- Assume that ...
2
votes
1answer
235 views

Geometric proof that if n is a non-perfect square, then √n is irrational.

I know there is a geometric proof of the irrationality of √2. I thought maybe this one could be generalized for √n when n is a non-perfect square, but I could not find something like that anywhere. ...
3
votes
2answers
279 views

Archimedean Property - The use of the property in basic real anaysis proofs

I've been looking for something like this in the previous answers on the topic, but I didn't enounter anything similar, so here there is my problem. First of all, here there is the definition of ...
0
votes
1answer
61 views

Use of Without loss of generality (WLOG)

I encountered following usage of WLOG Consider problem of minimizing $E:= (y-x)^2 + \lambda |x|^\tau$ and $\tau \in (1,2)$ and optimizing variable is $x$, we can assume without loss of generality that ...
0
votes
3answers
332 views

$C⊆A$ and $D⊆B$ and A and B are disjoint, then C and D are disjoint.

Let A,B,C and D be sets. How to prove: $C\subseteq A$ and $D\subseteq B$ and $A$ and $B$ are disjoint, then $C$ and $D$ are disjoint. Could anyone please explain to me how to approach this ...
14
votes
3answers
256 views

Showing that $1^k+2^k + \dots + n^k$ is divisible by $n(n+1)\over 2$

For any odd positive integer $k\geq1$, the sum $1^k+2^k + \dots + n^k$ is divisible by $n(n+1)\over 2$. I used induction principle for the solution but cannot prove it. I took $P(k) = ...
13
votes
7answers
974 views

Prove that the additive inverse of an odd integer is an odd integer

This is a homework problem, but I don't want the answer, just a little guidance: Prove that the additive inverse of an odd integer is an odd integer. When approaching a problem like this, how ...
1
vote
1answer
536 views

$f$ is constant if derivative equals zero

Suppose $f'(x)=0$ for all $x\in (a,b)$. Prove that $f$ is constant on $(a,b)$. This seems painfully obvious, but I can't prove it rigorously. $f'(x)=0$ for all $x\in (a,b)$ means that for any ...
0
votes
1answer
29 views

Is $X$ has a strong rank 1-diagonal?

Definition 1: A space $X$ has a strong rank 1-diagonal \cite{5} if there exists a sequence $\{\mathcal U_n: n\in \omega\}$ of open covers of $X$ such that for each $x\in X$, $\{x\}=\bigcap ...
1
vote
1answer
71 views

Can you prove this three-way linear map composition?

OK, this was an example that my prof gave when talking about surjective, injective and bijective functions. I also am curious if I am approaching this the right way. (Everyone here has been a really ...