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
2answers
149 views

Prove that at least one of the real numbers $a_1 , a_2 , … , a_n$ is greater than or equal to the average of these numbers

Prove that at least one of the real numbers $\,a_1 , a_2 , … , a_n$ is greater than or equal to the average of these numbers. What kind of proof did you use? I think I should use contradiction but I ...
1
vote
1answer
45 views

Prove if $a$ and $b$ are real numbers, and $a \neq b$ and $a > 0$, $b > 0$, then $\frac{(a+b)}{2} > \sqrt{ab}$

Prove if $a$ and $b$ are real numbers, and $a \neq b$ and $a > 0$, $b > 0$, then $\frac{(a+b)}{2} > \sqrt{ab}$ Using a backward proof: $\frac{(a+b)}{2} > \sqrt{ab}$ $\Rightarrow ...
1
vote
2answers
205 views

Uniform Convergence Involving $e^x$

my question is: Consider the Taylor polynomial of $e^x$ of order $n$ at $x=0$, or $P_n(x)=e^0 + e'^{(0)}x +...+\frac{e^{(n)(0)}x^n}{n!}$. Prove that the sequence {$P_n(x)$} converges uniformly to ...
1
vote
3answers
99 views

Proof theorem direct proof

For each theorem below, state whether or not the theorem is true and give either a direct proof, proof by cases or counter example to support your view Theorem: For any sets $A$ and $B$ such ...
0
votes
2answers
79 views

How can I prove that this equality is impossible?

I need to prove that: $$(6 + x^2) \mod 7 = 4$$ is not possible for $x\in \mathbb{N}$. I know the proof would be by contradiction (i.e. assume we have a value of $x$ that solves this equation ...
0
votes
0answers
49 views

Proof $G$ has a unique normal subgroup $H$ of order $p$

Let $p$ be a prime. $G$ is the group of functions $f(x)=ax+b$ from $\newcommand\Z{\mathbb Z}\Z/p\Z$ to $\Z/p\Z$ where $a$ belongs to $(\Z/p\Z)*$ and $b$ belongs to $(\Z/p\Z)$. I proved that $G$ is a ...
2
votes
0answers
39 views

How to Intuit/See Matrix Factorisation [GStrang P250 Ex 5.1A]

I beg leave for your forgiveness over the colours. Please enlighten me if there's a more efficient way. How is the determinant of the checkerboard sign pattern matrix, $ \begin{bmatrix} a(1, ...
0
votes
1answer
34 views

Advice for proving with induction scenarios with multiple chances for using the hypothesis.

I have done many, many questions about solving induction exercises. I managed to grasp a basic strategy: write all the information, take the statement you want to prove, try to apply the hypothesis ...
1
vote
1answer
66 views

Finding the explicit formula for the succession $x_0=2, x_{n+1} = 5x_n$ and proving it with induction

I'm trying to learn about recursion, first with this exercise: Find the explicit formula for the succession $$x_0=2, x_{n+1} = 5x_n$$ So, from what I've seen, I should test a bit. I see that the ...
-1
votes
1answer
48 views

Prove or disprove: If $B - A$ is nonempty, then $\overline{\overline{A}} < \overline{\overline{A \cup B}}$

Prove or disprove: If $B - A$ is nonempty, then $\overline{\overline{A}} < \overline{\overline{A \cup B}}$ Disprove (backwards proof): If $\overline{\overline{A}} < \overline{\overline{A \cup ...
0
votes
3answers
131 views

Prove that a circle has an infinite number of tangents

It seems obvious that a circle is comprised of the set of all points that are equidistant from one point, and that each point on the circumference of the circle represents a tangent. This seems to ...
0
votes
1answer
54 views

Defining an Infinite Matrix

Hey I am getting ready for my final exam and I'm having trouble figuring out this practice question: Let X be a random variable that takes values in {0,1,2,3,...}. It is known that: E(X) = ...
0
votes
3answers
43 views

Prove that tree has independent set

Prove that every tree with $n$ vertices has an independent set with the size of $\lceil \frac{n} {2} \rceil$. Okay, I think I understand the concept of this whole thing. I understand, that we are ...
-1
votes
2answers
91 views

prove that $f:X\rightarrow Y$ is surjective if and only if $f(f^{-1}(C))=C$

I need help with proving this: $f:X\rightarrow Y$ is surjective if and only if $f(f^{-1}(C))=C$ $C\subseteq Y$ Thanks.
1
vote
1answer
59 views

A confusion(possible book mistake) about one of the proofs in Spivak's Calculus?

In Chapter 5 - Function Limits, there is a proof that: if $|x - x_0| < 1; |x - x_0| < \frac{\epsilon}{2(|y_0| + 1)}; |y - y_0| < \frac{\epsilon}{2(|x_0| + 1)}$ then $|xy = x_0y_0| < ...
1
vote
4answers
55 views

check if $f(f^{-1}(D))=D$

I have to check whether $f(f^{-1}(D))=D$. I think this is not true but I'm stuck in my proof. Can somebody help me? Thanks in advance.
2
votes
0answers
52 views

proving $f^{-1}(C\cup D)=f^{-1}(C)\cup f^{-1}(D)$

I don't understand why I have to prove these: $f^{-1}(C\cup D)\subseteq f^{-1}(C)\cup f^{-1}(D)$ $f^{-1}(C)\cup f^{-1}(D)\subseteq f^{-1}(C\cup D) $ Why can't I do something like that: $x\in ...
0
votes
2answers
97 views

GCD and EEA Proof

Let n be an arbitrary positive integer. Express $\gcd(8n + 3, 5n - 2)$ as a function of $n$. Is the answer so trivial that all you need to do it multiply it out using EEA? So would $f(n) = (8n+3)x ...
3
votes
6answers
130 views

Inequality $\frac{x}{1+x} < \ln(1+x), \forall x>0$

Prove that $\frac{x}{1+x} < \ln(1+x), \forall x>0$. I wrote it as $e^x < 1 + x + (1+x)^x$ to see if it would make it any simpler. I do not think induction would work since that only works for ...
0
votes
1answer
71 views

Epsilon Limit Proof (Bridge to Abstract Mathematics)

For $(3n)$, how would I prove that the limit of $n$ approaching infinity does not exist? Obviously this would diverge but I'm not completely sure how to prove it. I know I have to use epsilon delta. ...
1
vote
2answers
63 views

Proving by induction inequalities that lack the variable on the right side.

Doing proof by induction exercises with inequalities, I got stuck on one that is a bit different from the others. There is no $n$ term on the rightmost part of the inequality: Prove that the ...
0
votes
1answer
429 views

Prove or disprove: If $A \subseteq B$ and $B$ is denumerable, then $A$ is denumerable

Claim: If $A \subseteq B$ and $B$ is denumerable, then $A$ is denumerable Proof: Assume $A \subseteq B$ and $B$ is denumerable, then it follows that $B$ is countable. Every subset of a countable set ...
19
votes
10answers
2k views

How to prove that either $2^{500} + 15$ or $2^{500} + 16$ isn't a perfect square?

How would I prove that either $2^{500} + 15$ or $2^{500} + 16$ isn't a perfect square?
2
votes
2answers
89 views

Proving by induction that $1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n}\le\frac{n}{2}+1$ holds for all $n \ge 1$

While looking at some examples of proof by induction related to inequalities, I had this one that I didn't quite get: Prove by induction that the following holds for all $n \ge 1$: ...
1
vote
2answers
135 views

Introduction to Analysis: The Riemann Integral

The following is a problem from Arthur Mattuck's book, "Introduction to Analysis." Page 265. Assume $f(x)$ integrable on $I$. Prove $F(x) = \int_a^x f(t)\,dt$ is continuous on $I$ How would I ...
4
votes
1answer
151 views

Solvability of the Quartic

In our Galois Theory classes we have been introduced to the idea that quartics can be solved by radicals. The course walks us through a construction that is designed to intuitively explain to us how ...
1
vote
1answer
47 views

how many elements does Ia have?

Let $A=\{1,2,3,4\}$. Let $F$ be the set of all functions from $A$ to $A$. Let $R$ be the relation on $F$ defined by $f,g \in F$ $f R g \Leftrightarrow |f(A)|=|g(A)|$ $f(A)=\{f(x): x\in A\}$ ...
3
votes
3answers
868 views

Proving Holder's inequality using Jensen's inequality

Let $p$ and $q$ be positive reals such that $\frac{1}{p}+\frac{1}{q} = 1$, so that $p,q$ in $(1,\infty)$. For $\vec a$ and $\vec b \in \mathbb{R}^2$ prove that $|\vec a \cdot \vec b | \leq ||\vec ...
0
votes
1answer
43 views

GCD's and Proofs

Let p and q be odd primes. Prove that gcd(p + q, p - q) = 2. I have considered EEA to multiply it out, but I'm unsure where to go from there.
0
votes
2answers
85 views

Let S = {1,2…10} Let R be the relation on P(S), the power set of S, defined by: for any X,Y ∈ P(S),

Let S = {1,2....10} Let R be the relation on P(S), the power set of S, defined by: for any X,Y ∈ P(S), XRY <=> X∩Y=∅ is it true that ∀X∈P(S),∃Y∈P(S) so that (X,Y)∈R? I dont know what is (X,Y)? ...
0
votes
2answers
39 views

What method would I use for this proof?

Show there are no integer, $x$ and $y$, that satisfy $x^{2} + 3y^{2} = 8$. I have no idea where to start unfortunately or what kind of method to start off with.
0
votes
1answer
789 views

Proving a tight bound on the worst case running time of an algorithm?

This exercise I don't understand what 'give a tight bound' implies here. The correct way to prove this is to consider that the runtime is in O and then use the definition of BIG O to prove that it ...
0
votes
1answer
78 views

Propositional logic derivation

Data given : Y value is either 0 or 1 Premises : 1) $(X=Y)$$\iff$ (R $\lor$ S) 2) S $\iff$ $(X=0)$ 2) R $\implies$ $(X=1)$ Result : $(X=1)$ $\implies$ R Can i infer result from premises and ...
0
votes
1answer
38 views

Prove equivalence of two regular expressions.

I am wondering if there is a standard way to prove that two regular expressions are equivalent. I have tried to prove, given two regular expressions $r$ and $s$, that $L(r) \subseteq L(s)$ and $L(s) ...
0
votes
1answer
38 views

Proper subset of span of only one vector

Prove that $v_1,....,v_k$ are linearly independent if and only if for each $j\in\{1,...,k\}$: span$(v_1,..,v_{j-1},v_{j+1},..,v_k) \subsetneq$ span$(v_1,...,v_{j-1},v_j,v_{j+1},...,v_k)$ My first ...
1
vote
0answers
94 views

Proof by contradiction. Which statement has to be shown to be false?

I want to prove the following statement: Show that if $B=(b_1,....,b_n)$ is a basis of a vector space V, then there is no list of vectors of length $n-1$ that spans V. I would like to prove this by ...
2
votes
1answer
149 views

Prove that if $A$ and $B$ are finite, then $A \cup B$ is finite

Statement: if $A$ and $B$ are finite, then $A \cup B$ is finite Proof: If $A$ and $B$ are finite, then there exists $m, n \in \mathbb{N}$ such that $A \approx \mathbb{N}_{m}$ and $B \approx ...
0
votes
3answers
259 views

Proving equivalent statements

If I have multiple statements and have to prove that they are all equivalent, which proof strategy should I use? E.g. lets say I have statements A, B, C and D and need to show that they are all ...
5
votes
5answers
124 views

Finding the derivative of $2^{x}$ from first terms?

I was trying to understand why $e^{x}$ is special by finding the derivatives of other exponential functions and comparing the results. So I tried ${\rm f}\left(x\right) \equiv 2^{x}$, but now I'm ...
0
votes
3answers
77 views

If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$.

If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$. Also... $a,b$ and $n$ are natural numbers. I feel I should begin with EEA to multiply out the gcd's, but I don't know where to go from ...
3
votes
1answer
201 views

Lawvere theories: an equivalence.

I'm having trouble understanding Lawvere theories (as defined below). Definition: A Lawvere Theory is a category $\mathcal{L}$ with finite products and with a distinguished object $A$ such that ...
3
votes
3answers
124 views

Question on Rudin sequences?

In baby Rudin, Rudin shows that $$\lim_{n \to \infty}\sqrt[n]{p} = 1.$$ In the proof of limit he tries to prove that the limit is $1$. So he takes $x_n = \sqrt[n]{p} - 1$. I have never noticed this ...
0
votes
2answers
103 views

Bi-implication theorem proving

While proving a theorem, i came across a situation like as follows (P has a property) $\leftrightarrow $ $(x=y)$ (P has a property) $\leftrightarrow $ $(y=z)$ Now can i infer the following fact ...
3
votes
4answers
91 views

Limits and differentiability

Suppose that $f$ is differentiable on $(0, \infty )$ and $\lim\limits_{x \to \infty} f(x) = 1$. If $\lim\limits_{x \to \infty} f'(x) = c$, show that $c = 0$. I know that since $f$ is differentiable, ...
1
vote
2answers
46 views

Let $F = \{2x-3:x \in E\}$. Show that $F$ is compact.

Suppose that $E$ is a compact nonempty subset of $\mathbb{R}$. Let $F = \{2x-3:x \in E\}$. Show that $F$ is compact. My idea is to prove that $F$ is closed and bounded. To prove that it is closed, ...
0
votes
5answers
47 views

How to prove this is true?

The question is: Show that $$\log_2(n!)\in O(n \log_2(n)).$$ I'm guessing I'll have to use principle of simple induction for this one. But how would I go about writing the proof for this? Should I ...
-1
votes
1answer
44 views

Proving linear independence.

Let $E$ be a $3$-dimensional vector space over the field of rational numbers. Suppose $T$ is a linear operator and $T(x)=y$, $T(y)=z$, $T(z)=x+y$ for certain $x$, $y$, $z$ in $E$ and $x\ne 0$. Prove ...
1
vote
1answer
93 views

How we got $z\cdot(x+y)=x\cdot y$

This is from "Test of math at 10+2 level": A vessel contains $x$ gallons of wine and another contains $y$ gallons of water. From each vessel $z$ gallons are taken out and transferred to the other. ...
4
votes
0answers
170 views

Puzzle - zero knowledge proof

I am solving the following problem : I have edge-matching puzzles, where all pieces are squares and the grid has $n$*$n$ format. There is no global image to guide a puzzle solver. Despite the puzzles ...
2
votes
2answers
49 views

How would I go about proving this?

Question is: Let $n$ represent a positive integer. Describe the largest set of values $n$ for which you think that $2^n < n!$ I'm not sure I get this question. For $n > 3$, it seems like ...