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

How to decide which moduli to check when solving a “polynomial” congruence?

Consider the following problem: Find all integer solutions to $y^2 = x^5 - 4$. The solution goes something like – check modulo 11, where $x^5 \equiv 0, \pm 1$, and then check cases to arrive at ...
4
votes
4answers
89 views

If $a,b$ are positive rational numbers and $\sqrt a+\sqrt b$ is rational, then both of $\sqrt a,\sqrt b$ are rational numbers

I'm trying to show that If $a,b$ are positive rational numbers and $\sqrt a+\sqrt b$ is rational, then both of $\sqrt a,\sqrt b$ are rational numbers. I squared the number $\sqrt a+\sqrt b$ ...
3
votes
3answers
48 views

Determine where h(x) := x $\lvert x \rvert$ is differentiable from R to R.

Determine where h(x) := x $\lvert x \rvert$ is differentiable from R to R. Not totally sure how to start this. Much appreciation, Jesse
5
votes
4answers
69 views

Prove that if $A$ is both open and closed, $A=\mathbb R$. [duplicate]

Suppose $A$ is a non-empty subset of $\mathbb R$. Prove that if $A$ is both open and closed, $A=\mathbb R$. I think I'm supposed to assume that $A$ is not equal to $\mathbb R$ and derive a ...
-3
votes
3answers
39 views

Stirling proof guidance [on hold]

I would like some guidances: Prove that $$\lim_{n\to\infty}\frac{2^nn!}{n^n} = 0$$ Any help is greatly appreciate.
1
vote
4answers
4k views

Is this correct method to prove that $a^2 + b^2 + c^2 ≥ ab + bc + ac$, when $a,b,c \geq 0$?

Can I prove it like this: Let's say that $a=b=c$ so we get "If $a \geq 0$ then $3a^2 ≥ 3a^2$" Now I take the negation of that statement and get "If $a \geq 0$ then $3a^2 < 3a^2$" The anti-thesis is ...
4
votes
4answers
77 views

Proving $\binom{m}{n} + \binom{m}{n-1} = \binom{m+1}{n}$ algebraically

I am working through the exercises and have spent half a day on one problem so I decided to get some help because I can't figure it out. Show that if $n$ is a positive integer at most equal to $m$, ...
0
votes
3answers
111 views

Discrete Mathematics Proof Question

Prove or disprove that there are infinitely many $x, y, z \in \mathbb N$ such that $$\frac{1}{x^2} + \frac{1}{y^2} = \frac{1}{z^2}$$ Currently, I tried to substitute $x, y,$ and $z$ with $2n$ and $n$ ...
0
votes
2answers
42 views

Prove that $\max\{|ac+b|,|a+bc|\}\ge\frac{mn}{\sqrt{m^2+n^2}}$

Let $a,b,c$ be complex numbers such that $|a+b|=m$ and $|a-b|=n$ and $mn\ne0$. Prove that $$\max\{|ac+b|,|a+bc|\}\ge\frac{mn}{\sqrt{m^2+n^2}}$$ I have tried using formula ...
1
vote
2answers
57 views

Prove by induction $n! > n^2$

I am trying to prove the inequality in the title for $n\geq 4$; however, I am stuck on the induction step! Any help would be appreciated. For $n\ge 4$, prove that $n! > n^2$. Base Case: $n=4$, ...
4
votes
0answers
58 views

Real Analysis book with pictures and ideas of proofs

I am taking real analysis course in my graduate class of Maths. My classes will start in 3 months. I have studied real analysis but not very rigorously. Whenever I see theorem I have no idea on how ...
2
votes
1answer
41 views

If a sequence $f(x_n)$ goes to its minimum, will $x_n$ go to the point at which $f$ achieve the minimum?

I have a continuous function $f$ that is defined on a compact set. And $f(x_0)$ is its minimum. If I have a sequence $x_n$ such that $f(x_n)\to f(x_0)$, how can I show that $x_n\to x_0$? I tried ...
2
votes
2answers
36 views

prove the nomalizer $N(H)$ of the subgroup $H$ in $G$ is a group

I need some help on the following question. For an arbitrary subgroup $H$ of the group $G$, the normalizer of $H$ in $G$ is the set $N(H) = \{x \in G \mid xHx^{-1} = H\}.$ Any help??
0
votes
1answer
20 views

Sum-of-divisors determinant

Let $\sigma_k(n)=\sum_{d|n}d^k$ be the generalized sum-of-divisors function. Let $S_n$ be the matrix defined by $[S_n]_{ij}=\sigma_i(j)$. I read a comment somewhere that $$\det(S_n)=1!\cdot 2!\cdots ...
2
votes
1answer
29 views

Epsilon and Delta proof of $\lim_{x\to0} \frac{2-\sqrt{4-x}}{ x}$

I need to prove $\lim_{x\to0} \frac{2-\sqrt{4-x}}{ x}$ I first found the limit to be $\frac{1}{4}$ by using l'hopital's rule. By definition i need to find a $\delta > 0$ for every $\epsilon >0$ ...
0
votes
0answers
12 views

Prove that on N, the relation V where mV n

This is my question! Help me, please! Prove that on $\Bbb N$, the relation $\mathsf V$ is a linear order where $m\mathsf Vn$ if and only if $m$ is odd and $n$ is even, or $m$ and $n$ are even and ...
2
votes
1answer
50 views

“Cascade induction”?

I refer to this answer. The answer is based on several simplification steps, all of them proven by induction. $$S_n = 2903^n - 803^n - 464^n + 261^n$$ $$T_n = 2642\cdot2903^n - 542\cdot803^n - ...
4
votes
3answers
77 views

Mistake in (Baby) Do Carmo? Elementary topology of surfaces.

If you have the book, it's proposition 2 of section 5.3. If not, the proposition reads: Given any two points p and q $\in$ a regular, connected surface S, there exists a parameterized piecewise ...
11
votes
1answer
168 views

A proof involving the Euler phi function

Problem: Let $\varphi$ be the Euler phi function, where for any $n \in \mathbb{Z^+}$, $\varphi(n)$ is the number of positive integers less than $n$ that are relatively prime with $n$. ...
1
vote
3answers
57 views

How to prove countably infinite?

How do I prove the following set is countably infinite? $\{\frac{1}{n}: n\in\mathbb{Z}\setminus\{0\}\}$ I know that I can say this set is a subset of $\mathbb{Q}$, and that $\mathbb{Q}$ is infinite, ...
3
votes
3answers
89 views

If it rains, John is sick. It didn't rain. $\vdash$ John wasn't sick. Is this valid?

If it rains, John is sick. It didn't rain. $\vdash$ John wasn't sick. I would say that this is false since the weather isn't directly influencing John's health. Am I right or wrong? Should I use ...
2
votes
1answer
19 views

Proving Cayley formula using Kirchhoff matrix theorem?

To count the number of spanning trees of a complete graph of order $n$ one can use Kirchhoff matrix theorem and arrive at the exact answer $n^{n-2}$. But in doing so, one should know how to evaluate ...
1
vote
2answers
26 views

Show $\sum_{1\leq n\leq x}\sum_{d\mid n}f(d)=\sum_{1\leq d\leq x}\sum_{1\leq m\leq x/d}f(d)$

I have been trying to get my head around this step in a proof, but havn't been able to, Question: Show $$\sum_{1\leq n\leq x}\sum_{d\mid n}f(d)=\sum_{1\leq d\leq x}\sum_{1\leq m\leq x/d}f(d)$$ ...
1
vote
2answers
267 views

Proof of recursive formula for Catalan numbers, and their interpretation as the number of paths

If $C_n$ is the $n$th Catalan number, then show that they satisfy the following recurrence: $$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots + C_kC_{n−k} + \cdots + C_nC_0\text{ ?}$$ I tried ...
1
vote
1answer
26 views

Proof By Induction - $n^2 = \sum_{i=1} ^{n} (2i-1)$ for all $n\geq 1$ [duplicate]

Using Proof By Induction I am trying to prove the following: $n^2 = \sum_{i=1} ^{n} (2i-1) $ for all $n\geq 1$ Here is my solutions so Far: Base Case: $n=1, LHS: 2(1)-1 = 1, RHS = 1^2 = 1, True$ ...
15
votes
5answers
287 views

How to prove that it is possible to make rhombuses with any number of interior points?

I was given some square dot paper which can be found on this link: http://lrt.ednet.ns.ca/PD/BLM/pdf_files/dot_paper/sq_dot_1cm.pdf and was told to draw a few rhombuses with the vertices on the dots ...
1
vote
4answers
29 views

Proving Two Sets are Equal - Infinite Sets - Example

Let $$A = \{x | x = 2n+1, n\in\mathbb{Z}\}$$ and $$B = \{x | x = 2m-21, m\in\mathbb{Z}\}.$$ I am trying to prove $A =B.$ I understand that I need to prove $A\subseteq B$ and $B\subseteq A$; But my ...
3
votes
2answers
82 views

show that nth Chebyshev polynomial is an nth order polynomial

Define the Chebyshev polynomial $T_n(x)=\cos(n\cos^{-1}(x)), n\geq 1, T_0=1)$. Show that $T_n(x)$ is an nth order polynomial This is my attempt, however I couldn't reduce it to a polynomial. ...
0
votes
1answer
16 views

Prove that $\int_{\mathbb{R}}x^me^{2ax}e^{-x^2/2}=e^{2a^2}\int_{\mathbb{R}}(x+2a)^me^{-x^2/2}$

As the title indicates, I've been trying for quite some time now to prove that $$\int_{\mathbb{R}}x^me^{2ax}e^{-x^2/2}=e^{2a^2}\int_{\mathbb{R}}(x+2a)^me^{-x^2/2}$$ $\forall m \in \mathbb{N}, \forall ...
5
votes
3answers
95 views

Where does the proof of $\sqrt 2$ is irrational break down when trying to prove the same for $\sqrt 4$?

I'm trying find where the common proof by contradiction that $\sqrt 2$ is irrational breaks down when trying to prove $\sqrt 4$ is irrational. Assume $(\frac pq)^2=4$ and $\gcd(p,q)=1$. I guess I ...
0
votes
0answers
14 views

Orthogonal surfaces

Prove that the three surfaces of the family $xy/z=u$ $\sqrt{x^2+y^2}+\sqrt{y^2+z^2}=v$, $\sqrt{x^2+y^2}-\sqrt{y^2+z^2}=w$ that pass through just one point are orthogonal I´m assuming that first I ...
0
votes
3answers
45 views

Suppose $A$ is a subset of $B$ and $B$ is a subset of $C$ and $A$ is equinumerous with $C$. Prove $B$ is equinumerous with $C$.

Definition I use: $A \sim B$ means $A$ is equinumerous with $B$ which means there is a $f\colon A \rightarrow B$ that is a bijection. My goal is to prove the following, Suppose $A \subseteq ...
1
vote
1answer
291 views

Characterize normal subgroups - Find all subgroups of $S_3$ conjugate to $\{id, (1,3) \}$ - Fraleigh p. 143 14.29

(27.) A subgroup H is conjugate to a subgroup K of a group G (viz. p. 141 $K \le G$ is a conjugate subgroup of $H$), if $i_g[H] = gHg^{-1} =K$ for some $g \in G$. Show that conjugacy is an ...
1
vote
1answer
107 views

Proof of Hyperbolic Functions

Find the proof:  (a) Use the definitions cosh(x)= 1/2(ex +e^−x) , sinh(x)= 1/2(e^x − e^−x) to express sinh(x + y) and cosh(x + y) in terms of cosh(x), sinh(x), cosh(y) and sinh(y). (b) Using the ...
0
votes
1answer
28 views

Prove that $\prec$ is irreflexive and transitive

Note: Definitions I use (Velleman's How To Prove It) If $A$ and $B$ are sets, then we will say that $B$ dominates $A$, and write $A \precsim B$, if there is a function $f: A \rightarrow B$ ...
0
votes
1answer
38 views

Are $x$ and $y$ divisible by $n$, if so how do I prove it?

If $y$, $x$,are natural numbers, and $n$ is a prime number, $y = x + n$, $y>x>n$, and $y$ and $x$ are not coprime, is it true that $n$ is a divisor of both $x$ and $y$? If so could you please ...
-2
votes
0answers
24 views

To prove ($A\cup B$) $\cap C$ = $(A \cup C) \cap (B \cup C)$ [duplicate]

I have never done rigorous et theory before .How do i prove this and generalise for $A_{i}$ ,i belonging to I ($A\cup B$) $\cap C$ = $(A \cup C) \cap (B \cup C)$ Hints ? Thanks
1
vote
1answer
48 views

Prove that $f$ is an onto function and a homomorphism function from $(\mathbb{Z} \times \mathbb{Z}, \oplus)$ to $(\mathbb{Z}, +)$

I have a lot of issues trying to figure out this problem. Any advice? Consider the two groups $(\mathbb{Z} \times \mathbb{Z}, \oplus)$ and $(\mathbb{Z}, +)$, where $(a,b) \oplus (c,d) = (a + c, b + ...
0
votes
2answers
51 views

Construction of Natural Numbers

I am trying to prove that the natural numbers can be constructed from the product of a power of $2$ and an odd number. For all $n \neq 0$ in the natural numbers, $n = (2k+1)(2^p)$, where $k$ and $p$ ...
0
votes
3answers
29 views

Proving $T(n) = 1 + \sum_{j=0}^{n-1} T(j)$, $T(0)=1$ implies $T(n)=2^n$

I feel that this is a fundamental question. $$ T(n) = 1 + \sum_{j=0}^{n-1} T(j). $$ Given $$ T(0) = 1. $$ Show $$ T(n) = 2^n. $$ If I substitute values, I can see that the series goes like 1, 2, 4, ...
0
votes
1answer
37 views

What sequence of polynomials is equal to $2^n$ for integers $1$ to $k$?

I am trying to prove to someone that no matter how many terms you have of a sequence you can never be 100% sure of the underlying formula. Consider this sequence: $$2^n=1,2,4,8,16,...$$ But just given ...
12
votes
4answers
194 views

Proving $\sqrt{1+\sqrt{2+\cdots+\sqrt{n}}} < 3$ for $n\geq 1$ by induction

How can I prove by induction that $\sqrt{1+\sqrt{2+\cdots+\sqrt{n}}} < 3$ for $n\geq 1$? My guess is that there must be another form to express the sum of nested square roots, but I don't know how ...
4
votes
2answers
62 views

Proving that $3^n<n!$ when $n\geq 7$

It's been 10 years since my last math class so I'm very rusty. How would I go about proving $$3^n < n!$$ where $n \geq 7$? I understand that factorials grow faster than set values with a variable ...
3
votes
2answers
57 views

Help in proving a tautology

I am having real trouble deriving this tautology: $\forall(x) ((x=a) \lor (x\neq a))$ It is easy to solve this by assuming the negation, unpack the negation with DeMorgan's Law, and derive from ...
0
votes
1answer
54 views

Proof of infinite monkey theorem. [duplicate]

I was just wondering, does the infinte monkey theorem also has a proof? And why is this called a theorem? It is sheer common sense. And what are its applications. I have heard about PHP and IEP and I ...
0
votes
1answer
661 views

Palindrome Decidable by DFA

Here's a problem a professor I was talking with gave to me to see how people solve. How would you solve this? A string in {a,...,z}* is said to be a palindrome if it is equal to its own reversal. Is ...
2
votes
1answer
42 views

Do all singular $n\times n$ matrices form a vector subspace when $n\ge2$?

I want to prove or disprove that the set of all $n\times n$ singular matrices form a vector subspace of $M_{nn}$ when $n\geq 2$. So, let: $$ A_{n,n} = \begin{pmatrix} a_{1,1} & a_{1,2} & ...
0
votes
1answer
24 views

Measurability of sequence of functions

Let $(f_n)_{n \in \Bbb N}$ be a sequence of measurable functions on a measure space $(X, M, \mu)$. Prove that the set $\{x \in X \; | \; \lim_n f_n(x) \text{ exists} \text{in } [-\infty, ...
4
votes
2answers
107 views

How do I prove that $ f(n) = (n + 1)! - 1 $ is an injective function?

I have this problem: Consider the function $f : \mathbb{N} \rightarrow \mathbb{N}$ defined, for every $n \in \mathbb{N}$, by $$f(n) = (n+1)! - 1$$ Prove that $f$ is injective. How do I ...
3
votes
0answers
34 views

Proof that $\mathbb{Z}[\sqrt{3}]$ is a Euclidean Domain.

Proof that $\mathbb{Z}[\sqrt{3}]$ is a Euclidean Domain. Proof that $\mathbb Z[\sqrt{3}]$ is a Euclidean Domain Is it possible to solve this question without using $\mathbb{Q}[\sqrt{3}]$ restricted ...