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

1
vote
1answer
39 views

Proving a Special Case of a Limit Theorem

I'm having trouble proving a special case of the limit theorem below. I attempted a proof by contradiction that appears to me to make sense in the first direction but I'm not able to come up with ...
0
votes
1answer
36 views

Big Omega Proof for $5^n = \Omega(6^n)$

I got the Big-O ($\mathcal{O}$) proof but I am having troubles with the Big Omega ($\Omega$) proof. I am trying to prove $6^n$ is not the tightest bound for $5^n$. Is this logic true: $7^n$, $8^n$ ...
2
votes
3answers
87 views

Bijective Proofs

Give a bijetive proof: The number of subsets [n] equals the number of n-digit binary numbers. I do not understand how to do this problem, can someone help me figure it out? I have this so far, Let ...
18
votes
1answer
653 views

Does an elementary solution exist to $x^2+1=y^3$?

Prove that there are no positive integer solutions to $$x^2+1=y^3$$ This problem is easy if you apply Catalans conjecture and still doable talking about Gaussian integers and UFD's. However, can this ...
1
vote
1answer
37 views

How to “prove” the following very simple vector identities

For my upcoming exam, I have to be able to prove the following four statements (among a bank of others). Though they are pretty obviously true, I'm struggling to come up with a way to prove them ...
-1
votes
3answers
46 views

Prove $ f(A1) \setminus f(A2) \subseteq f(A1 \setminus A2) $

here is my proof but it only works for functions that have an inverse:
0
votes
1answer
25 views

Extending a theorem true over the integers to reals and complex numbers

How does one generally extend a theorem proved over the integers to the real numbers and beyond e.g. induction proofs, De Moivre's Theorem? I am aware that to extend a theorem proved over ...
0
votes
3answers
51 views

Show that 1 is the supremum of $S = \{ x \epsilon R: x^2 < x \}$

I'm still new to proof writing so I was wondering if I could have a little help organizing my thoughts on this, I attempted this proof in a slightly oblong way that is probably not the standard, but I ...
0
votes
1answer
31 views

rewrite $(\sqrt{5} + 2)(\sqrt{5}-2) = 1 $ until…

"rewrite $(\sqrt{5} + 2)(\sqrt{5}-2) = 1 $ until you have an equation with $\sqrt{5}$ on the left and a ratio of two expressions involving $\sqrt{5}$ on the right." Ok..All i need to know is if i'm ...
2
votes
1answer
31 views

Finding a bound on a specific value of a holomorphic function

Let $f$ be a holomorphic function on $\overline{D(0,1)}$ such that $|f(z)| \leq M,$ if $|z|=1$ and $Im(z) \geq 0$ and $|f(z)| \leq N, $ if $|z|=1$ and $Im(z) <0.$ Could anyone advise me how to ...
-4
votes
2answers
32 views

Suppose S and T are two sets. Prove that if (S ∩ T) = S then S ⊆ T

I'm new to this entire proof thing, and I am so confused Suppose S and T are two sets. Prove that if (S ∩ T) = S then S ⊆ T Please help me
0
votes
1answer
25 views

If $a \in \mathbb{N}$, prove that gcd$(a, a+2)$ is $1$ if $a$ is odd and $2$ if $a$ is even.

Once again the problem is: If 'a' is an element of N, prove that gcd(a, a+2) is 1 if 'a' is an odd number, and 2 is 'a' is an even number. I really have no idea on how to prove this, and I'm brand ...
0
votes
1answer
23 views

Introduction chapter Exercise Q3 from “How to Prove It: A Structured Approach”

The following question is from the book "How to Prove It: A Structured Approach" Second Edition. Theorem 3 : There are infinitely many prime numbers. Euclid's proof Introduction Chapter : Exercise ...
0
votes
3answers
50 views

Is my arithmetical proof using induction correct?

The exercise 2.b of my textbook ask me to prove that: $$\text{(P): }\;\forall n\in \mathbb{N}, 13\;|\;(3^{n+2}+4^{2\cdot n+1})$$ I would like to know if my proof is correct and if not what I need to ...
6
votes
4answers
1k views

There exist no integers for which $x^2-4y=2$

I am working on a new exercise in my textbook: $$\text{Prove that: (P): }\;\nexists \;x,y \in \mathbb{Z}, x^2-4\cdot y = 2 $$ I am stuck and I would really like to see a correct proof so I can move ...
1
vote
1answer
109 views

The set of rational numbers in the interval $(0,1)$ cannot be expressed as the intersection of a countable collection of open sets

The set of rational numbers in the interval $(0,1)$ cannot be expressed as the intersection of a countable collection of open sets I found this proof on a certain web page A direct proof would be ...
0
votes
1answer
33 views

Show that are logically equivalent

Can you answer me , please. 1- Show that (p→r)∧(q→r) and (p∨q)→r are logically equivalent 2- show that (p → r) ∨ (q → r) and (p ∧ q) → r are logically equivalent without truth table .
2
votes
2answers
31 views

Induction Proof without Explictly Using The Induction Hypothesis?

I have encountered several problems where one can prove the desired result without actually needing the induction hypothesis. More specifically, you basically just pick $n \in \mathbb{N}$ and run ...
4
votes
2answers
128 views

finding the difference of perfect squares

Find the difference between the smallest perfect square larger than one million and the largest perfect square smaller than one million. I did not want to use a calculator for this question. I ...
0
votes
0answers
13 views

Proving modular hash function

I am having trouble getting started with the following problem : Suppose that keys are t-bit integers. For a modular hash function with prime M (the number of hash indexes), prove that each bit has ...
0
votes
3answers
101 views

Proving that the square root of 5 is irrational

Prove that $\sqrt{5}$ is irrational. I begin with the identity $(\sqrt{5} + 2 )(\sqrt{5} - 2 ) = 1$. Then I am told to extract $\sqrt{5}$ from the first or second factor and consider it to be ...
0
votes
2answers
39 views

How to prove the $\lim_{x\to 1} \frac{1}{\log x}$ does not exist.

How to prove the $\lim_{x\to 1} \frac{1}{\log x}$ does not exist. I'm not really sure how to proceed with this one. I have two ideas at hand, proof by contradiction or a proof using the Sequential ...
0
votes
1answer
15 views

Proving a statement with two variables by complete induction

I was recently introduced to this topic and I'm trying to prove Tue following statement. For most of numbers, m^n => n^m So I derived this into something that could be proved by induction... The ...
0
votes
1answer
46 views

How to write a formal proof of the statement: For all real numbers $x$, if $x \ge 1$ then $\frac{3|x-2|}{x} \le4$

For all real numbers $x$, if $x\ge1$ then $\frac{3|x-2|}{x} \le 4$ I understand that I must algebraically show how to build on $x\ge1$ to reach $\frac{3|x-2|}{x} \le4$, but cant for the life of me! I ...
1
vote
2answers
77 views

Evaluate $\begin{align} \int^{\infty}_{0} \dfrac{x^\alpha}{(1+x^2)^2}\end{align}dx, \ -1 < \alpha<3.$

Evaluate $\begin{align} \int^{\infty}_{0} \dfrac{x^\alpha}{(1+x^2)^2}\end{align}dx, \ -1 < \alpha<3.$ May I verify if my solution is correct? Thank you. Consider ...
0
votes
1answer
24 views

Alternative ways to prove an easy set relation

I have a simple set relation, which is almost trivial to prove, but surprisingly, I can only prove it with an "indirect" method, which is bugging me: Let the set $L$ be a subset of $\mathbb{R}^n$. ...
0
votes
0answers
29 views

Prove that $dim(V)$ is an even number

Let $V$ vector space so that $dim(V)=n$ and let $T:V\to V$ a linear transformation so that $Im(T)=N(T)$. Prove that $dim(V)$ is an even number I have no idea how to star the problem. Can you give a ...
0
votes
1answer
27 views

Prove that every element of $V$ can be expressed as $w+cv_0$ for some $w\in \ker(T)$ and $c\in \mathbb R$

Let $V$ be a vector space over $\mathbb R$ and let $T:V\to \mathbb R$ a linear transformation. Suppose $\ker(T)\neq V$ and let $v_0\in V$ so that $v_0\notin \ker(T)$. Prove that every element of $V$ ...
0
votes
2answers
54 views

Natural deduction: given premises, conclude $M \lor E$. [closed]

I need to prove that the following argument is valid using Natural Deduction: 1.  $[\lnot (B \lor \lnot I) \rightarrow (\lnot L \land J)]$ 2.  $[\lnot L \rightarrow (M \land B)]$ 3.  $\lnot (B ...
1
vote
0answers
18 views

Application of Sturm comparison theorem

Let $w(x), q(x)$ be continuous functions on $[a,b]$ and $q(x) < 0, \forall x \in [a,b].$ Could anyone advise me how to use Sturm comparison thm to show any non trivial solution to $y^{\prime\prime} ...
1
vote
2answers
59 views

How to prove that we can switch two $\forall$?

This is true? See a simple proof (High-school level) Thanks e.g: $$\forall x, \forall y\;P\;\text{is true}. \iff \forall y,\forall x\;\text{P is true}$$
2
votes
1answer
24 views

Distinct elements in the Union and Intersection of A and B

Take a set $x$ with $10$ distinct elements. Rule: Everytime you have two subsets, $A$ and $B,$ you also have $A\cup B$ and $A \cap B.$ What is the maximum number of subsets you can have such ...
0
votes
0answers
25 views

Lipschitz in any convex compact subset of a Domain.

Need a little help getting started on this one. Let $ f \in \text{C}\left[ Q, \mathbb{R}^n \right], Q \subset \mathbb{R}^n$. Assuming $f(t,x)$ has continuous partial derivatives in $x$, show that ...
3
votes
1answer
19 views

No four points with pairwise distance 1 can be contained inside a halfdisk of radius 1.

An open disk $D$ of radius $1$ in the Euclidean plane is the set of points with distance less than $1$ to the center of the disk. An open half disk $H$ of radius $1$ is obtained by "cutting" $D$ ...
0
votes
1answer
24 views

Show that $h:D \to R$ is continuous in $D$.

I need to prove this: Suppose $f,g : D\to R$ are both continuous on $D$. Define $h: D\to R$ by $h(x)=max \{f(x),g(x)\}$. Show that $h$ is continuous on $D$. But I do not know how to attack this ...
1
vote
2answers
35 views

In complete graph, how can I prove ${n\choose 2} = {k\choose 2} + k(n-k) + {n-k\choose 2}$ for $0 \le k \le n$

I'm studying graphs in algorithm and complexity, but I'm not very good at math. How can I prove that ${n\choose 2} = {k\choose 2} + k(n-k) + {n-k\choose 2}$ for $0 \le k \le n$?
2
votes
2answers
55 views

Let $f$ be a holomorphic in $D(0,1)$, with Re$\,f(z) >0$ and $f(0)=1.$ Then $\lvert\, f'(0)\rvert\leq 2$ [closed]

Let $f:D(0,1) \to \mathbb{C}$ be a holomorphic function, such that $$ \mathrm{Re} \,f(z) >0\quad \text{and}\quad f(0)=1. $$ Could anyone advise me how to prove $\lvert\, f'(0)\rvert\leq 2 \ ?$ ...
1
vote
2answers
38 views

Help with a sequence proof problem

I have the following theorem to prove, and the book makes a certain suggestion that I don't understand. Theorem Suppose that the sequence $\{a_{n}\}$ converges to $l$ and that the sequence ...
2
votes
2answers
38 views

Finding a formula by conjecture.

I am told to consider the sum $2^0 + 2^1 + 2^2 + 2^3 + \cdots + 2^n$ for $n ∈ ℕ ∪ \{0\}$. Next, I am to find the value of the sum for $n= 0, 1, 2, 3, 4$. After I find those values, I am supposed to ...
0
votes
1answer
17 views

Application of the Rational Roots Theorem

Let f(x)=3x$^3$ - 40x$^2$ + 97x + 10 a. Find a rational number r such that f(r) = 0. (Hint: Use the rational roots theorem to narrow down possibilities for r.) So, I figured this part out. write r ...
0
votes
3answers
47 views

Prove that sequence $x_{n}=\frac{1}{2+1}+\frac{1}{2^2+1}+…+\frac{1}{2^n+1}$ has a limit.

Given following sequence: $$x_{n}=\frac{1}{2+1}+\frac{1}{2^2+1}+...+\frac{1}{2^n+1}$$ I have to prove that this sequence has a limit. So I think first of all I should prove that this is convergent ...
0
votes
0answers
25 views

What's the relationship between $\operatorname{bd}(A \cup B)$ and $\operatorname{bd}A \cup \operatorname{bd} B$?

$\renewcommand{\int}{\operatorname{int}}$ $\int(A \cup B)$ and $\int A \cup \int B$ $\operatorname{bd}(A \cup B)$ and $\operatorname{bd}A \cup \operatorname{bd} B$ $(A \cup B)'$ and $A' ...
0
votes
3answers
67 views

Prove that $1^{k} + 2^{k} + \cdots + n^{k}$ is $O (n^{k+1})$

I have the following to prove: $1^{k} + 2^{k} + \cdots + n^{k} \text{ is }O (n^{k+1})$ I have done the following: $$\frac {1^{k} + 2^{k} + \cdots + n^{k}}{n^k} \leq n$$ Am I on the right track? I ...
3
votes
4answers
580 views

How do I make this simple proof better (and more correct?)

Let $x$ and $y$ be real numbers. If $x\cdot{y}>\frac{1}{2}$, then $x^2+y^2>1$. Proof: We will prove with the direct method. Let $x$ and $y$ be real numbers. Since $$ x\cdot{y}>\frac{1}{2} $$ ...
0
votes
1answer
25 views

Prove If a set contains more vectors than there are entries in each vector, then the set is linearly dependent

I want to prove this theorem: If a set contains more vectors than there are entries in each vector, then the set is linearly dependent. That is, any set $\{ v_1,v_2,...,v_p \}$ in $\mathbb{R}^n$ is ...
0
votes
1answer
27 views

Prove 'if a | c and b | c, then lcm(a,b) | c'

Well, the title says it all really. The question is: Prove that if c is a common multiple of a and b, then c is a multiple of lcm(a,b) Nobody in my class has found a way to do it. Whatever I ...
0
votes
1answer
36 views

Conditions under which a conformal map cannot be extended holomorphically

Let $f$ be a conformal map from unit disk $|z| <1$ to square $D=\{x+iy \in \mathbb{C}:|x|<1,|y|<1\}.$ Could anyone advise me how to prove $f$ cannot be extended to holomorphic function ...
0
votes
0answers
36 views

Proof using complete induction

Consider the set $S \subset \mathbb{N}^2$ of ordered pairs of integers defined by the following recursive definition: • $(3,2) \in S$ (basis) • If $(x,y) \in S$, then $(3x−2y,x) \in S$ (recursive ...
1
vote
0answers
25 views

Check my proof - Linear Algebra

Still not completely confident with my capabilities in writing formal proofs so I thought I would ask for a check of this proof. Theorem Let $V$ and $W$ be vector spaces, and let $T$ and $U$ be ...
1
vote
1answer
20 views

Is there a proof for what I describe as the “recursive process of mathematical induction for testing divisibility”.

I was working on my homework for Discrete Math, and we were asked to "Prove: $6 | n^{3}+5n$,where $n\in \mathbb{N}$" my solution varied significantly from how I have seen it done by others. I noticed ...