Questions tagged [proof-writing]

For questions about the formulation of a proof. This tag should not be the only tag for a question and should not be used to ask for a proof of a statement.

Filter by
Sorted by
Tagged with
0 votes
1 answer
107 views

Error in demonstration of $(a-b)^{2} \ge 0$

It's a fact that: $\frac{a+b}{2} \ge \sqrt{ab}$ When a and b are non negative real numbers. What's the error in the following demonstration: $\frac{a+b}{2} \ge \sqrt{ab}$ , then $a+b \ge 2\sqrt{ab}$ , ...
0 votes
0 answers
21 views

Validating Existing Mathematical Proofs: Exercises? [closed]

I'm looking for exercises where I'm given a proof for a statement, and I need to determine if the proof is correct or not. This will help me get better at understanding and evaluating proofs. Thanks ...
0 votes
0 answers
12 views

Insertion Sort Proof by Induction [closed]

I am taking an algorithms class and for my exams, I need to understand how to do proofs for 12 different algorithms including insertion sort. Can someone give a somewhat simple-to-understand proof of ...
4 votes
2 answers
5k views

Proof: $a < \sqrt{ab} < \frac{a+b}{2} < b$

I am currently working on spivak calculus 4th edition. One of the problem asks the following: Prove that if $0 < a < b$ $$ a < \sqrt{ab} < \frac{a+b}{2} < b$$ Here is how I wrote it: If ...
1 vote
3 answers
136 views

Inductive proof that $2^n $ is bigger or equal to $1+n$

I'm studying proofs by induction and I wonder if what I did constitutes a solid proof or not. I know the three steps to conduct an inductive proof, so I will write down what I did. Base case: n=1 $2^...
0 votes
2 answers
70 views

Rationale behind Conditional Proof

For some time now, I have been able to use the Conditional Proof rule in Natural Deduction. We assume A, derive B within the scope of the assumption and discharge the assumption to get that A implies ...
2 votes
3 answers
2k views

Show every bounded infinite set has a maximum limit point and a minimum limit point.

Show every bounded infinite set has a maximum limit point and a minimum limit point. Here is my thought even if it is not formal Let $S$ be bounded and infinite set. Bolzano–Weierstrass theorem: ...
-1 votes
0 answers
27 views

Limit summation via induction [closed]

Prove that $\displaystyle \lim_{x\rightarrow +\infty}\sum_{n=1}^{x}\frac{1}{x+n}=\ln 2$. I'm not sure how to prove the base case, let alone the induction hypothesis and so forth. Can someone please ...
3 votes
0 answers
39 views

Prove that a Lebesggue outer measure on $\mathbb{R}^d$ is an outer measure which assigns to each $d$-dimensional interval its volume.

I just started to self-study some measure theory. I need to prove the following proposition Proposition$\quad$ Lebesgue outer measure on $\mathbb{R}^d$ is an outer measure, and it assigns to each $d$-...
0 votes
3 answers
40 views

Explanation needed for Hammack's Introduction to Proof Example 1.2 {7a+3b : a,b ∈ Z}

I'm having trouble understanding what Hammack means with this and how he arrived at the result. Solution: This set contains all numbers of form 7a + 3b, where a and b are integers. Each such number ...
-1 votes
1 answer
58 views

Struggling with writing proofs [closed]

I am a first year student currently taking a discrete math course. I can understand proofs in the solution. But when it's my time to write proofs, I am struggling with applying the ideas/techniques I ...
0 votes
0 answers
25 views

Prove that If a < b and c < d then a + c < b + d [duplicate]

I'm currently on a calculus book. It starts with inequalities and the rules of it. So there is my question: If a < b and b < c, then a < c. If c is any number and a < b, then it is also ...
2 votes
2 answers
1k views

Finite union of countable sets is countable.

Question Is my proof that the union of countable sets is countable correct? If $A_1, A_2, A_3,\dots, A_n$ is a collection of countable sets, then the union: $$A_1\cup A_2\cup A_3 \cup \dots A_n$$ is ...
5 votes
5 answers
903 views

Sum of squares are closed under products and squaring.

For any natural number $n\ge 1$, given pairs $(a_1,b_1),(a_2,b_2),...,(a_n,b_n)$ of integer numbers, there exist integer number $c$ and $d$ such that $$\prod_{i=1}^{n}(a_i^2+b_i^2) = c^2+d^2$$ My ...
-2 votes
4 answers
71 views

why is the co-prime part not mentioned in the definition of the rational number?

Proving $\sqrt{2}$ an irrational number is a quite popular exercise, in precalculus courses, but if we look clearly the definition that is introduced, in the beginning of the course, it never ...
-2 votes
0 answers
43 views

If $f: A \to B$ and $g: B \to C$ are bounded functions, then $g \circ f$ is bounded [closed]

If $f: A \to B$ and $g: B \to C$ are bounded functions, how would I prove that $g \circ f$ is bounded?
1 vote
0 answers
22 views

Extra-axiomatic true statements for proving a theorem?

So, my question is about proving theorems and the axioms needed to prove the theorem. My understanding is that, in the theorem statement there are certain axioms and one conclusion we have to prove. ...
1 vote
1 answer
28 views

Lemma to Prove Euclid's Lemma (a and c integers and t the smallest positive integer such that c | at, then t | c)

I came across a proof of Euclid's Lemma from https://www.sci.brooklyn.cuny.edu/~mate/misc/euclids_lemma.pdf that used another lemma to assist in the proof: Let a and c be positive integers and let t ...
-2 votes
1 answer
95 views

How can you prove an inductive case of $n^2 < 2^n$? [duplicate]

I'm trying to prove that $n^2 < 2^n$. I see this proof question from the example of 2.5.3 here. I understand that when you prove an inductive case where $P(k+1)$ is true, you have first to assume ...
0 votes
2 answers
2k views

Inequality Proof by Contradiction

I need help setting up the following proof: Prove that $0 ≤ a < b$ implies $0 ≤ a^2 < b^2$ and $0 ≤ a^{(1/2)} < b^{(1/2)}$. I am thinking proof by contradiction is the right method, I just ...
0 votes
1 answer
40 views

How to write a clear proof that if $N$ is a normal subgroup whose quotient group is abelian, the commutator subgroup is a subset of $N$?

I'm trying to find the right level of explicitness to use when writing algebra proofs. The challenge is that algebra proofs, once complete, can often devolve into simply a series of equations. But ...
-3 votes
1 answer
51 views

Proof using Contrapositive arguments

Prove that if $(3x + 1)/333$ is a rational number, then x is also rational. I'm using only Contrapositive method to prove the statement above. So I learnt that for contrapositive, we use $p \to q \iff ...
0 votes
1 answer
63 views

Is the statement "$f$ is continuously differentiable over a closed set" mathematically incorrect?

For example, I am currently reading a sentence that writes: "let $f$ be a continuously differentiable function over a closed and convex set $C$." Sentence of this type appears everywhere in ...
3 votes
3 answers
358 views

How to prove that $\text{erf}\left(\frac{x}{\sqrt{2}}\right)\geq\left(1-\frac{1}{x^2}\right)$ for $x>0$?

Having in mind that the error function is a function such that: $$\text{erf}(x)=\displaystyle\int_0^{x}\frac{2}{\sqrt{\pi}}e^{-u^2}du$$ Graphically I can see that for $x>0$ $$\text{erf}\left(\frac{...
0 votes
1 answer
34 views

How to show that the set of minimizers for a convex function over a convex set is closed?

It is well known that the set of minimizers of a convex function over a convex set is convex. It is also true that it is closed. But I have not been able to show this result. Let $f$ be a convex ...
0 votes
0 answers
165 views

Writing a Hilbert-style Proof for $(A ∧ (¬B)) ⊢ (¬(A → B)$

I've been trying to write a Hilbert-style proof using the Axioms and Rules of Inference for propositional logic, but I keep getting stuck at step 3. $$(A ∧(¬B)) ⊢ (¬(A → B)$$ $(A ∧ (¬B))$ (...
-2 votes
1 answer
28 views

Writing two similar statements in one theorem [closed]

I want to write in one theorem two statements which have the following general form: (a) If $x\in A$, then $x$ can be uniquely expressed as the sum $x=a_1+\ldots+a_n$, where $a_j\in A$ for each $j$. (...
3 votes
1 answer
176 views

Proofs with shift operators

Here, the Ramanujan Master Theorem is proven in the following way: $$ \begin{split} \int_0^\infty x^{s-1}\sum_{n=0}^{\infty}\frac{(-1)^n}{n!} \lambda(n)x^n & = \int_0^\infty x^{s-1}\sum_{n=0}^{\...
5 votes
0 answers
36 views

Question About The Generation of The Borel $\sigma$-Algebra on $\mathbb{R}^d$

I am new to measure theory. I was asked to prove the following result: Proposition$\quad$ The $\sigma$-algebra $\mathcal{B}(\mathbb{R}^d)$ of Borel subsets of $\mathbb{R}^d$ is generated by each of ...
2 votes
1 answer
120 views

Understanding the method for the proof of compactness theorem

In Sets, Logic, Computation, the compactness theorem is stated as follows: For any sentences $\Gamma$ and $A$, the following holds: $\Gamma\models A$ iff there is some finite $\Gamma_0\subseteq\...
-3 votes
0 answers
31 views

Absolute value ineq./equality [closed]

Prove either of them is the case.
0 votes
1 answer
49 views

Prove that the inverse of the inverse of a matrix A is equal to A

I've written a proof of $ (A^{-1})^{-1} = A $, but I'm worried it's a circular argument. Please let me know if this is solid. I would also be interested if you have any other proofs of this property. ...
0 votes
1 answer
36 views

Prove that if X is a subspace and Y is a subspace, then X+Y is a subspace.

I'm doing a proof and I'm not sure if the logic is completely sound. Proposition: If X is a subspace of V and Y is a subspace of V, then X + Y is a subspace of V. Proof: Let $ a,b \in X,$ and $l,k,...
-2 votes
0 answers
31 views

Proof for a^n - 1 = 1. [duplicate]

I'm reading this book: https://doc.lagout.org/science/0_Computer%20Science/2_Algorithms/The%20Art%20of%20Computer%20Programming%20(vol.%201_%20Fundamental%20Algorithms)%20(3rd%20ed.)%20%5BKnuth%201997-...
0 votes
3 answers
200 views

Is this proof of the principle of recursion theorem proving anything?

The following is presented as an example to motivate my question. It's my paraphrase of the principle of recursion theorem and proof. From Fundamentals of Mathematics Foundations of Mathematics: The ...
1 vote
3 answers
558 views

$\matrix {AB}=\matrix 0$ and $\matrix A\not= \matrix 0$, then $|\matrix B|=0$ ?!

Let $A$ and $B$ be two square matrices such that $\matrix {AB}=\matrix 0$, where $\matrix 0$ denotes the Null Matrix. My textbook mentions that [without proof]: if $\matrix A\not= \matrix 0$, then $|\...
-1 votes
2 answers
48 views

Proving nice divisibility [duplicate]

Let $n=10x+y$ where $n$, $x$ and $y$ are positive integers. Prove that $n$ is divisible by $13$ iff $x+4y$ is divisible by $13$. I let $n=13k$, thereafter mutliplied $x+4y$ by $10$, to get $10x+40y$ ...
-1 votes
1 answer
41 views

performing induction on $b_{n+1}=1+\sum_{r=1}^{n}b_{r}^{2}$ [closed]

A sequence is defined by $b_{1}=1$ and $b_{n+1}=b_{n}\left(b_{n}+1\right)$. Prove that for each n: $b_{n+1}=1+\sum_{r=1}^{n}b_{r}^{2}$
-1 votes
0 answers
20 views

Proving a contrapositive statement for Mersenne primes [duplicate]

Prove that: If n is not prime, $2^{n}-1$ is not prime. I tried to make a sub, but that's unfeasible, so not sure what to do now.
0 votes
4 answers
439 views

Infinite limit proof

Prove that $\lim_{x→+∞} \ln ⁡x =+∞$ I know that $f(x) = \ln x$ can be written as $\ln x$ if $x>1$ and $0$ if $x=1$ Do these have any useful to prove the limit above?
1 vote
1 answer
78 views

Show if $a$ has infinite order, then $a^i = a^j$ if and only if $i = j$

My abstract algebra textbook as the following part of a theorem that it almost treats as trivial, and I want to prove this myself: Theorem. Let $G$ be a group, $a \in G$ and $i, j \in \mathbb{Z}$. If $...
0 votes
0 answers
21 views

A question about Introduction online convex optimization Ch2 Ex4

The problem: Let $\mathcal{K}\subset R^d$ be a closed and bounded set. $\mathcal{K}$ is a convex set if and only if $\forall x\in R^d, |P_{\mathcal{K}}(x)| =1$ (always exist a unique projection point)....
1 vote
0 answers
19 views

Proof of this subaditivity-related measure-theory inequality

I have bumped into this problem in the introduction of Measure-theory notes. Let $(X,\mathcal{M},\mu)$ a finite measure space and let $(A_n){n\in\mathbb{N}}$ , $(B_n){n\in\mathbb{N}}$ two sequences ...
0 votes
0 answers
83 views

A new topology on $\Bbb{Z}$ based upon basis $X_d = $ the insolubility of $x^2 = 1\pmod d$ etc

Let $p_n$ denote the $n$th prime throughout and define $p_n\# := p_n p_{n-1} \cdots p_1$ to be the $n$th "primorial". Define the topology $\tau$ on $\Bbb{Z}/p_n\#$ to be that generated by ...
2 votes
1 answer
82 views

Abbott: Which type of proof is this?

Let $x_1=2$ and define $$ x_{n+1}:=\frac{1}{2}\left(x_n+\frac{2}{x_n}\right).$$Show that $x_n^2\geq 2$. This was my working Suppose inductively that $x_n^2\geq 2$ for some $n\in \mathbb N$. Then $$x_{...
0 votes
2 answers
52 views

Measurability of the set of elements who belong to a infinite amount of subsets in a sequence [closed]

I've been struggling to prove the following statement: Let (X,$\mathcal{M}$,$\mu$) a finite measure space and let $(A_n)_{n\in\mathbb{N}}$ a sequence of measurable sets in X. Now consider $M$ the set ...
0 votes
1 answer
53 views

For any square-free $n \geq 1$ and $a \in \Bbb{Z}/n$ including $\gcd(a,n) \neq 1$, then in the list $a, a^2, a^3, \dots$ either $a$ or $a^2$ repeats?

For example, modulo $30$ we have that $\gcd(5, 30) = 5$, but $5, 5^2, 5^3 = 5, 5^2, \dots$ goes the list, so both repeat. We know it's true when $\gcd(a,n) = 1$ because a cyclic group is formed in $\...
3 votes
3 answers
181 views

Are all "without loss of generality"-questions logic-based?

This Wikipedia article and AoPS page have the same proof that is an example of WLOG. These and other WLOG proofs seem to be connected with logical statements. Am I wrong? However, a question I asked a ...
9 votes
6 answers
4k views

Show that $\gcd(a, 0)$ exists and equals $|a|$ for all $a$ in $\mathbb Z$

I came up with the proof in the paragraph below. My question is about how I expressed the proof, and about the first part of the question above. For one, my proof seems to me very wordy compared to ...
0 votes
1 answer
33 views

How do we get this approximation

Show the following relationship: $\int_{-\infty}^{\infty} \Phi(\lambda x) N(x | \mu, \sigma^2) \, dx = \Phi\left(\frac{\mu}{\sqrt{\lambda^{-2} + \sigma^2}}\right)$ Hint: One way to solve this is to ...

1
2 3 4 5
316