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
1answer
50 views

Math Analysis - Two Bounded Functions and partitions proof

Let $f,g:[a,b]\rightarrow \mathbb R$ be bounded functions and $g$ is increasing. Show that for every partitions $P$ and $Q$ of $[a,b]$ with $P\le Q$ we have $s(f,P,g) \le s(f,Q,g) \le S(f,Q,g)\le ...
1
vote
1answer
48 views

Pointers about the concept of 'division extensionality'?

When working a bit on another question (If $a \equiv b\pmod m$, then $\gcd(a, m) = \gcd(b, m)$), I discovered the following, which seems to be valid: $$ a = b \;\;\equiv\;\; \langle \forall d :: d ...
2
votes
1answer
139 views

Convergence of a power series function

Consider the following differential equation: $$w''(x)+p(x)w'(x)+q(x)w(x)=r(x)$$ with the initial condition of $w(0)=w_0,\ w'(0)=w_1$, and $$w_{n+2}=\frac{r_{n+2}-(n+1)p_0w_{n+1}-\sum_{k=0}^n w_k ...
3
votes
1answer
142 views

Providing a sketch for a proof before proceeding through the actual proof. [closed]

Question is pretty straightforward. My mathematics is sloppy, and I recognize my inaptitude in that my proofs are more or less too intuitive. My diagnosis dictates the fact that I attack a problem ...
1
vote
0answers
72 views

Examining every mathematical result in purely formal, ZFC language.

My main interest is physics. However, being self-taught in mathematics for the most part, my proofs tend to be more intuitive than it is acceptable. Yet, I recognize my inaptitude in rigor, and I ...
1
vote
2answers
230 views

Convergent sequences and proof

Prove that $\dfrac{1+n}{n^2}$ converges as $n \to \infty$ How do I go about constructing this proof? Can I use the definition that $\operatorname{abs}(a_n - L < \epsilon)$?
2
votes
3answers
327 views

Prove$\overline{(A \cap B \cap C)} = \overline{A} \cup \overline{B} \cup \overline{C}$ By Subsets

This problem I am trying to solve is one I alluded to in this thread: Proving By Subsets I am having difficulty with proof by subsets, so I am aware that I am missing steps; I would certainly ...
-3
votes
1answer
294 views

Proving By Subsets [closed]

I am currently trying to learn about conducting proofs by using subsets. In my textbook, there is an example on this very matter; however, the seem to do something that is in contradiction with what ...
2
votes
2answers
122 views

Is this proof using the pumping lemma correct?

I have this proof and it goes like this: We have a language $L = \{\text{w element of } \{0,1\}^* \mid w = (00)^n1^m \text{ for } n > m \}$. Then, the following proof is given: There is a $p$ ...
0
votes
1answer
407 views

Induction proof on covering a checkerboard with dominoes - don't think my proof is right.

So I'm trying to solve this problem and I think I'm on the write track, but my proof relies on a domino being divisible by 2, which I don't think is correct. The problem: Prove that a $2^n \times ...
8
votes
2answers
928 views

Prove that $\mathcal{P}(A)⊆ \mathcal{P}(B)$ if and only if $A⊆B$. [duplicate]

Here is my proof, I would appreciate it if someone could critique it for me: To prove this statement true, we must proof that the two conditional statements ("If $\mathcal{P}(A)⊆ \mathcal{P}(B)$, ...
6
votes
2answers
415 views

What quantifies as a rigorous proof?

Okay I have been thinking about this common combinatorial identity. $$\sum_{r=0}^{n} \binom{n}{r} = 2^n.$$ It is simple to prove this by induction, but it requires some annoying algebraic manipulation ...
5
votes
4answers
467 views

Proving that $\lim_{h\to 0 } \frac{b^{h}-1}{h} = \ln{b}$

Is there a formal proof of this fact without using L'Hôpital's rule? I was thinking about using a proof of this fact: $$ \left.\frac{d(e^{x})}{dx}\right|_{x=x_0} = e^{x_0}\lim_{h\to 0} ...
4
votes
2answers
84 views

If $x\lt y $ for arbitrary real x and y there exists a real r $r$ such that $x \lt r \lt y$ and hence infinitely many.

If $x\lt y $ for arbitrary real $x$ and $y$ there exists a real r $r$ such that $x \lt r \lt y$ Prove that there is at least one r satisfying this inequality, and hence infinitly many. I was ...
1
vote
3answers
2k views

Proving That The Product Of Two Different Odd Integers Is Odd

Okay, here is how I begin my proof: Let $q$ and $r$ be odd integers, then $q = 2k+1$ and $r = 2m+1$, where $k,m \in Z$. $q \times r = (2k+1)(2m+1) \implies q \times r = 4mk + 2k + 2m + 1 \implies q ...
3
votes
2answers
294 views

Proof by contradiction: $ \emptyset \subseteq A$

I have to proof by contradiction that: let $ A $ a set and $ \emptyset $ the empty set, then $ \emptyset \subseteq A$; if $ \emptyset \nsubseteq A$ then $\exists x \in \emptyset ( x \notin A ) $ ...
0
votes
1answer
48 views

Showing the following language is not contex free

I need to show the following language is not context free via the Pumping Lemma. $$L = \{0^n\#0^{2n}\#0^{3n}\mid n \ge 0 \}$$ I was wondering if someone can help explain how to begin such a proof. ...
2
votes
3answers
106 views

proof of combinatoric/using pascals theorem

prove that, for even values of $n$, $$\sum_{i=0}^{n/2}\binom{n}{2i}= 2^{n-1}\;.$$ I tried using pascals theorem to help prove this with no success
1
vote
1answer
30 views

How to show any space is dually scattered?

As the title explains, how to show any space is dually scattered? A topological space $X$ is dually scattered if for any neighbourhood assignment $\{ O_x : x \in X \}$ there is a scattered ...
0
votes
1answer
168 views

Einstein Summation Proof, Does this count as an expansion?

Prove curl grad $\phi = 0$ for all scalar fields. $\phi$ (i.e. $\nabla \times \nabla \phi \ 0$ using Einstein summation notation only, no term by term expansion. Well, first step is to set up in ...
4
votes
0answers
71 views

Arbitrary ratio sequences on a partition of $\mathbb{R}$ (Partition regularity of fixed ratio sequences)

Background: This question arose purely recreationally and doesn't really fit into any context that I know of. Let $A \sqcup B = \mathbb{R}$ be a partition of the ...
3
votes
1answer
158 views

Magnitude of a vector, cubed, in Einstein Summation Notation

Evaluate $\nabla \cdot (r^3v)$. The answer will be in terms of r. Where v represents the position vector and r represents the scalar magnitude of the position vector. I started by writing this in ...
2
votes
1answer
142 views

Can I use Schwartz's Lemma to prove that $f(0)=0$ and $\operatorname{Re}f(z)\rightarrow 0$ implies $f(z)=0$ for all $z\in\mathbb{C}$?

Problem. Suppose that $f(x)$ is an entire function satisfying $f(0)=0$ and $\operatorname{Re}f(z)\rightarrow 0$ as $|z|\rightarrow \infty$. Show that $f(z)=0$ for all $z\in \mathbb{C}$. The ...
2
votes
2answers
222 views

Einstein Summation Notation Interpretation

A vector field is called irrotational if its curl is zero. A vector field is called solenoidal if its divergence is zero. If A and B are irrotational, prove that A $ \times $ B is solenoidal. I'm ...
1
vote
2answers
147 views

Theorem of Eulerian Path

I am a little bit confused by the proof of Theorem 1.8.1 (Euler 1736) on the page 23 of the textbook Graph Theory by Diestel. Theorem 1.8.1 (Euler 1736) A connected graph is Eulerian if and only if ...
3
votes
1answer
60 views

How might one go about proving this poorly worded theorem about divisibility with the number 3?

I was messing around and found something interesting, at least to me. Although I may not know how to delicately word this, so I hope it is clear. Claim: Each natural number $n$, whose sequence of ...
5
votes
2answers
168 views

Sipser Pumping Lemma Clarification

In a Theory of Computation book I am using, the explanation of Pumping Lemma is not bad, but some parts of it are not clear to me. Here is the Definition of Pumping Lemma: If A is a regular ...
2
votes
1answer
278 views

The minimum number of mice required to find a poisoned bottle.

Here's an interesting question. There are $1000$ mice and $1000$ bottles (numbered $1,2,3....1000$). One of the bottles is poisoned. You can mix the solution with the other bottles any number of ...
8
votes
1answer
226 views

Proof that the set of doubly-stochastic matrices forms a convex polytope?

Does the set of all doubly-stochastic matrices form a convex polytope? In general, I wonder how the proofs of convexity and geometry can be established for sets of matrices of this kind? Anything to ...
0
votes
0answers
27 views

Second-Order Random Choice Proof

Given $G = (V,E)$ ;$ |V| = n, |E| = m$ then choose $T$ with $t$ vertices uniformly I have to proof the graph theory as $$E[X] - E[Y] \geq a$$ Which $$E[X] \geq \frac{(2m)^t}{n^{2t-1}}$$ X is random ...
12
votes
2answers
337 views

6 point lying on a common circle

$Z$ is an interior point of segment $XY$. Three semicircles are drawn over segments $XY$, $XZ$ and $ZY$ on the same side. The midpoints of the arcs are $M1$, $M2$ and $M3$ respectively. A circle ...
2
votes
1answer
647 views

lim sup inequality proof - is this the right way to think?

I have tried to read many proofs of this but I'm not sure I get it, so please bare with me. Show that $\lim_{n \rightarrow \infty} \sup (a_n+b_n) \leq \lim_{n \rightarrow \infty} \sup (a_n)+lim_{n ...
3
votes
3answers
467 views

Tetrahedron problem (proving)

Prove that if $P$ is the intersection of the altitudes of a tetrahedron $ABCD$ and $r$ is the circumradius then $PA^2+PB^2+PC^2+PD^2=4\cdot r^2$.
2
votes
2answers
298 views

What is the fastest (most reliable) way to calculate the Frenet frame, curvature and torsion, given r(t)?

Vector calculus, just learned about the Frenet frame and curvature and torsion. Naturally, we have to calculate a lot of these on homework and exams. However, the formulas that we are given for ...
2
votes
3answers
2k views

Proving that a Turing Machine that only accepts even length strings is undecidable

I need to prove that a Turing Machine that only accepts even length strings in undecidable. The proof I was thinking is explaining the following: Given an input that contains even length strings, if ...
0
votes
3answers
73 views

(Dis)prove that: $\forall a,b \in \Bbb Z, \space (a \mid b^2 \land a \le b) \to a \mid b$

So I'm trying disprove this statement. Well, I'm pretty sure it's wrong because it doesn't work when $a = 0$ . I'm just not sure if all I need to do is give that counterexample, or if there is a way ...
3
votes
2answers
87 views

Totient function and Euler's Theorem

Given $\big(m, n\big) = 1$, Prove that $$m^{\varphi(n)} + n^{\varphi(m)} \equiv 1 \pmod{mn}$$ I have tried saying $$\text{let }(a, mn) = 1$$ $$a^{\varphi(mn)} \equiv 1 \pmod{mn}$$ ...
10
votes
8answers
250 views

Examples of “transfer via bijection”

On some occasions I have seen the following situation: We want find out whether a set of a given cardinality $\varkappa$ has some property P. If this property is invariant under bijective maps, then ...
7
votes
2answers
334 views

Proof of the standard algorithm for addition?

Can anyone present or point me toward a formal proof of the validity of the standard algorithm we all use for addition (line up your numbers one over the other, add the ones-place, carrying 'excess' ...
1
vote
1answer
82 views

Structural induction on expressions

Let $S$ be a recursively defined set of expressions. Base case, $v\in S$ Constructor Case: if $x\in S$ and $y\in S$, then $(x+y)\in S$ and $(x * y)\in S$ Prove by stuctural induction that for ...
2
votes
1answer
112 views

Proof method for expression involving quantifiers

Assume that I want to prove $\forall x \forall y P(x,y)$ where $P(x,y)$ is some proposition. But, instead, if it were easier to prove $\forall y \forall x P(x,y)$ and if I prove the latter one just ...
1
vote
3answers
174 views

Help with Big O and Big Omega problem.

this is a homework problem: 1) $$ \text{Let }f(n) = n^2+5000 \text{ and } g(n) = 5(n^2) + 100.\text{ Prove formally that }f(n) = \theta (g(n)) $$ My attempt: a)Prove f(n) is $ O(g(n)) $: When $ n ...
1
vote
3answers
315 views

How do I setup a proof using contradiction.

In specific how can I setup a contradiction proof if $3n+2$ is odd then $n$ is odd? I don't want the answer. I just want to know how to set up the proof by contradiction. I think that I should assume ...
4
votes
2answers
567 views

Prove by Combinatorial Argument that $\binom{n}{k}= \frac{n}{k} \binom{n-1}{k-1}$

This is a question from my first proofs homework and I am confused about the combinatorial argument aspect. I already did the algebraic proof. I think I am supposed to put into words what both sides ...
1
vote
2answers
130 views

Tricky well defined function and induction

Lets define a function $f$ such that $\Bbb N \times\Bbb N \to\Bbb N$. It takes two natural numbers as inputs and also outputs a natural number. Let $f$ have the following properties $f(a,b) = ...
4
votes
1answer
61 views

Prove that L shapes can be filled with smaller L shapes [duplicate]

Prove that all any size L shape, following regular ratio of an L, can be filled with smaller L's
2
votes
2answers
90 views

L shaped region

Prove, using the well-ordering principle, that, for all $n\geq 1$, an $\mathsf{L}$-shaped space with two sides of length $2n$ and four sides of length $n$ can be tiled using some number of 3 square ...
3
votes
1answer
319 views

Proving a function is big O

How would I go about proving a function is big O? Do I use the regular proofs (direct, contrapositive, contradiction)? Example: Prove that $x^n$ is $O(n!)$ for every real number $x$. My proof by ...
42
votes
7answers
2k views

Could I be using proof by contradiction too much?

Lately, I've developed a habit of proving almost everything by contradiction. Even for theorems for which direct proofs are the clear choice, I'd just start by writing "Assume not" then prove it ...
2
votes
2answers
91 views

Proof inequality

I can't proof this inequality. $$ 1 + \sum_{k=0}^{n-1}\biggl(\prod_{j=0}^{k-1}(1+w_j)\biggr)w_k \leq \prod^{n-1}_{k=0}(1+w_k) $$ where $(w_n)$ is a nonnegative sequence. Any idea? Any helpful trick? ...