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

0
votes
0answers
11 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 ...
0
votes
1answer
16 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 ...
2
votes
2answers
34 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
26 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
10 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 ...
3
votes
1answer
35 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
19 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
21 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
38 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
24 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 ...
0
votes
3answers
78 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
116 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
45 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 ...
20
votes
6answers
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
28 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
67 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
9 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
55 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
15 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
36 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
119 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
33 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
29 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.
0
votes
3answers
34 views

Show that $\frac{1}{2}x^{\frac{2}{x}} \rightarrow \frac{1}{2}$ as $x \rightarrow \infty$

Could someone please show me the algebraic steps in showing that $\frac{1}{2}x^{\frac{2}{x}} \rightarrow \frac{1}{2}$ as $x \rightarrow \infty$? As the way I see it $\frac{1}{2}x^{\frac{2}{x}} ...
0
votes
2answers
72 views

Proving the Ideal Generated by the Coefficients of $f(X)\cdot g(X)\in R[X]$ is $R$.

Let $R$ be a commutative ring with unity, and let $f(X),g(X)\in R[X]$. Assume the ideals generated by the coefficients of $f(X),g(X)$ are both $R$. Prove that the ideal generated by the ...
2
votes
0answers
53 views

A false conjecture by de Polignac

(This question would be similar to my other on Goldbach's conjecture so I'll change the "rules") In 1848 de Polignac claimed that "every odd integer is the sum of a prime $p$ and a power of $2$". For ...
3
votes
1answer
182 views
+50

Conjectured primality test for specific class of $N=k\cdot 6^n-1$

How to prove that this conjecture is true ? Definition : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ~\text{and}~ x ...
1
vote
0answers
26 views

On properties of linear orders

I have a simple question. Let A={a,b,c,...} be a set and > a total strict order on $2^A$. Total strict order means that for any two subsets of A, say S and S', either S>S' or S'>S but not both. The ...
1
vote
2answers
28 views

Rigorous Linear Transformation Proof

$T:V \rightarrow V$ We could also write: $T:V \rightarrow Im(T)$ The question tells us that $Im(T)=Im(T^2)$ It's intuitively obvious that this means that T then maps $Im(T)$ to itself so if you ...
3
votes
2answers
125 views

Is $f(x) = x^3 \sin \frac{1}{x} $ uniformly continuous on $(0, \infty)$?

Since the derivitive of $f$ is bounded on a neighborhood of $0$, $f$ is uniformly continuous on $(0, M)$ where $M$ is any positive number. I'd like to prove that $f$ is uniformly continuous on a ...
0
votes
1answer
21 views

If $\text{gcd}(a,561)=1$, then $a^{560}=1\mod 561$ [duplicate]

We have the factorization $561=3*11*17$. Because $\text{gcd}(a,561)=1$, there are integers $x,y$ such that $ax+561y=1$. So $ax=1\mod 561$. Since the gcd is $1$, we have $a\not \in 3\mathbb{Z}, ...
1
vote
0answers
32 views

Basic Set-Theoretic Properties from Halmos

I've been backtracking lately to make sure that I have a solid set-theoretic background before taking measure theory this fall. Here's a few facts I've come across today, and my attempted proofs. Let ...
0
votes
1answer
39 views

Proof for the coefficient of $x^n$ in $(x^0 + x^1 + \dots + x^n)^n$

Theorem: The coefficient of $x^n$ in $(x^0 + x^1 + \dots + x^n)^n$ is $\binom{2n-1}{n-1}$. How to prove this? Multinomial theorem produces the following $$ \left(\sum_{k=0}^{n} x^k \right)^n = ...
23
votes
2answers
849 views

A false conjecture by Goldbach

In 1752 Goldbach send this conjecture to Euler: "Every odd integer can be written in the form $p+2a^2$ where $p$ is a prime or $1$ and $a$ is a natural number (can be even 0)." This conjecture turned ...
2
votes
1answer
65 views

Can I assume that the dimension of a vector space is always non-negative?

I'm trying to prove that if $V$ is finite-dimensional and $U_1,...,U_m$ are subspaces of $V$, then $\dim(U_1+...+U_m)\le \dim U_1+...+\dim U_m$ through induction. For $m=1$, the inequality is trivial ...
1
vote
1answer
22 views

Zero of holomorphic function

Let $\Omega \subset \mathbb{C}$ be an open set that contains the unit ball $D$ and let $f \in \mathcal{O}(\Omega)$ a non constant map s.t. $|f(z)| = 1$ for all $z \in \partial D$. Show that $f$ has a ...
3
votes
1answer
74 views

Irrationality of ${5^{1/7}}$

I am struggling with elementary proofs, and would appreciate any feedback as to the logic and structure of my work. Show that ${5^{1/7}}$ does not represent a rational number. Suppose ${5^{1/7}}$ is ...
1
vote
2answers
78 views

Prove the Identity $\pi=2- \sum_{1}^{∞} \frac{(-1)^m}{m^2-\frac{1}{4}} $

By considering the fact that $f(\pi/2)=1$, prove the identity $\pi=2- \sum_{1}^{∞} \frac{(-1)^m}{m^2-\frac{1}{4}} $ This question was is a subsection in a chapter on Fourier series, can I use my ...