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

3
votes
4answers
87 views

How to easily prove $x+\frac{1}{x} \ge 2 \quad ∀x\in ℝ^+$ [duplicate]

When I tried to solve some certain math problem (an inequation) for pivate exercise purposes, I had to prove that $x+\frac{1}{x} \ge 2 \quad ∀x\in ℝ^+$, I solved it with tools from differential ...
0
votes
0answers
12 views

Predicate Logic Proof by Refutation Question

I am studying proof my refutation in predicate logic. I am looking at the step where all quantifiers need to be moved to the prefix position. Assuming the following formula: ...
1
vote
3answers
30 views

How is derived the inductive step in mathematical induction?

I am quite familiar with the algorithm of mathematical induction but I can't rationalize the inductive step very well. Suppose I have the classical example: $$0 + 1 +2 + \ldots + n = ...
8
votes
3answers
186 views

Abstract nonsense proof

What is a simple example of an "abstract nonsense" proof in category theory. For a theorem you are proving, it doesn't matter if the category or regular proof came first, it is just that the category ...
1
vote
1answer
37 views

Correctness of Proof by Refutation

I am trying to solve the following by proof by refutation: A or B 1. NOT A or I 2. NOT B or T 3. NOT I 4. NOT T 5. Where the goal is to prove a contradiction. ...
2
votes
1answer
106 views

Quadratic Diophantine Equation $x^2 + axy + y^2 = z^2$

I have been reading about this quadratic Diophantine equation of the form $x^2 + axy + y^2 = z^2$ where x, y, z are integers to be solved and a is a given integer. All integral solutions are given ...
0
votes
2answers
44 views

Prove a formula about binoms

I want to prove that $\binom{n}{n/2} \leq 2^{n-1}$ [Assuming $n$ is even] I've tried to do that but I didn't succeed.
4
votes
1answer
178 views

How to prove that equilateral triangle formed by cube's corners cannot be fully inserted to this cube

I would like to prove that equilateral triangle prescribed by cube's corners and sides equal to $b = a \sqrt{2}$ cannot be inserted into the interior of a cube of side $a$. This triangle is presented ...
0
votes
2answers
111 views

How can one pass from “almost surely” to “surely”?

Several results (e.g in probability theory or using prob. theory) are stated in an almost surely phrasing (meaning the set of outcomes where this is not so has measure zero) How can one pass from ...
0
votes
0answers
46 views

algebraic proof of integration

You can prove integration in this way with algebra and number theory for the problem y=2x^2+1 or y=ax^2+c: $$S_n=\frac{2b^3k^2}{n^3}+\frac{b}{n}....... ...
3
votes
1answer
74 views

Epsilon-delta proof for a sum

Consider $\displaystyle \begin{array}{ccccc} f & : & \mathbb R^+ & \to & \mathbb R \\ & & x & \mapsto & \frac{x}{\sqrt{1+x}} \\ \end{array}$ Prove that ...
1
vote
0answers
57 views

Is the proof of non-totality of a function $f$ trivial if $f$ is recursively defined only on a subset of $\Bbb N$?

I define a fuction $*$ in a recursive way on a subset of natural numbers (with subset I mean that is $*$ define in the second argument only for $\Bbb N-\{0,1\}$ in other words we have $*:\Bbb N ...
0
votes
2answers
63 views

How would this problem need the Mean Value Theorem?

I'm asked to square the inequality and use the Mean Value Theorem to prove that $$\sqrt{1+x} < 1 + \frac{x}{2}$$ for $x>0$. Unfortunately, I don't really understand why I would need such a ...
3
votes
0answers
166 views

Which is the best transitional mathematics book for self-teaching among the ones listed?

What is Mathematics, An Elementary Approach to Ideas and Methods - Courant Robbins Stewart How to Solve It, A New Aspect of Mathematical Solving - Polya Introductory Mathematics, Algebra and Analysis ...
0
votes
0answers
30 views

U-substitution proof by partitions

I am trying to prove integration by substitution, i.e. for $f:[c,d] \rightarrow \mathbb{R}$ continuous and $\phi: [c,d] \rightarrow [a,b]$ continuous on $[c,d]$ and $C^1$ on $(c,d)$. Then define ...
1
vote
1answer
49 views

In an exam the average marks of all the students is $30$ . Show that at least $20\%$ of the students have got at least $10$

In an exam the average marks of all the students is $30$ (out of $100$). We have to show that $\underline{\mathrm{at\ least\ 20\%\ of\ the\ students\ have\ got\ at\ least\ 10}}$ (out of $100$). I ...
4
votes
4answers
236 views

Prove that p has m distinct roots if and only if p and p' have no roots in common

Problem: Suppose $p \in \mathcal{P}(\mathbf{C})$ has degree $m$. Prove that $p$ has $m$ distinct roots if and only if $p$ and its derivative $p'$ have no roots in common. My proof so far: If $m=0$, ...
2
votes
1answer
45 views

Proving a theorem on limits

I need to prove that: If $$\lim_{(x,y) \to (a,b)}f(x,y)= 0 \text{ and } g(x,y)\leq k,$$ then: $$\lim_{(x,y) \to (a,b)}f(x,y) g(x,y) =0.$$ My approach is like follow: ...
2
votes
1answer
87 views

Prove that the dual graph of any (planar) graph is connected

I'd like to know if there's a standard proof that the dual graph of any planar graph is connected (or, if there's a counterexample, I'd like to know that too). I've thought of a proof that might work ...
3
votes
1answer
40 views

$HA^{\omega}$ is a conservative extension of $HA$. But why?

This is definitely a silly question, but I've no one to ask... $HA^{\omega}$ is an extension of $HA$ in all finite types. One can formalize a model of $HA^{\omega}$ in $HA$ using indicies of partial ...
1
vote
1answer
51 views

Show that if the diameter of an undirected graph is $d$ then there exists some vertex separator $S\subseteq V$ of size $|S| \leq { n\over d-1} $

Show that if the diameter of an undirected graph is $d$ then there is some set $S\subseteq V$ with $|S| \leq \frac{n}{d-1} $ such that removing the vertices in S from the graph would break it into ...
0
votes
0answers
22 views

complete logic for proving inequalities

Last semester I took a course on algorithm analysis a big part of which was proving that the running time function of a program was in the set $O(f(x))$ for some $f$. To prove $f\in O(g(x))$ one ...
5
votes
1answer
82 views

Using Plancherel's Theorem to Prove the Gauss Sum

I'm interested in proving the following: Where $p$ is an odd prime and $z$ is a primitive $p$th root of unity, we let $Q(p)=\sum^{p−1}_{k=0}z^{k^2}$. Prove: $|Q(p)|=\sqrt{p}$. Specifically, I want ...
1
vote
2answers
52 views

Proving $2^x$ is only ever 9 less than a perfect square for a unique value of x

I am trying to prove something that has essentially boiled down to proving that $9 + 2^x$ will only ever be a perfect square for the unique value of x=4, and that no other value will produce a perfect ...
1
vote
2answers
41 views

Show a double-sided infinite integral of $\sin(x+b)$ exists iff $b=n\pi$

More formally: Show that $$\lim_{a\rightarrow \infty} \int_{-a}^a \sin(x+b)$$ exists if and only if $b=n\pi$ for some $n \in \mathbb{Z}$. I get the intuition fine. The function is just a horizontal ...
4
votes
0answers
89 views

Proving u-substitution the hard way — use only definition of integration with partitions

I am trying to prove integration by substitution, i.e. for $f:[c,d] \rightarrow \mathbb{R}$ continuous and $\phi: [c,d] \rightarrow [a,b]$ continuous on $[c,d]$ and $C^1$ on $(c,d)$. Then define ...
3
votes
2answers
125 views

Proof that SAT is NPC

I am not really sure I understand the idea behind Cook theorem (it says that SAT is a NP-complete problem). I read the proof with all its parts corresponding to the Turing machine TM solving it (TM ...
0
votes
2answers
56 views

Ideas on how to proceed with a proof?

Sorry if this is a nonspecific question - I can provide more details but at this point I need general ideas on a proof strategy. So I recently reduced a rather difficult optimization problem to ...
0
votes
4answers
376 views

Prove: if x is odd, then sqrt(x) is odd.

If $x$ is odd, then $\sqrt{x}$ is odd, where $x$ is an integer. Any hints welcome and preferred. Thank you!
0
votes
1answer
35 views

Logistic Regression derivation

From the Wikipedia article http://en.wikipedia.org/wiki/Multinomial_logistic_regression: $ln \frac{\Pr(Y_i=1)}{\Pr(Y_i=K)} = \beta_1 \cdot \mathbf{X}_i $ $ln \frac{\Pr(Y_i=2)}{\Pr(Y_i=K)} = ...
0
votes
1answer
56 views

show analytic function such $f(z)={\operatorname{Log}(z+5)\over z^2+3z+2}$

Show that $f(z)=\dfrac{\operatorname{Log}(z+5)}{z^2+3z+2}$ is analytic everywhere except at the point $-1,-2$ and on the ray $\{(x,y):x\le -5,y=0\}$. i think that separate denominator and ...
3
votes
2answers
79 views

Passing a derivative through a limit.

After searching around on the net and on SE I have not found a satisfactory answer. Let $f_n: D \to \mathbb R$ be a sequence of functions. What assumptions, aside from $f$ being differentiable, do we ...
2
votes
0answers
45 views

Velleman's How to prove it. Partial order proof.

Theorem: Suppose that $R$ is a partial order on $A$, $B_1 ⊆ A$, $B_2 ⊆ A$, $x_1$ is the least upper bound of $B_1$, and $x_2$ is the least upper bound of $B_2$. Prove that if $B_1 ⊆ B_2$ then ...
0
votes
2answers
65 views

Suppose $F$ and $G$ are families of sets.

Suppose $F$ and $G$ are families of sets. Prove that $\bigcup F$ and $\bigcup G$ and are disjoint iff for all $A∈F$ and $B∈G$ , $A$ and $B$ are disjoint. It has been suggested to use contrapositive ...
1
vote
3answers
32 views

Where does my proof of uniform continuity fail?

I am trying to prove that $f:R \to R f(x)=\sin x$ is uniformly continuous. I have said: Fix $\epsilon > 0$ and $\delta=\epsilon$ $|\sin x - \sin y| \le |\sin x| - |\sin y| \le 1 - 1 = 0 ...
2
votes
1answer
63 views

Help Needed Showing that $\chi(\overline{G \times H}) \leq \chi(\overline{G}) \times \chi(\overline{H})$

Where $\chi(G)$ denotes the chromatic number, $\overline{G}$ the graph complement, and $\times$ the Cartesian Graph Product: I need to show that $(\forall G,H)( \chi(\overline{G \times H}) \leq ...
3
votes
3answers
66 views

Is it possible to use mathematical induction to prove a statement concerning all real numbers, not necessarily just the integers? [duplicate]

I am referring to the part of proof by mathematical induction where you show that "if it is true for one value k then it is true for the value k+1". Does proof by induction work over all real numbers? ...
1
vote
2answers
35 views

Proofs involving Well-Defined and One-to-One

Chartrand, 3rd Ed, P224-225: Define a relation $R$ as a relation from A to B. $R$ is well-defined means: $(a,b), (a,c) \in R \implies b = c$. P220: A function $f: A \to B$ is one-to-one ...
0
votes
0answers
33 views

How to Devise Combinatorial Arguments for Proving Identities

What are some strategies or tips for contriving/devising combinatorial arguments? Combinatorial proof for $\binom{n}{a}\binom{a}{k}\binom{n-a}{b-k} = \binom{n}{b}\binom{b}{k}\binom{n-b}{a-k}$? I ...
0
votes
1answer
37 views

Proving a function is not uniformly continuous.

I am using the definition: $(∃ε > 0)(∀n ∈ N)(∃ x_n, y_n ∈ (0,1])[(|x_n − y_n| < δ_n =1/n) ∧ (|f(x_n) − f(y_n)| ≥ ε)]$ to prove that $1/x^2$ is not uniformly continuous. In the solution I am ...
0
votes
1answer
25 views

Prove that the distance function $d_p(x,y)=\sum_1^n |x_i-y_i|^p$ $0<p<1$ is a metric on R^n

Hi I am trying to prove that for $0<p<1$ the function $d_p(x,y)=\sum_1^n |x_i-y_i|^p$ is a metric on $\mathbb{R}^n$. I am struggling with the triangle inequality part; We have to prove ...
0
votes
2answers
38 views

I know the limit of a subsequence exists, but how do I find it?

I know intuitively that for: $(a_n) = (1,1,2,1,2,3,1,2,3,4, ...)$ for any $m$ in the positive natural number there is a subsequence (m,m,m,..) that tends to m as n tends to infinity. I believe I ...
2
votes
2answers
87 views

Proving a math statement is true or false

For all $x$ there is a $y$ such that if $x$ is non negative then $y^2 = x$ Is my logic correct in proving that statement is true ? Can provide an explanation of how to test this proof ? $x=2$ ...
5
votes
5answers
671 views

Positive integers expressable as sums of powers of 2

I need to prove that any positive integer is expressable as $$x=2^{j_0}+2^{j_1}+2^{j_2}+...+2^{j_m}$$ where $m\ge 0$ and $0\le j_0\lt j_1\lt j_2\lt ... \lt j_m. $ I think I get the gist of the proof; ...
1
vote
3answers
49 views

Disproving 0 as a dividend

Prove each of the following statements. (a) For all $b \in \mathbb{Z}$ if for all $k \in \mathbb{N}$, $b \not\mid k$, then $b = 0$. By hypothesis: $b \not\mid k \implies b\ell \neq k, \ell ...
3
votes
1answer
55 views

How to show that $P_n(x)$ have n distinct roots [duplicate]

Let $P_n : \mathbb R \to \mathbb R $ , $n\in \mathbb N$ be defined by $P_n(x)=\frac{\displaystyle1}{\displaystyle2^n n!}\frac{\displaystyle d^n}{\displaystyle dx^n}[(x^2-1)^n]$ I need to show that ...
0
votes
1answer
67 views

Converse of DIC

I am looking to prove the converse of the Divisibility of Integer Combination. I know how to prove the contrapositive of this statement but not the converse ... any help? Below is my attempt at ...
2
votes
6answers
105 views

Investigating the linearity between squares and their roots

I recently noticed that $\sqrt{128} = 11.31$ and that $128$ is $\approx 30\%$ between $121 = 11^2$ and $144=12^2$, that is: $$ \frac{128-121}{144-121} = \frac{7}{23} \approx 30\%$$ and $\sqrt{128} = ...
2
votes
1answer
96 views

How to Prove it 4.1 ex.10

Prove that for any sets A, B, C, and D, if A × B and C × D are disjoint, then either A and C are disjoint or B and D are disjoint. Proof(someones). Suppose (A X B) and (C X D) are disjoint. Let (x,y) ...
1
vote
1answer
150 views

Find bases given that P is the change of coordinates matrix from this to this [Lay P244 Q4.7.19]

Lay P289: Let $V$ be an $n$-dimensional vector space, let $W$ be an $m$-dimensional vector space, and let $T$ be any linear transformation from $V$ to $W$. To associate a matrix with $T$, choose ...