For questions about the formulation of a proof, not about the mathematics behind it.

learn more… | top users | synonyms

5
votes
2answers
72 views

Proof using induction: $n! > n^2$, for $n\geq4$

Proof using induction: $n! > n^2$, for $n\geq4$ Basis: For n = 4, we have: $4! > 4^2$ $24 > 16$ (TRUE) Inductive step: By the induction hypothesis: $k! > k^2$ $(k+1)k! > (k+1)k^2$ ...
0
votes
1answer
28 views

Prove: If $G$ and $H$ are disjoint $G_{\delta}$, then there exists an $F_{\sigma}$ set $B$ such that $H\subseteq B$ and $B\cap G=\emptyset$

Problem. Prove: If $G$ and $H$ are disjoint $G_{\delta}$ sets, then there exists an $F_{\sigma}$ set $B$ such that $H\subseteq B$ and $B\cap G=\emptyset$. Please HELP. Thank you..
0
votes
1answer
28 views

Questions about proving by cases for a biconditional

Let's say I have a predicate, $\forall x\in h(x) : f(x) \leftrightarrow h(x) \lor g(x)$ I understand that when Q $\implies$ P that we do cases and assume both h(x) and g(x) in each case, however when ...
0
votes
1answer
42 views

How to prove that $\forall n \in \Bbb{N}$, $n+\lfloor \sqrt{n} +\frac12 \rfloor$ cannot be a complete square?

Here is my thinking process: Let $k=4n$, so $n=\frac{k}{4}$, then $k\in \Bbb{N}$. Then the expression becomes $\frac{k}{4}+\lfloor \frac{1}{2}\sqrt{k} +\frac12 \rfloor$. But then I don't know how to ...
2
votes
1answer
31 views

How to prove that $\forall x\in \Bbb{Q}:\ x\ne 0\implies [\exists a,\ b\in \Bbb{I}: x=a\cdot b]$ if $\Bbb{I}$ is set of irrational numbers?

I initially thought contrapositive would be easier, so I wrote $\forall x\in \Bbb{Q}:\ [\forall a,\ b\in \Bbb{I}: x\ne a\cdot b]$ $\implies x=0$. But I still had no idea how to start. Could someone ...
0
votes
1answer
24 views

Show that the collection $\tau^*=\{(a,b]:a,b\in \mathbb{R},a<b\}$ is a basis for a topology in $\mathbb{R}$

Show that the collection $\tau^*=\{(a,b]:a,b\in \mathbb{R},a<b\}$ is a basis for a topology in $\mathbb{R}$.Help me on this.Thank you very much in advance..
0
votes
3answers
33 views

Let $X$ be a topological space and $A\subseteq X$. Prove $\operatorname{Fr}(A)=\emptyset$ iff $A$ is both open and close in $X$.

Let $X$ be a topological space and $A\subseteq X$. Prove $\operatorname{Fr}(A)=\emptyset$ if and only if $A$ is both open and close in $X$. Can you help me on this?
1
vote
4answers
51 views

Terminating each branch of a proof with $\square$

My question is a variation on this one. I have a proof which divides at the top level into a number of mutually exclusive cases, with further partitioning within that. Is it reasonable to place a ...
0
votes
2answers
54 views

how to prove that invertible matrix and vectors span the same space?

Given $M$ is an invertible matrix, and {$\vec{v_1}...\vec{v_k}$} spans $R^n$, then {A$\vec{v_1}...A\vec{v_k}$} also spans $R^n$ What does matrix invertibility have to do with span?
2
votes
1answer
67 views

What is the right way to show that $\lim\limits_{n \to \infty} f_n(x_n) = f(x), x_n \to x$

There is a question (could be from Ruddin's real analysis text) To show that $\lim\limits_{n \to \infty} f_n(x_n) = f(x)$, is equivalent to show that: $$|f_n(x_n) - f(x)| < \epsilon$$ Which ...
1
vote
1answer
26 views

A newbie need some help in proof building. How to prove that any regular expression admits a disjunctive normal form?

Prove that any regular expression admits a Disjunctive Normal Form, i.e.: R = R1 U R2 U … Rn , where neither Ri contains a union. I would like some help with this question. If you could push me into ...
2
votes
3answers
35 views

Deductive proof in natural numbers - division

Prove, using induction rule: $$\forall_{n\in N} \left (2^{2n+1} + 3n + 7 = 9c\right)$$ $$c\in N$$ 1. I checked with 1 : works 2. I assumed that it is true for some natural number k 3. I plugged in ...
0
votes
2answers
45 views

$\gcd(3k+2,5k+3) = 1$ for all integers $k$

I'm doing this question for an assignment, the question is: Prove: if $k\ \epsilon\ \mathbb N$, then $gcd(3k+2, 5k+3)=1$. I was going to do it by induction, so what I have so far is: $n\ |\ 3k+2$ ...
3
votes
2answers
94 views

proof - $(x,y) = (4,6)$ is the only solution for $x^3 + x^2 - 16 = 2^y$

I saw this question and on seeing the answers I believed it did not have to be so complicated. The pair $(x,y) = (4,6)$ only fits the equation. Find all possible $(x, y)$ pairs for $x^3 + x^2 - 16 ...
2
votes
1answer
42 views

How should the word “determine” be interpreted?

My question is this, I am asked to prove that two sets A and B determine the same set C iff some condition is satisfied. How should I understand the above statement? In particular, how should the ...
0
votes
1answer
20 views

Elementary proof: division by integer makes real number smaller.

It's been so long since I took discrete math, maybe someone here can help me with what ought to be a straight forward and simple proof. Effectively I want to show this: Let a and b be positive ...
0
votes
2answers
28 views

$1^{p−1}+2^{p−1}+…+(p−1)^{p−1}≡−1 mod p$

I need help proving the following Let p be an odd and prime, prove that $1^{p−1}+2^{p−1}+…+(p−1)^{p−1}≡−1 mod p$
1
vote
1answer
41 views

Proof convergence implies $\liminf = \limsup$.

I have yet to see very straightforward proofs that convergence of a sequence implies equality of $\liminf$ and $\limsup$, so I'd like to attempt to present one here: Statement: If $\{a_k\}$ ...
0
votes
0answers
11 views

Supremum , upper bound, maximum hesitation.

Just a quick question. Say I have a set and I proved that it has no upper bound. Can I surely state that if it has no upper bound this it has no supremum and maximum? If it's true. Does it holds ...
0
votes
0answers
9 views

How to show by induction that for $f(t) = \sum_{j=0}^k a_j t^j$ we have $\Delta^k f(t) = k!a_k$?

I am asked to prove by induction that for $f(t) = \sum_{j=0}^k a_j t^j$ we have that $\Delta^k f(t) = k!a_k$. For those who do not already know $\Delta$ is the backward difference operator, i.e., ...
0
votes
0answers
12 views

Transitivity Proof on graphs: computational or by hand?

I am stuck to transitivity consideration with graphs where $x^a,x^b$ are boolean monomials such as $x_1x_3$ and $x_5$, the cut sets contains $C=\{x^{C_i}=0\mid C_i\in C\}$, ...
0
votes
0answers
30 views

Sucint book request for mathematical logic

I want to read a sucint book for logic (50 pages would be nice) which summarizes everything you need to read and write rigorous mathematical proofs. I want a book that explains, for instance, ...
1
vote
1answer
48 views

Efficient way to show Graph is a tree in proof

I am new to inductive proofs in general, and brand new to graph proofs. I am looking for an efficient way to declare that the induced subgraph prior to application of induction is, in fact, a tree. ...
0
votes
1answer
39 views

Set theory proof for $\min C = \bigcap _{\alpha \in C} \alpha$

Let $C$ be a set of ordinals a) $\sup C$ is the least ordinal $\beta$ such that for all $\alpha\in C$, $a\leq \beta$. b) If $C$ is transitive (and thereby ordinal), then $\sup C \notin C$ if an only ...
6
votes
2answers
104 views

Is it good to use mean value theorem in $\epsilon-\delta$ continuity proofs?

I wanted to prove $f(x) = \cos(x)$ is continuous using $\epsilon-\delta$ proof Couple of posts on MSE appealed to MVT to resolve this problem. Namely: $\exists c \in [x,x_o]$ s.t. ...
1
vote
0answers
22 views

How does one go about describing an algorithm? [closed]

I created an algorithm, and I was wondering what important information I should add to my paper. I know this isn't a concrete question, but please help!
3
votes
2answers
57 views

Difference operator: Proof by induction that $\Delta^k (X_t)= k!a_k+\Delta^k (Y_t)$

Hello I am having issues with the following exercise. I have to prove that $$\Delta^k (X_t)= k!a_k+\Delta^k (Y_t)$$ where $X_t = m_t +Y_t=\sum_{j=0}^ka_jt^j+Y_t$ for $t \in \mathbb {Z}$. Note: ...
4
votes
1answer
82 views

How to prove $\log_23$ is irrational?

I think using contradiction is good. Assume $\log_23$ is rational Then $\exists p\in \Bbb{Z}, q\in \Bbb{Z}^*: \log_23 = \frac{p}{q}$ ###$p, q$ has no common factors. Then $3^{q}=2^{p}$ ... Here ...
1
vote
1answer
33 views

How to prove $\forall x,y\in\mathbb{R} : x^3+x^2y=y^2+xy \Leftrightarrow y=x^2\lor y=-x?$

Let $x,y\in\mathbb{R}$ Assume $x^3+x^2y=y^2+xy$ Then $x^2(x+y)=y(x+y)$ Then either $(x+y)=0$ or $(x+y)\ne0$ Assume $x+y=0$ Then $y=-x$ Assume $(x+y)\ne0$ Then $y=x^2$ Then $x^3+x^2y=y^2+xy ...
4
votes
0answers
67 views

How to prove $\forall x,y\in\mathbb{R}: x^2+y^2 = (x+y)^2 \Leftrightarrow x=0\lor y=0?$

The question I really have is the structure and I am not sure to use pack-unpack or not. Here is my try: Let $x,y\in\mathbb{R}$ Assume $x^2+y^2 = (x+y)^2$ Then $x^2+y^2 = x^2+2xy+y^2$ #by ...
0
votes
2answers
72 views

Proving $x \lt y \iff x^n \lt y^n $

Let F be an ordered field. $ x,y \in F, x,y \ge 0 $ and $n \in N$ Prove that: $$ x \lt y \iff x^n \lt y^n$$ Now I'm choosing to use induction to prove this (is that the only way to prove this?) ...
0
votes
0answers
34 views

Proof of Thue's lemma

Here is the statement : "Let $m\in \mathbb{N}$, $a \in \mathbb{Z}$, if $\gcd(a,m)=1$ then there exists $x,\ y \in \mathbb{N}^*$ such as $x, y < \sqrt m$ and $ax \pm y \equiv 0 \ [m]$ ". I do not ...
1
vote
2answers
27 views

Matrices Invertibility Existence

I have two square matrices, $A$ and $B$, and I know that $AB = I_n$, how do I then show that $A$ is invertible? I've been considering determinants, and I have started off by assuming that $A$ is not ...
0
votes
2answers
23 views

Let $D$ be the open disc centred at $i$ and radius $3$. Prove that $|z-\omega|<6$ for all $z,\omega \in D$

I can see why it is less than $6$ because the longest distance is from either side through the origin and it can't be $6$ because it is an open disc. I think to prove formally I should use the ...
6
votes
3answers
83 views

Construct a sequence of measureable sets $E_1\supseteq E_2 \supseteq E_3 \supseteq \cdots$ such that $\mu(E_n)=\infty$ for each $n$ but …

Construct a sequence of measureable sets $E_1\supseteq E_2 \supseteq E_3 \supseteq \cdots$ such that $\mu(E_n)=\infty$ for each $n$ but $$\mu\left(\bigcap_{n=1}^\infty E_n\right)=0$$ Claim: Let ...
0
votes
0answers
17 views

Proving an statement including series

I am going to prove the following lemma. I would appreciate it if you can help me. Lemma: If $S\in N\cup\{0\}$ and for any $\lambda \geq 0$, we have $S\geq \lambda$, then, $\frac{S}{\lambda}\left ...
2
votes
2answers
29 views

Use of “yield” in proofs

I have started to learn discrete maths on my own, and while writing my first proofs, I am sometimes drawn to use the verb "yield" (e.g. Let $a=2b²+5b+4$ for some integer b. Since $\Bbb Z$ is closed ...
0
votes
1answer
27 views

How to prove if $A \subseteq B$ then $B \setminus (B \setminus A) = A$ using forward-backward method?

From "Introduction to Real Analysis (Dover books)" Exercise 1.15.1.g is to prove: if $A \subseteq B$ then $B \setminus (B \setminus A) = A$ It indicates to use the forward backwards method. I an ...
2
votes
1answer
41 views

Prove by induction that the number of derangements of length $n$ is $D_n = (n-1)(D_{n-1}+D_{n-2}), n>2$

Prove by induction that $$ D_n = (n-1)(D_{n-1}+D_{n-2}), n>2 $$ where $D_n$ is the number of derangements of $n$ objects. I am a little rusty in induction, and here's what I have done so far. ...
0
votes
1answer
14 views

How to properly write proof to show Cauchy and Convergence at the same time?

I am seriously confused about how to write a proper proof that show cauchy and convergence at the same time. This is because there are two $N$s involved. One is that for every $m,n \geq N$ sequence is ...
1
vote
2answers
40 views

Proving by arriving to truth from an assumption.

It's easier to explain the question on an example. Let's consider this pretty simple problem: We have to prove that $(-1)a=-a$ where $a \in R $. My question is, can I prove this in the following ...
6
votes
0answers
123 views

How do people pick $\delta$ so fast in $\epsilon-\delta$ proofs

For example, in a proof that shows $f(x) = \sqrt(x)$ is uniformly continuous on the positive real line, the proof goes like: Let $\epsilon > 0$ be given, and $\delta = \epsilon^2$.... Or to ...
2
votes
0answers
96 views

Would this be an easier way to prove the twin prime conjecture?

Prove: For every prime, $p\geq7$, there exists some $pn$ such that $p$ is its largest prime factor, $n$ is a positive integer, and $(pn-4, pn-2)$ is a twin prime. My questions: Would this indeed ...
0
votes
1answer
19 views

The number of k-element multisets whose elements all belong to [n]

$\binom{n+k-1}{k}$ Hello. The above formula refers to the number of k-element multisets whose elements all belong to [n]. I am unsure of the proof, particularly the proof involving bijections. Could ...
0
votes
1answer
62 views

Prove that if $(A,<)$ is a well ordering, then $(A,<)\nless(A,<)$

Prove that if $(A,<)$ is a well ordering, then $(A,<)\nless(A,<)$ I'm trying to teach myself set theory for a course I am taking and am struggling a bit here. I need to suppose for ...
1
vote
0answers
30 views

show that any two polynomials in $ F[x] $ are congruent modulo a nonzero polynomial $ p(x) $

Is the below proof correct, and is there a more succinct way to prove this? I just went directly and showed (I think) $$(\forall f(x),g(x) \in F[x])( \exists k(x) \in F[x])(f(x)-g(x)=p(x)k(x))$$ ...
0
votes
1answer
22 views

Claim: Given ODE $\dot x = f(x)$, $f$ is locally lipschitz, then $x$ must be locally lipschitz as well

Can someone prove or disproof the claim: Given a locally lipschitz vector field $f$ with associated ODE $\dot x = f(x)$, then the solution $x$ must be locally lipschitz Note: local lipschitz ...
3
votes
1answer
56 views

Proving an if and only if statement

Suppose I am trying to prove a statement in the form A if and only if B. I know I need to prove that If A, then B If B, then A I know that 1 is equivalent to proving "If not B, then not A". My ...
0
votes
1answer
28 views

proof - infinite pair integers $a$ and $b$ such that $a + b = 100$ and $\gcd(a, b) = 5$

Prove that there are an infinite pair integers $a$ and $b$ such that $a + b = 100$ and $\gcd(a, b) = 5$. I don't know how to proceed with this. Especially, proving that they are infinite. There was ...
0
votes
3answers
67 views

How many ways are there to prove that there is no largest prime? [duplicate]

Is there any other proof by which I can show that there is no largest prime? I saw an example where it is proved with contradiction.(Idea is basically that of Euclid's proof) Imagine that the ...