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

2
votes
1answer
41 views

Question About Proving that $\mathbb Z_p^\times$ Is Cyclic

Statement 1: Let $p$ be prime and that $m$ divides $p - 1$. If there exists an element in $\mathbb Z_p^\times$ with order $m$, then the number of elements in $\mathbb Z_p^\times$ with order $m$ ...
-1
votes
0answers
18 views

Conditional Probability on a Mixed RV

TLDR: How do you show $P(Y\in\Omega|X=x_0)=1$ when $Y$ is a mixed RV. Let $(X,Y)\to\mathbb{R}^{dx+dy}$ be a random vector distributed according to a density $f_{X,Y} (x,y)$. Let $X$ be a continuous ...
0
votes
1answer
33 views

Need help with proof with absolute value and complex numbers. [duplicate]

Had some trouble trying to prove the following problem. Prove that if $|z| < 1$ and $|w| < 1$, then $$ \frac{|z-w|}{|1-\overline{z}w|} < 1 $$ Would appreciate some help.
7
votes
3answers
285 views

Succinct Proof: All Pentagons Are Star Shaped

Question: What is a succinct proof that all pentagons are star shaped? In case the term star shaped (or star convex) is unfamiliar or forgotten: Definition Reminder: A subset $X$ of ...
-1
votes
0answers
38 views

Is this problem tractable? (In terms of the nonzero solution) [on hold]

My classmate bet me that I cannot find a closed-form nonzero solution to this problem, and claims that he can using techniques he learned in complex analysis. After working on it for a while, it seems ...
2
votes
2answers
40 views

$\{a_n\} \to a$ iff $\limsup_{n \to \infty} \{a_n\} = \liminf_{n \to \infty} \{a_n\}$

It is clear that if $$\limsup_{n \to \infty} \{a_n\} = \liminf_{\to \infty} \{a_n\},$$ then $\{a_n\} \to a$, since we can just squeeze the terms in the middle. I understand that to prove the ...
14
votes
5answers
791 views

Fibonacci number identity.

How do I see that $f_{n+1}f_{n-1} = f_n^2 + (-1)^n$, $n \ge 2$, where $f_1 = 1$, $f_2 = 1$, and $f_{n+2} = f_{n+1} + f_n$ for $n \in \mathbb{N}$?
1
vote
5answers
220 views

Proof by induction for “sum-of”

Prove that for all $n \ge 1$: $$\sum_{k=1}^n \frac{1}{k(k+1)} = \frac{n}{n+1}$$ What I have done currently: Proved that theorem holds for the base case where n=1. Then: Assume that $P(n)$ is ...
-1
votes
1answer
25 views

Use induction to prove that n! ≥ 2^(n−1) for for all integers n ≥ 1. [on hold]

Use induction to prove that n! ≥ 2^(n-1) for for all integers n ≥ 1. Hello everyone, I'm stuck on this problem right here $(k+1)! = 2^{(k+1)-1}$
1
vote
0answers
37 views

Possible proof strategy for Sendov conjecture?

Sendov's conjecture says that if all roots of a polynomial lie within the unit disk, then for every root, there exists a critical point at a distance at most one from the root. I read that Sendov ...
3
votes
3answers
34 views

Help with partitions, equivalence classes, equivalence relations.

The following definitions and results are from my textbook. A partition $\mathcal{P}$ of a set $X$ is a collection of nonempty sets $X_1, X_2, \dots$ such that $X_1 \cap X_j = \emptyset$ for $i ...
3
votes
1answer
23 views

All closed rational rays measurable implies $f$ measurable

Is the following proof correct? Let $f: X \to \mathbb{R}$ where $X$ is a measurable space. Suppose $\{x: f(x) \geq r\}$ is measurable for each $r \in \mathbb{Q}$. Then, $f$ is measurable. Proof: ...
1
vote
0answers
26 views

Proving the Leibniz Rule for Lie Derivatives of tensor fields.

I am learning some Differential Geometry on my own in preparation for a course I'm starting in October, and one of the exercises in the notes I'm using is to check that the Lie Derivative satisfies ...
0
votes
1answer
48 views

Proof for linearity on tensor products

Theorem: Let $U$ and $V$ be vector spaces. Let $\mathbf{u}^* \in U^*$. Define $\mathbf{f} : U \otimes V \to V$: $$\mathbf{f}\left(\sum_{r} \mathbf{u}_r \otimes \mathbf{v}_r\right) = \sum_{r} ...
0
votes
0answers
21 views

Property of nth root

I'm trying to prove the following result: "Let $x,y \geq 0$ be non-negative reals, an let $n,m \geq 1$ be positive integers. If $y=x^{1/n}$ then $y^n=x$." $x^{1/n}:=sup \{y \in \mathbb{R}: y \geq 0, ...
0
votes
0answers
14 views

Proof of optimal substructure for the “plus sign game”

First of all, I think there's no "plus sign game", I have just invented the name to describe the problem faster. Another thing: I thought to ask the question in these stack exchange's website because ...
1
vote
1answer
19 views

Every collection of periodic sets $A_n \subset \Bbb{N}$ (minus a common point), that avoids…

Let $\{A_n\}$ be a set of subsets of $\Bbb{N}$ each of which are periodic except for a common point. That is to say, there exists one and only one $x_0$, such that for each $n$, if $x \in A_n, x \neq ...
3
votes
3answers
46 views

Proving $[(P\lor Q)\land(P\to R)\land(Q\to R)]\to R$ is a tautology without using a truth table?

$$[(P\lor Q)\land(P\to R)\land(Q\to R)]\to R\tag{1}$$ How can I prove that $(1)$ is a tautology without using a truth table? I used the identity $$(P\to R)\land(Q\to R)\equiv(P\lor Q)\to R$$ but ...
1
vote
1answer
30 views

Validity of my proof by contradiction of converse of Pythagorean Theorem.

So in, $\triangle ABC$ it is given that $AB^2=AC^2+BC^2$. Let us assume that $\angle C\neq{90}^{\circ}$. And let us make a perpendicular $AD$ to $BC$. Now, by the Pythagorean Theorem, in $\triangle ...
0
votes
1answer
11 views

Which Function is Big-O of the Other

Given $f(n)=nlog(n)$ and $g(n)=10^{-6}n^2$, I am asked to find whether $f\in O(g)$ or $g \in O(f)$. The book claims that $f \in O(g)$, but I do not see how that is true. If it is true, there exists ...
4
votes
1answer
38 views

How to formulate the requirements that a counterexample must satisfy?

Let $p_1, p_2$ and $p_3$ be three statements. Suppose now we know that if $p_1$ is true, then $p_2$ and $p_3$ are equivalent. That is, if $p_1$ and $p_2$ are true, then $p_3$ is true, and if $p_1$ ...
1
vote
1answer
21 views

Show that if there is a function $g:Y\to X$ such that $g\circ f$ is the identity function on $X$, then $f$ is one to one.

Let $X,Y$ be nonempty sets and $f:X\to Y$ be a function. Show that if there is a function $g:Y\to X$ such that $g\circ f$ is the identity function on $X$, then $f$ is one to one. My approach is by ...
4
votes
1answer
23 views

Basic question on equivalence relations.

Show that the following relation is an equivalence relation on the given set. $m \sim n$ in $\mathbb{Z}$ if $m \equiv n\,(\text{mod}\,6)$.
2
votes
2answers
39 views

Prove function space is linearly independent.

Let $V$ the space of all funcions $f:Ŗ\rightarrow R$. Prove that the ten functions defined by $x\rightarrow |x-1|$,$x\rightarrow |x-2|$,....,$x\rightarrow |x-10|$ are linearly independent. I need ...
1
vote
1answer
31 views

Deriving the inverse Fourier transform without knowledge of the form it will take

I've run by several proofs of the Fourier inversion theorem. However, every proof I have come across starts by assuming the form that the inverse transform will take. For example, Ron Gordon's ...
1
vote
6answers
132 views

Prove the existence of the square root of $2$.

I am trying to prove the existence of the square root of $2$. I have some steps with a very vague explanation and I would like to clarify. The proof: Let $$S=\{x\in\mathbb R\mid x\geqslant 0 \text{ ...
1
vote
0answers
22 views

Showing polynomials as products of roots

How do I show rigorously that any polynomial $a_nx^n+a_{n-1}x^{n-1}+...a_1x+a_0$ can be written as $a_n(x-b_1)(x-b_2)...(x-b_n)$ for real $a_i$ and real or complex $b_i$
2
votes
1answer
117 views

Polynomial tending to infinity

Take any polynomial $(x-a_1)(x-a_2)\ldots(x-a_n)$ with roots $a_1, a_2,\ldots,a_n$ where we order them so that $a_{i+1}>a_i$ is increasing so $a_n$ is the biggest root. It doesn't matter whether ...
1
vote
1answer
73 views

Is this a valid proof of this math challenge problem?

From a fixed point P not in a given plane, three mutually perpendicular line segments are drawn terminating in the plane. Let a, b, c denote the lengths of the three segments. Show that ...
0
votes
2answers
46 views

Weird question about natural numbers. Obvious or not?

Given any subset $A,C \subset \Bbb{N}$, there exists a maximal subset $B \subset \Bbb{N}$ such that for all $b \in B, a \in A, \ |b - a| \in C$. For instance $A = \{3,5\}$, $C = \{2,4\}$, then ...
25
votes
7answers
1k views

We all use mathematical induction to prove results, but is there a proof of mathematical induction itself?

I just realized something interesting. At schools and universities you get taught mathematical induction. Usually you jump right into using it to prove something like $$1+2+3+\cdots+n = ...
0
votes
1answer
30 views

Show that (c,a)=(c,b)

In my book I have the implication: If $gcd(a,b)=1$ and $c|(a+b)$, then $gcd(c,a)=gcd(c,b)=1$. It gives me a hint that begins by supposing that $gcd(a,c)=gcd(b,c)=d$. But in my opinion, I do not ...
1
vote
1answer
33 views

Find all primes $p$ for which $x^2+2x+4\equiv 0 \pmod p$ is solvable. Am I correct?

Getting ready for an exam, I would like to focus on the correctness of my solution, final results and assumptions, and would appreciate any comment regarding it or even additional ...
3
votes
3answers
68 views

If a set is countable and infinite, there is a bijection between the set and $\mathbb{N}$

I'm trying to show that if a set $S$ is infinite and countable then there is a bijection $\varphi : S\to \mathbb{N}$. Since $S$ is countable, we know that there is an injection $f: S\to \mathbb{N}$. ...
1
vote
1answer
10 views

Binomial Distribution formula

If $X\sim B(n,p)$, show that $P(X=r+1)=P(X=r) \cdot \frac{p(n-r)}{q(r+1)}$ for $r=0,1,...,n-1$ My attempt, $P(X=r+1)={_n}C_{r+1}(p)^{r+1}(1-p)^{n-(r+1)}$ How to proceed then?
0
votes
2answers
58 views

Proof for $V \cong V^{**}$

Theorem: Let $V$ be an vector space. Then the dual space of $V$'s dual space is canonically isomorphic to $V$. I am able to prove that $V$ is a subspace of $V^{**}$, the map ...
0
votes
0answers
16 views

Proving inequalities with the Archmedian property

I have to determine how large n∈N must be to ensure that (1/n)<ε is satisfied and use the Archimedean property to establish that such n exists. I know that the Archimedean property is ∀ε>0 and ...
2
votes
1answer
38 views

Cantor's diagonal argument modified version

I have the following doubt regarding Cantor's diagonal argument. First of all, the "usual case" is quite clear for me. If $X$ is some set, then we can show there is no surjection from $X$ onto the set ...
1
vote
1answer
37 views

Proving a given set is a submanifold

Let $S \subseteq \mathbb R^n$. I have been faced with showing that $S$ is a submanifold and I have some ideas but I want to get the complete picture. (Main) Question 1: What methods are there to ...
0
votes
0answers
17 views

Absolute Value Inequality of Differences

I'm hoping someone could give insight as to how I can improve my organization, and/or thought process. Show that $|a-b| \lt c$ if and only if $b -c \lt a \lt b + c$. By the statement $b - c \lt a ...
3
votes
4answers
120 views

Proving $\frac{n^n}{3^n} < n!$ for $n\ge6$ by induction

How would I prove this using mathematical induction: $\dfrac{n^n}{3^n} < n!$ for all $n \geq 6$. Here is what I have tried: $\dfrac{n^n}{3^n} < n!$ for all $n \geq 6$ Base case: ...
0
votes
0answers
35 views

Absolute Value Inequality Proof

I realize this is almost identical to another question I posted, but I wanted to ask what the distinction between the two is -- comprehension-wise (other than the $\lt$ vs. $\le$). Show that $|b| ...
0
votes
0answers
57 views

A question regarding a theorem of Erdos and Hajnal

Consider the following theorem of Erdos and Hajnal: Definition. For any set $x$, a function $f$ is called ${\omega} $-Jonsson iff $f$: $^{\omega}x$ $\rightarrow$ x and whenever $y$$\subseteq$$x$ and ...
0
votes
1answer
41 views

How to prove triangle inequality in How to Prove It Sec. 3.5 Question 12c?

(a) Prove that for all real numbers $a$ and $b$, $$|a| \le b \text{ iff } -b \le a \le b.$$ (b) Prove that for any real number $x$, $$-|x| \le x \le |x|.$$ (Hint: Use part (a).) (c) Prove that ...
3
votes
2answers
37 views

Unique Linear Map- Linear Algebra

Let $E = {e_1, . . . , e_n}$ be a basis for $\mathbb{R}^n$ , and let $v_1, . . . , v_n$ be arbitrary vectors in $\mathbb{R}^m$. Prove that there is a unique linear map $T : \mathbb{R}^n \rightarrow ...
1
vote
1answer
45 views

Absolute Value Property of Field of Real Numbers

I don't think my thought process is correct. Also, does 'if and only if' indicate that I should automatically resort to proof by contradiction? Show that ${|b|} \le {a}$ if and only if $ {-a} \le b ...
0
votes
1answer
20 views

What am I doing wrong here? Showing $\text{Ord}_{N}(a)|k\iff a^k\equiv 1 \pmod N$.

Show $\text{Ord}_{N}(a)|k\iff a^k\equiv 1 \pmod N$ where $a$ is invertible. What I did is: If $\text{Ord}_{N}(a)|k$ it is obvious. Suppose $a^k\equiv 1 \pmod N$. Not let us assume by contradiction ...
3
votes
1answer
28 views

Recognizing genuine proof obstructions

This is a meta question about mathematics. It is not inspired by an actual problem. Also, I'm not sure to what extent the distinction I'm drawing makes sense. Question: How can I decide if an ...
1
vote
1answer
31 views

Completeness Axiom Proof

Let $A_1$, $A_2$, $A_3$... be a collection of nonempty sets, each of which is bounded above. (a.) Find a formula for sup($A_1$$\bigcup$$A_2$). Extend this to sup($\bigcup^{n}_{k=1}$$A_k$). (b.) ...
1
vote
3answers
33 views

Prove that $\frac{2^{x+1}+(x+1)^2}{2^x+x^2}\rightarrow 2$ as $x \rightarrow \infty$

Could someone please show me the proof that $\frac{2^{x+1}+(x+1)^2}{2^x+x^2}\rightarrow 2$ as $x \rightarrow \infty$ I have no idea where to begin with this one. Thanks.