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
2answers
1k views

How do I prove the arithmetic-geometric mean inequality?

I am following along with this bare-bones proof of the arithmetic-geometric mean inequality with two real numbers. I'm having difficulty understanding the logic behind this step: $$ ...
3
votes
1answer
91 views

Rice's theorem_Theory of computation

Is there any body tell me, where is wrong in this proof Problem: The set of number of turing machine that has 5 state is decidable or not? Answer: The set is obviously 'Set of partial computable ...
6
votes
3answers
178 views

Extreme Value Theorem Proof (Spivak)

Them: If $f$ is continuous on $[a,b]$, then there is a $y$ in $[a,b]$ such that $f(y) \geq f(x)$ for each $x \in [a,b]$ Proof. We already know that $f$ is bounded on $[a,b]$, which means that ...
1
vote
1answer
52 views

Is this proof on the product of $X$ OK?

Let $X^2$ be star $\sigma$-compact and $F$ be a closed subset in $X^2$. If $\mathcal{U}$ is an open cover of $F$, then there exists a $\sigma$-compact subset $A$ of $X$, such that $F \subseteq ...
1
vote
1answer
74 views

A modified Buffon's needle

A needle 2.5cm long is dropped on a piece of paper that has a very fine parallel lines 2.25cm apart drawn on it. What is the probability that the needle lies between the two lines? I can see how ...
2
votes
1answer
62 views

Are there examples of theorems proved via proper (i.e. non-conservative) extensions?

This is not a question about set theory specifically, but lets talk about ZFC just for concreteness Suppose we have a sentence $\phi$ in the language of ZFC, and a proof that either $(\mathrm{ZFC} ...
0
votes
1answer
67 views

Finding a reccurence relation for the following problem

A circular disk is cut into n distint sectors, each shaped liek a piece of pie and all meeting at the center point of the disk. Each sector is to be painted red, green, yellow, or blue in such a way ...
-2
votes
1answer
136 views

Given the following recurrence relation, prove using mathematical induction

How can we prove this using mathematical induction? $m_1 = 0$ $m_k = m_{\lfloor (k/2) \rfloor} + m_{\lceil (k/2) \rceil} + k-1$ for all integers $k \geq 1$ Prove using mathematical induction that ...
0
votes
6answers
2k views

Finding the number of subsets of S

How can we find the number of subsets of $S=\{1,2,3,...,10\}$ that contain neither 5 nor 6? Thanks!
1
vote
2answers
115 views

Use the binomial theorem to expand

How can we expand this using the binomial theorem? $(x^2 + 1/x)^7$
7
votes
2answers
362 views

How does one DERIVE the formula for the maximum of two numbers

I want to derive (not prove that this is true) the formula $\max (x,y) = \dfrac{x + y + |y-x|}{2}$ I was reading a proof (which they have the result ahead of time already) that we do cases and then ...
1
vote
2answers
142 views

A typo in Spivak's solution?

Problem Solution I honestly cannot figure out what he is doing. On one hand, I think Spivak wants to write $|\phi(b)/b^n| > 1/2$ instead of $|\phi(b)/b^2| < 1/2$. On the other ...
1
vote
2answers
127 views

Induction on the Fibonacci sequence?

Prove by induction that the $i$th Fibonacci number satisfies the equality: $$F_i = \frac {\phi^i - \hat\phi{}^i}{\sqrt5}$$ where $\phi$ is the golden ratio and $\hat\phi$ is its conjugate. ...
3
votes
2answers
48 views

Show that $\exists A \subset \mathbb{R}$ such that $\forall x$ $\in \mathbb{R}$, we may write $x$ uniquely as $x=a+q$, where $a\in A,q\in\mathbb{Q}$.

Not sure where to go with this one. Clearly will have to use the axiom of choice at some point. I haven't been able to think of a good example for the set A. Once we've got that, it'd be a matter of ...
1
vote
0answers
30 views

Farthest vector pair in subset of unit circle.

This question is extended from this question Given a set $S$ and a pair of vector $x,y\in S$ In this version the set $S$ is a subset of unit circle. That is for all $s \in S$, $||s||=1$ Does the ...
1
vote
1answer
23 views

Showing a pair of vector is the farthest vector pair in certain set

Given a set $S$ and a pair of vector $x,y\in S$ I would like to show $x$ and $y$ are the farthest vector pair in the set $S$ I start with showing there doesn't exist a vector $a \in S$ s.t. ...
2
votes
3answers
85 views

Prove that $(S \cap T = \varnothing) \land (S \cup T = T) \rightarrow S = \varnothing$.

Logically, the following proposition makes sense: $(S \cap T = \varnothing) \land (S \cup T = T) \rightarrow S = \varnothing$ Or, in english, if sets $S$ and $T$ share no elements, and the union of ...
5
votes
2answers
577 views

How can a matrix be Hermitian, unitary, and diagonal all at once

I was given the following problem in class, and I'm not really sure how to begin this proof. Describe all 3 by 3 matrices that are simultaneously Hermitian, unitary, and diagonal. How many are ...
14
votes
1answer
522 views

Spivak's proof that every polynomial of odd degree has a root

I have the second edition of Spivak. Consider Can someone tell me why he considers $2n|a_{n-1}| \dots$? Later he shows everything is squeezed between -1/2 and 1/2 and he gets the desired result. I ...
1
vote
1answer
48 views

Let $X$ has countable extent. Does $X^2$ have countable extent?

Definition 1: A space $X$ has countable extent if every uncountable subset of $X$ has a limit point in $X$. I'm struggling with this question: Question 2: Let $X$ has countable extent. Does ...
0
votes
1answer
205 views

Lie derivative: Leibniz rule proof

How can I prove $\mathcal{L}_v(\omega\wedge\alpha) = (\mathcal{L}_v\omega)\wedge\alpha + \omega\wedge(\mathcal{L}_v\alpha)$ ?
4
votes
0answers
90 views

Infinite “String” of Implication Statements

This question is inspired by the conversations at Does this require transfinite induction? First of all, does an infinite string of implication statements have a conclusion? I don't think so, but I ...
2
votes
2answers
782 views

Proving Cauchy's Mean Value Theorem

In proving Cauchy's mean value theorem, the first step is to use this function: $$ h(x)=[f(b)−f(a)]g(x)−[g(b)−g(a)]f(x)$$ I've seen this in many textbooks but none of them actually show how they got ...
-1
votes
1answer
1k views

Proof of divisibility by 2 and 3 if and only if divisible by 6

I can't find a way of proving that: For integer a, a is divisible by 2 and divisible by 3 if and only if a is divisible by 6. I’m not sure where to go from here. Any help would be great!
2
votes
3answers
287 views

Prove that Statements forms are tautologies

Given variable statement forms $A$ and $B$. How to prove that if $(A\land B)$ is a tautology then $A$ and $B$ are tautologies too?. Mi approach would be a proof by contradiction, something like: If ...
3
votes
1answer
148 views

Prove that there exist infinitely many squares $a$ such that $\sqrt{\sqrt{a}}$ is a square

I was just thinking about squares while randomly punched numbers into my calculator and I was wondering do there exist infinitely many squares such that $\sqrt{\sqrt{a}}$ is a square and $a$ is also a ...
11
votes
1answer
264 views

Find all functions $F(x,y)$ such as $\frac{\sqrt{3}}{2}\frac{\partial{f}}{\partial{x}}+\frac{1}{2}\frac{\partial{f}}{\partial{y}}=0$

How to find all possible functions $f(x,y)$ such as: $$ \frac{\sqrt{3}}{2}f_x+\frac{1}{2}f_y=0$$ (with $f_x = \frac{\partial{f}}{\partial{x}}$ ) Here's everything I tried: 1) I can guess the ...
2
votes
2answers
80 views

Proving if $a_1\equiv b_1\pmod{n}$ and $a_2\equiv b_2\pmod{n}$ then we have $a_1+a_2\equiv b_1+b_2\pmod{n}$.

How can I prove if $a_1\equiv b_1\pmod{n}$ and $a_2\equiv b_2\pmod{n}$ then we have $a_1+a_2\equiv b_1+b_2\pmod{n}$? I have tried several ideas I've found online but don't really understand them. Is ...
5
votes
3answers
234 views

Pythagorean theorem and its cause

I'm in high school, and one of my problems with geometry is the Pythagorean theorem. I'm very curious, and everything I learn, I ask "but why?". I've reached a point where I understand what the ...
1
vote
2answers
82 views

how to prove: $A=B$ iff $A\bigtriangleup B \subseteq C$

I am given this: $A=B$ iff $A\bigtriangleup B \subseteq C$. And $A\bigtriangleup B :=(A\setminus B)\cup(B\setminus A)$. I dont know how to prove this and I dont know where to start. please give me ...
1
vote
2answers
74 views

$T\circ T=0:V\rightarrow V \implies R(T) \subset N(T)$

Question Let $T:V \rightarrow V$ be a linear map. How do I prove that $T \circ T = T_0$ ( the zero linear map) iff $R(T) \subset N(T)$? Attempt \begin{eqnarray} T\circ ...
2
votes
1answer
70 views

If $x,y$ are elements of $\mathbb{R}$ and $x>0$ then there is a positive integer $n$ s.t. $nx > y$

Im reading a proof about this The proof is here. Let $A$ be the set of all $nx$, where $n$ runs through the positive integers. If $nx \le y$, then $y$ would be an upper bound of $A$. (start ...
7
votes
1answer
323 views

The genus of the Fermat curve $x^d+y^d+z^d=0$

I need to calculate the genus of the Fermat Curve, and I'd like to be reviewed on what I have done so far; I'm not secure of my argumentation. Such curve is defined as the zero locus ...
-1
votes
1answer
61 views

Existence Proof: $T(v_i)=w_i$ for all $i=1,2,3,\dots,n$

Theorem to prove: Let $\{v_1,\dots,v_n\}$ be a linearly independent set in a finite-dimensional vector space $V$ and let $w_1,\dots,w_n$ be arbitrary vectors in a vector space $W$. Then there exists ...
4
votes
1answer
163 views

Hard-wiring a proof method in my head

There's s a kind of proof regularly used in linear algebra ( proving facts about Transformations, direct sums, basis, ... ) that i have definitely agreed with but still couldn't connect my intuitive ...
0
votes
1answer
82 views

Proof: Two circles have a most 2 intersections

I already prooved the statement here in general, but know I tried to proove it in an other way: I put $M_1$ on $(0/0)$ and the x-axis through $M_1$ and $M_2$. That simplifies the equatons for ...
0
votes
1answer
59 views

Proving recurrence relations

So, I initially proved the theorem that if $a != b^d$ and $n$ is a power of $b$, then $f(n) = C_1n^d + C_2n^{log_b a}$, where $C_1 = b^dc/(b^d − a)$ and $C_2 = f(1) + b^dc/(a − b^d )$. This is seen ...
5
votes
2answers
128 views

If $f$ and $g$ are continuous, prove $f\circ g$ is continuous.

Suppose that $(X,T)$, $(Y,U)$ and $(Z,V)$ are three topological spaces and that $g\colon X\to Y$ and $h\colon Y \to Z$ are continuous. Prove that $h\circ g\colon X \to Z$ is a continuous ...
0
votes
2answers
92 views

Proof pythagoras theorem with dot product + distance

I want to proof $d(A.B)^2=d(A,C)^2+d(B,C)^2$ for with $(\vec a-\vec c) \bullet (\vec b - \vec c)=0$. I applied the definitions of distance and got $d(A,B)^2=d(A,C)^2+d(B,C)^2 \Leftrightarrow ...
-4
votes
1answer
77 views

Transformation Existence Proof: A Call for Critique [duplicate]

QUESTION Prove that there exists a $T:V\rightarrow W$ such that $N(T)=V'\subset V$ and $R(T)=W'\subset W$ ATTEMPTED ANSWER Let $V$ and $W$ be finite-dimensional vector spaces over $F$. Let ...
3
votes
2answers
116 views

Repeating Square Root Closed Form [duplicate]

I've been thinking about repeating square roots: $\sqrt{x+\sqrt{x+\sqrt{x+\cdots}}}$. I wrote a program on my calculator to do it $n$ times and I found that, if $x = y^2 - y$ then ...
0
votes
1answer
91 views

Explanation of proof common divisor divides gcd needed

I have been given a proof that uses the gcd to show that there is no biggest prime. However (coming from a less mathematical background) I am having trouble actually understanding what it means and ...
2
votes
1answer
64 views

Proofs regarding diagonalization of matrices

I'm trying to prove that a unitary matrix can be diagonalized using an orthonormal basis of eigenvectors, and that the eigenvalues are on the unit circle. So far, I have been able to show that if A is ...
3
votes
2answers
731 views

Solving two simultaneous recurrence relations

If we have the two recurrence relations $$a_n = 3a_{n-1} + 2b_{n-1}$$ $$b_n = a_{n-1} + 2b_{n-1}$$ with $a_0 = 1$ and $b_0 = 2$. My solution is that we first add two equations and assume that $f_n = ...
3
votes
1answer
49 views

Using a particular image to justify a (specific) trig integral equality.

I would like to include the following string of equalities in a paper: $$\sin ^2(x) + \cos ^2(x) = 1$$ $$\int _0^{\dfrac{\pi}{2}} \sin ^2 (x)dx + \int_0^{\dfrac{\pi}{2}} \cos ^2 (x)dx = ...
3
votes
1answer
118 views

Is my proof correct? $p_1p_2p_3\cdots p_n+1)$ cannot be the square of an integer

Prove that $p_1p_2p_3\cdots p_n+1$, where $p_n$ is the $n^{th}$ prime, cannot be the square of an integer. Let $p_1p_2p_3\cdots p_n+1=Q$ and assume it is the square of an integer, so ...
6
votes
2answers
165 views

Discreteness of eigenvalues for certain operators - can this approach be made rigorous?

I was idly thinking about why one might naïvely expect a discrete spectrum of eigenvalues for a linear operator $L$ when I dreamt up the following argument (which I expect isn't new instead - ...
1
vote
0answers
53 views

Visual/intuitive proof of why $\sum k^3 = (\sum k)^2$, where $k$ goes from 1 to $n$? [duplicate]

I understand that one could prove this by first proving the analytic expressions of the sigma terms through induction, and then square the $\displaystyle\sum_{k=1}^n k$ term to show LHS = RHS. Are ...
2
votes
3answers
232 views

is this a foolish way to do proofs?

When I'm asked something like "show X is equal to Y", I first try to manipulate what I know (X) into the result (Y). A lot of the time, I do not investigate the result I'm trying to conclude with. I ...
1
vote
2answers
1k views

A one-to-one function from a finite set to itself is onto - how to prove by induction?

I'm not sure if I can do this without knowing what f actually is? Let $X$ be a finite set with $n$ elements and $f: X \rightarrow X$ a one-to-one function. Prove by induction that $f$ is an onto ...