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
3answers
38 views

Determine the numbers $n$ that are orders of elements of $\mathbb{Z}^3 / H$

Let $G=\mathbb{Z}^3/H$, where $H$ is a subgroup that has been generated by $(2,0,2), (6,6,6) $ and $(8,36,38)$. How can I solve this problem? I don't know where to start. A related question would ...
2
votes
2answers
71 views

How many elements are in the conjugacy class of $\tau \in S_9$?

Just one simple question: Let $\tau =(56789)(3456)(234)(12)$. How many elements does the conjugacy class of $\tau$ contain? How do you solve this exersie? First step is to write it in disjunct ...
0
votes
1answer
63 views

How to determine if $G$ contains an element of order $k$?

I'm struggling with this kind of problem: Given a group $G= (\mathbb{Z}/n\mathbb{Z})^*$ (which is the multiplicative modulo group), determine if the group contains an element of order $k$. What is ...
2
votes
0answers
76 views

has any cycle found in MD5?

We are not sure whether MD5 has fixed point or not. But since the sample space is finite, it must have cycles: $$ A →(MD5)→ B →(MD5)→ C →(MD5)→ D →(MD5)→ A $$ Has any research been done on MD5 to ...
3
votes
0answers
323 views

Confusing proof of brun's theorem?

I read Brun's proof of Brun's theorem here : http://gallica.bnf.fr/ark:/12148/bpt6k486270d/f110.image (and the following pages) and here http://gallica.bnf.fr/ark:/12148/bpt6k486270d/f138.image ...
5
votes
3answers
130 views

Archimedean Proof?

I've been struggling with a concept concerning the Archimedean property proof. That is showing my contradiction that For all $x$ in the reals, there exists $n$ in the naturals such that $n>x$. ...
0
votes
0answers
82 views

Hamiltonian cycle problem: how to prove NP-completeness?

How to prove that finding a Hamiltonian cycle in a graph is an NP-complete problem? Should I try to reduce the travelling salesman problem (TSP) to this one (Hamiltonian cycle)?
0
votes
1answer
192 views

Proof of equivalent definitions of continuity of a function

Let $X$ and $Y$ be metric spaces, and $f : X\rightarrow Y$ a function I have to prove: (1) $f : X\rightarrow Y$ is continuous (3) $\forall\,F \subset Y closed: f^{-1}(F) \, is\,closed$ from $(3) ...
1
vote
2answers
168 views

I don't understand this proof of the AM-GM inequality?

The proof uses this lemma which I understand: $\mathbf {Lemma}$: Suppose $x$ and $y$ are positive real numbers such that $x>y$. If we decrease $x$ and increase $y$ by some positive quantity $E$ ...
-1
votes
3answers
462 views

How many ways can $5$ rings be placed on $4$ fingers?

I've been trying to solve this problem and I am kind of struggling with it and with other combinatorics problems. Could you check and see if i did it right? Given problem: How many ways can 5 ...
3
votes
2answers
135 views

choosing $5$ non consecutive books from a shelve of $12$

In how many ways can you pick five books from a shelve with twelve books, such that no two books you pick are consecutive? This is a problem that I have encountered in several different forms ...
1
vote
3answers
93 views

$3^{3n+1} < 2^{5n+6} $ for all non-negative integers $n$. Is my induction solution correct?

Show using mathematical induction that $3^{3n+1} < 2^{5n+6} $ for all non-negative integers $n$. I'm not sure whether what I did at the last is valid? Basis step: for all non-negative integers ...
1
vote
3answers
58 views

What do you use for your basis step when its domain is all integers?

Example: *For all integers $ n , 4( n ^2 + n + 1) – 3 n ^2$ is a perfect square what should i use? negative infinity? I know you can use a direct proof but what if theres an induction question with ...
2
votes
0answers
72 views

Checking an inductive proof on a combinatorial product

Consider the following product, for $n, k, i \in \Bbb Z_+, k \geq 2$: $$ {\prod_{\ell = 1}^i {n + k - \ell \choose k } \over \prod_{\ell = 1}^{i-1} { k + \ell \choose k}} \tag{$*$} $$ It has been my ...
1
vote
0answers
196 views

Ramanujan-Nagell and Pell’s equation

In my study of Pell’s equation $(x(d))^2-d(y(d))^2=1$ (eq.1), I looked at the family of equations where $d=2^n-3$ to which 61 belongs. (This was really a study of d=61 in equation 1.) In some cases, ...
0
votes
0answers
74 views

Cauchy sequence proof problem.

I worked out the following problem Show that $\{a_n\}$ and $\{b_n\}$ are equivalent Cauchy sequences iff $\{c_n\} = \{a_1,b_1,a_2,b_2, \cdots \}$ is Cauchy. my proof: $(\Leftarrow)$ Suppose ...
0
votes
4answers
373 views

All real numbers can be expressed as a limit of rational numbers?

RTP Let $C$ be a set of Cauchy sequences. $\forall x \in {\Bbb R}, \exists \{a_n\} \in C$ sucht that ${a_n} \to x$. I have no clue to even start this problem. All I know so far is that $\Bbb R$ ...
12
votes
4answers
2k views

$\epsilon$-$\delta$ proof that $\lim\limits_{x \to 1} \frac{1}{x} = 1$.

I'm starting Spivak's Calculus and finally decided to learn how to write epsilon-delta proofs. I have been working on chapter 5, number 3(ii). The problem, in essence, asks to prove that ...
2
votes
1answer
127 views

Pythagorean theorem proof by dissection

I have this proof of the Pythagorean theorem, but in the last two lines of the fourth paragraph I can't seem to find geometrically how the congruency between $1$, $2$, $3$, $4$ and $1'$, $2'$, $3'$, ...
14
votes
2answers
647 views

Where's the error in this $2=1$ fake proof? [duplicate]

I'm reading Spivak's Calculus: 2 What's wrong with the following "proof"? Let $x=y$. Then $$x^2=xy\tag{1}$$ $$x^2-y^2=xy-y^2\tag{2}$$ $$(x+y)(x-y)=y(x-y)\tag{3}$$ ...
2
votes
1answer
141 views

Proof using the rule of product or multiplication rule of combinatorics.

Assume that set $A$ has $r$ elements, and set $B$ has $n$ elements (both of them are finite and not empty sets), I need to proof using the rule of product or multiplication principle of ...
0
votes
1answer
92 views

Let $X$ be a Moore space and $e(X)=\omega$. Is it metrizable?

Let $X$ be a Moore space and $e(X)=\omega$. Is it metrizable? What I've tried: I list these facts: 1 A space $X$ is a Moore space iff $X$ is a $\sigma$-space and a $p$-space. 2 If $X$ is a ...
2
votes
2answers
115 views

Prove that $n! < n^n $ where n >1 and is an integer , why do some people say my solution is wrong?

Prove that $n! < n^n $ where n >1 and is an integer. Lets skip the base case cause its trivial. Assume that: $$ k! < k^k = $$ Inductive step: $$(k+1)! < (k+1)^{k+1} =$$ $$(k)!(k+1) < ...
8
votes
1answer
245 views

Proving that $\omega(N)\neq4$ for an odd perfect number $N$ by hand

Let $\omega(n)$ denote the number of distinct prime factors of a positive integer $n$, and let $N$ be an odd perfect number. It is not difficult to show that $\omega(N)\ge3$. In fact, Nocco already ...
2
votes
3answers
60 views

Prove Satisfiability of Property by Set

What is a proof strategy for proving that some property is satisfied by a particular set of numbers. For example, what would be an approach for proving that the archimedean property is satisfied by ...
1
vote
1answer
973 views

Suppose a,b are real numbers, if a is rational and ab is irrational, then b is irrational (Is my solution correct?)

Suppose $a,b$ are real numbers, if $a$ is rational and $ab$ is irrational, then $b$ is irrational. Solution: Proof by contraposition $$b = \frac{p}{q}$$ $$ a = \frac{j}{k}$$ where $p,q,j,k$ are ...
2
votes
3answers
620 views

Proving if $x$ is an even integer then $x^2 -6x +5$ is odd

If $x$ is an even integer, then $x^2 - 6x + 5$ is odd. My solution (direct proving): $$ x = 2k$$ $$ x^2 - 6x + 5 = 4k^2 -12k + 5 $$ $$ 4k^2 -12k + 4 + 1 = 2(2k^2-6k+2)+1$$ which is by definition is ...
1
vote
1answer
93 views

Is this pumping lemma solution correct?

Let Σ = {a, b, c}. Use the pumping lemma to prove that A = {aibicj | i,j ≥ 0} is not regular. Please make sure that your proof is clear, logical and complete. The solution that I wrote was: ...
2
votes
1answer
144 views

Approximate Nash Equilibrium

I am sort of confused by the notion of approximate Nash equilibrium. I will try to express my confusion in the following exercise. Problem. Is it true that for every two player game where every ...
-3
votes
1answer
93 views

$\operatorname{rank} (T^*) = \operatorname{rank} (T)$ : PROOF

Let $T$ be a linear operator on a finite dimensional inner product space. Prove that $\operatorname{rank}(T^*) = \operatorname{rank}(T).$
1
vote
0answers
62 views

Trying to prove an identity about a product

I have a product formula that, given a tuple $(a_1, \dots, a_{n-1}, 0)$, computes a dimension (of a vector space) via the following formula: $$ \mathrm{dimension} = \prod_{i < j} {(a_i + \cdots + ...
2
votes
1answer
64 views

Inner Product Spaces : $N(T^{\star}\circ T) = N(T)$ (A PROOF)

Let $T$ be a linear operator on an inner product space. I really just want a hint as to how prove that $N(T^{\dagger}\circ T) = N(T)$, where "$^\dagger$" stands for the conjugate transpose. Just as ...
4
votes
3answers
163 views

Invertibility in a finite-dimensional inner product space

Let $T$ be an invertible linear operator on a finite-dimensional inner product space. I just want a hint as to how I should prove that $T^{\star}$ is also invertible and $( T^{-1} )^{\star} = ( ...
3
votes
3answers
345 views

Evaluate $\displaystyle\sum_{k=1}^nk\cdot k!$

I discovered that the summation $\displaystyle\sum_{k=1}^n k\cdot k!$ equals $(n+1)!-1$. But I want a proof. Could anyone give me one please? Don't worry if it uses very advanced math, I can just ...
0
votes
1answer
91 views

Proving inequality of addition and multiplication

Which approach can be used to proof the inequality of the following equation? $$ax^2 + cy^2 = -2bxy.$$ We only know that $a > 0$ and $c > 0$ as well as: $$ac - b^2 > 0.$$ Therefore $b$ ...
6
votes
3answers
104 views

How to prove $4(n!)>2^{n+2}$ for $ n\geq 4$ with induction

I've done the base step, but how do I prove it is true for $n+1$ without using a fallacy? $$4(n!)>2^{n+2}\quad \text{for } n\geq 4$$ Please help.
5
votes
1answer
60 views

Equivalence between these definitions of ordinal numbers

Von Neumann defines an ordinal $\alpha$ as a transitive set whose elements are well-ordered with respect to the membership relation $\in$. Meanwhile, in Naive set Theory, Halmos defines an ordinal ...
2
votes
3answers
73 views

How to prove/show $1- (\frac{2}{3})^{\epsilon} \geq \frac{\epsilon}{4}$, given $0 \leq \epsilon \leq 1$?

How to prove/show $1- (\frac{2}{3})^{\epsilon} \geq \frac{\epsilon}{4}$, given $0 \leq \epsilon \leq 1$? I found the inequality while reading a TCS paper, where this inequality was taken as a fact ...
1
vote
2answers
215 views

Proving a biconditional statement with an or

I want to prove a theorem in geometry of the form $p \iff q \vee r$. My plan is to prove: $q \implies p$ as well as $r \implies p$ $p \text{ and } \lnot q \implies r$ Can I get someone to verify ...
1
vote
1answer
122 views

A question on mean value inequality

It is known that mean value inequality is very useful. It is: For any $0 \le a_i (i=1,2,\dots,n)$, $$ a_1 a_2\dots a_n\le (\frac{a_1+a_2+\dots + a_n}{n})^n \tag1 $$ My question is: how many ...
3
votes
3answers
109 views

Multipliciousness within an inner product space.

Question: Let $V$ be an inner product space and $v,w\in V$. Prove that $\lvert\langle v,w\rangle\rvert=\lVert v\rVert \lVert w\rVert$ if and only if one of the vectors $v$ or $w$ is a multiple of ...
4
votes
2answers
3k views

This is a possible proof of the Riemann Hypothesis [closed]

http://arxiv.org/abs/1305.6845 The above link claims to have solved the Riemann Hypothesis. It's not mine, of course. I just saw this on Tumblr and realized I needed bigger guns. This proof looks like ...
1
vote
0answers
68 views

Proving $\text{Var}{(\hat{y}_h)} = \sigma^2 \left(\frac{1}{n} + \frac{(x_h-\bar{x})^2}{S_{xx}}\right)$

I have asked in another question how $\text{Var}{(\hat{y}_h)} = \sigma^2 \left(\frac{1}{n} + \frac{(x_h-\bar{x})^2}{S_{xx}}\right)$. Note that $\hat{y}_h$ = $b_0 + b_1X_h$ which is a regression line ...
5
votes
3answers
207 views

Help with Cartesian product subsets [duplicate]

I want to prove that if $A \subseteq C\,$ and $\,B \subseteq D,\,$ then $\,A \times B \subseteq C \times D.$ I know that $A \subseteq C \iff a \in A \rightarrow a \in C$ and that $B\subseteq D\iff ...
2
votes
2answers
394 views

How do I prove Binet's Formula? [duplicate]

My initial prompt is as follows: For $F_{0}=1$, $F_{1}=1$, and for $n\geq 1$, $F_{n+1}=F_{n}+F_{n-1}$. Prove for all $n\in \mathbb{N}$: ...
3
votes
2answers
241 views

Prove the monotonicity of the expectation of a binary random variable function

Consider $R$ independent binary random variables $y^1, \ldots, y^R$ over the space $\{-1, +1\}$ such that $\Pr(y^j = 1) = p^j \geq 0.5$ and $\Pr(y^j = -1) = 1 - p^j$, $\forall j = 1,\ldots,R$. ...
6
votes
4answers
162 views

Is there a simpler approach to these system of equations?

I recently came across the following system of equations: $$x + y + z = 1 \\ x^2 + y^2 + z^2 = 2 \\ x^3 + y ^3 + z^3 = 3$$ And I have two questions: One, is there a way to prove or disprove ...
53
votes
15answers
7k views

Prove if $n^2$ is even, then $n$ is even.

I am just learning maths, and would like someone to verify my proof. Suppose $n$ is an integer, and that $n^2$ is even. If we add $n$ to $n^2$, we have $n^2 + n = n(n+1)$, and it follows that ...
0
votes
5answers
241 views

Proof of the equality of the difference of two sets iff sets are equal (direct vs. indirect)

I have a problem with the following (really) basic result: $$A\backslash B=B\backslash A \Longleftrightarrow A=B$$ More specifically, I am able to prove it only by contradiction (in particular in the ...
3
votes
2answers
317 views

Natural Deduction proof for $\forall x \neg A \implies \neg \exists xA$

$\forall x \neg A \implies \neg \exists xA$ I won't ask you to solve this for me, but can you please give some guiding lines on how to approach a proof in NDFOL? There are many tricks that the TA ...