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

6
votes
3answers
110 views

How to prove $4(n!)>2^{n+2}$ for $ n\geq 4$ with induction

I've done the base step, but how do I prove it is true for $n+1$ without using a fallacy? $$4(n!)>2^{n+2}\quad \text{for } n\geq 4$$ Please help.
5
votes
4answers
493 views

Discrete Math Proofs Involving Real Numbers

I am stuck on these two problems. $1$. Prove that for every three positive real numbers a, b, and c that $(a+b+c)*(\frac{1}{a}+\frac{1}{b} + \frac{1}{c}) \ge 9$. $2$. Prove that for every three ...
5
votes
3answers
284 views

Help with Cartesian product subsets [duplicate]

I want to prove that if $A \subseteq C\,$ and $\,B \subseteq D,\,$ then $\,A \times B \subseteq C \times D.$ I know that $A \subseteq C \iff a \in A \rightarrow a \in C$ and that $B\subseteq D\iff ...
5
votes
4answers
285 views

Combinatorial Proof

I have trouble coming up with combinatorial proofs. How would you justify this equality? $$ n\binom {n-1}{k-1} = k \binom nk $$
4
votes
3answers
216 views

Invertibility in a finite-dimensional inner product space

Let $T$ be an invertible linear operator on a finite-dimensional inner product space. I just want a hint as to how I should prove that $T^{\star}$ is also invertible and $( T^{-1} )^{\star} = ( ...
4
votes
3answers
4k views

Prove that the intersection of two equivalence relations is an equivalence relation.

I am reading this chapter of the Book of Proof, and I'm stuck at the Exercise 10 of section 11.2. It is as follows. Suppose $R$ and $S$ are two equivalence relations on a set $A$. Prove that $R ...
3
votes
1answer
51 views

Do absolute convergence of $a_n$ implies convergence of $K_n=\frac{1}{\ln(n^2+1)}\sum_{k=1}^{+\infty}a_k\frac{3k^3-2k}{7-k^3}\sin k$?

The problem asks us to decide whether the following statement is true: Let $\{a_n\}_{n\geq1}$ be any absolutely convergent sequence. Does that imply that the sequence: ...
3
votes
3answers
76 views

Prove that $G$ is abelian iff $\varphi(g) = g^2$ is a homomorphism

I'm working on the following problem: Let $G$ be a group. Prove that $G$ is abelian if and only if $\varphi(g) = g^2$ is a homomorphism. My solution: First assume that $G$ is an abelian group ...
3
votes
2answers
810 views

How to find the period of the sum of two trigonometric functions

I want to know if there exists a general method to find the period of the sum of two periodic trigonometric function. Example: $$f(x)=\cos(x/3)+\cos(x/4).$$
3
votes
2answers
521 views

Why is $\cos(2x)=\cos^2(x)-\sin^2(x)$ and $\sin(2x)=2\sin(x)\cos(x)$?

I was studying math.. and I just realized that I only just memorized these trigonometric equations, but I don't really know the reason behind them. So um... Why is $\cos(2x)=\cos^2(x)-\sin^2(x)$ and ...
3
votes
2answers
136 views

Let $S$ and $T$ be finite non-empty sets such that $|S| = |T|$. Show that the function $f : S\to T$ is onto if and only if it is one-to-one.

This is a recent homework bonus question assigned in my Proofs and Conjectures class. It (evidently) includes and evaluates our understanding of elementary-set theory and how to determine and prove ...
3
votes
2answers
133 views

If $f$ is differentiable and $\lim_{x→0} f'(x) = L$, then $f'(0) = L$.

True/False. (c) If $f$ is differentiable on an interval containing zero and if $\lim_{x→0} f'(x) = L$, then $f'(0) = L$. 1. How to presage proof by contradiction? Proof by contradiction. ...
3
votes
4answers
103 views

How to prove that triangle inscribed in another triangle (were both have one shared side) have lower perimeter?

This question looks really simple, but to my (and my co-workers) frustration we were not able to prove this in any way. I tried all triangle formulas known to me but I feel I'm missing the point, and ...
3
votes
1answer
122 views

Proof for recursively defined sets

Language $L\subset \{a,b\}^*$ is such that: $\epsilon \in L$ $a \in L$ For any $x\in L$, $xb\in L$ and $xba\in L$ Nothing else in $L$. Im just learning recursive sets, but with that definition am ...
3
votes
2answers
122 views

Prove through induction that $3^n > n^3$ for $n \geq 4$

I'm new to induction and have not done induction with inequalities before, so I get stuck at proving after the 3rd step. The question is: Use induction to show that $3^n > n^3$ for $n \geq ...
3
votes
2answers
335 views

Prove the monotonicity of the expectation of a binary random variable function

Consider $R$ independent binary random variables $y^1, \ldots, y^R$ over the space $\{-1, +1\}$ such that $\Pr(y^j = 1) = p^j \geq 0.5$ and $\Pr(y^j = -1) = 1 - p^j$, $\forall j = 1,\ldots,R$. ...
3
votes
2answers
2k views

Prove the centralizer of an element in group $G$ is a subgroup of $G$

We have a group $G$ where $a$ is an element of $G$. Then we have a set $Z(a) = \{g\in G : ga = ag\}$ called the centralizer of $a$. If I have an $x\in Z(a)$, how do I go about proving that the inverse ...
2
votes
2answers
73 views

Prove that if an average of a thousand numbers is less than 7, then at least one of the numbers being averaged is less than 7 [closed]

I tried proving this by contraposition, by saying, "If every number that is being averaged is greater than 7, then the average of a thousand numbers is less than 7." This seems easier to prove, but I ...
2
votes
2answers
546 views

If $x \in\mathbb{Z}$ has the property that for all $m \in\mathbb Z$, $mx = m$, then $x = 1$

I am learning proofs, and I am stuck with this proposition: Let $x \in\mathbb{Z}$. If $x$ has the property that for all $m \in\mathbb Z$, $mx = m$, then $x = 1$. I want to use the additive ...
2
votes
2answers
95 views

Prove $1^3 + 2^3 + \cdots + n^3 = (1 + 2 + \cdots + n)^2$ using Induction [duplicate]

Prove $1^3 + 2^3 + \cdots + n^3 = (1 + 2 + \cdots + n)^2$ using Induction My proof so far: Let $P(n)$ be $1^3 + 2^3 + \cdots + n^3 = (1 + 2 + \cdots + n)^2$ Base Case $P(1):$ LHS = $1^3 = 1$ ...
2
votes
2answers
36 views

Next step to take to reach the contradiction?

This problem is from Discrete Math and its Applications I am trying to use proof by contradiction to do this problem, proof by contradiction as described by the book Here is my work so far for ...
2
votes
2answers
153 views

Show that, for any $\epsilon>0$, there exist two rationals such that $q < x < q'$ and $|q-q'|<\epsilon$

I think I have the first part, as I have shown that $q < q + (q'-q)/2 < q'$, but I have trouble in proving that $|q-q'|< \epsilon$. Could someone tell me if there is a better way of showing ...
2
votes
1answer
252 views

Pigeonhole Principle

Let $X = {x_0, x_1, · · · , x_m}$ be a subset of ${1, 2, · · · , n}$, where $m > n/2$, and $x_0$ is the smallest number in $X$. Use the pigeonhole principle to show that $X$ contains two numbers ...
2
votes
1answer
115 views

Defining a partial order on $A\times B$, given partial orders on $A$ and on $B$

Let $(A,\preceq_A)$ and $(B,\preceq_B)$ be partially ordered sets. Define $C = A \times B$ and define the relation $\preccurlyeq$ on $C$ to be $(a,b) \preccurlyeq$ $(a',b')$ if and only if ...
2
votes
2answers
311 views

When Dim eigenspace = 1, any $2\times 2$ complex matrix A is similar to $\left(\begin{array}{ll} \lambda & 1\\ 0 & \lambda \end{array}\right)$.

$\bbox[5px,border:2px solid gray]{ \text{ Case 3 } }$ If $\dim E_{\lambda}=1$, take a nonzero $v\in E_{\lambda}$, then $\{v\}$ is a basis for $E_{\lambda}$. Extend this to a basis $\mathfrak{B}=\{v,\ ...
2
votes
2answers
225 views

$\binom{n}{k}\binom{n}{n - k}$ vs $\binom{n}{k}$ - Differences? Similarities?

So the # of ways to choose an $n$ set with $k$ kiwis is $\binom{n}{k}\binom{n}{n - k} = \binom{n}{k}^2$. AlexR wrote No, picking exactly $k$ kiwis means you discount the $n-k$ remaining ...
2
votes
1answer
25 views

Reduce all cases to $x \to 0^{+}$ and $f(x),g(x) \to 0$ before proving L'Hôpital's Rule

Hypotheses: I. $f$ and g differentiable on $(a,b)$ and continuous on $(a,b]$, II. $\lim_{x \to a} f(x) = \lim_{x \to a} g(x) = 0 \quad $ or $\pm \infty$ III. $\lim_{x \to a} f'(x)/g'(x)$ exists IV. ...
2
votes
2answers
104 views

Intuition - Fundamental Homomorphism Theorem - Fraleigh p. 139, 136

Let $\phi: G \to H$ be a group homomorphism with $K = \ker\phi$. Then $G/K \simeq \phi[G]. $ The hinge to the proof is to define $\Phi: G/K \to \phi[G]$ given by $\Phi(gK) = \phi(g)$. Then we must ...
2
votes
0answers
234 views

Show that an element has order $p$ in $S_n$ iff its cycle decomposition is a product of commuting $p$-cycles.

I would like to know if my proof below is correct. Problem Let $p$ be a prime. Show that an element has order $p$ in $S_n$ iff its cycle decomposition is a product of commuting $p$-cycles. Show by ...
2
votes
3answers
310 views

Demonstrate that if $f$ is surjective then $X = f(f^{-1}(X))$

I haven't been able to do this exercise: Let $f: A \rightarrow B$ be any function. $f^{-1}(X)$ is the inverse image of $X$. Demonstrate that if $f$ is surjective then $X = f(f^{-1}(X))$ where $X ...
2
votes
1answer
140 views

On how to get a solution for a nonhomogeneous problem for the heat equation.

Evans PDE book presents the following problem (page 87): Write down an explicit formula for a solution of $$\left\{\begin{matrix} u_t-\Delta u+cu=f &\text{ in }\mathbb{R}^n\times(0,\infty) ...
2
votes
1answer
80 views

Proofs involving sequential limit

Let $S$ be the domain of the function $f$. Suppose $S=\left\{\frac{1}{n}: n\in\Bbb N\right\}$. Show $\lim_{x\to0}f(x)=L$ iff $\lim_{n\to\infty}f\left(\frac{1}{n}\right)=L$. Idea: I want to say, let ...
2
votes
2answers
124 views

Proof that this is independent

Prove that {$1, \sin(x), \sin(2x), \sin(3x),\ldots, \sin(nx)$} is an independent set. I can think of the long way which is to differentiate this and put the differentiations into a matrix and row ...
2
votes
1answer
121 views

Where is the fallacy in this coupling argument of two Bernoulli variables?

With respect to the scenario introduced in Prove the monotonicity of the expectation of a binary random variable function, let us now suppose that the function: $$\begin{align*} f(\mathcal{J}) = ...
2
votes
3answers
265 views

I don't understand this proof of the AM-GM inequality?

The proof uses this lemma which I understand: $\mathbf {Lemma}$: Suppose $x$ and $y$ are positive real numbers such that $x>y$. If we decrease $x$ and increase $y$ by some positive quantity $E$ ...
2
votes
1answer
921 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 ...
2
votes
2answers
97 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 ...
2
votes
4answers
133 views

Is a contradiction enough to prove a set equality to $\varnothing$?

An exercise asks me to prove the following: $$A \cap (B-A) = \varnothing$$ This is what I did: I need to prove that $A \cap (B-A) \subseteq \varnothing$ and $\varnothing \subseteq A \cap (B-A)$ The ...
2
votes
2answers
144 views

Sum of Sines Interval [duplicate]

Possible Duplicate: How can we sum up $\sin$ and $\cos$ series when the angles are in arithmetic progression? How is it possible to show for integer $m$: ...
1
vote
3answers
44 views

Show that if $A$ and $B$ are sets, then $(A\cap B) \cup (A\cap \overline{B})=A$.

Show that if $A$ and $B$ are sets, then $(A\cap B) \cup (A\cap \overline{B})=A$. So I have to show that $(A\cap B) \cup (A\cap \overline{B})\subseteq A$ and that $A \subseteq(A\cap B) \cup (A\cap ...
1
vote
7answers
122 views

Give a direct proof of the fact that $a^2-5a+6$ is even for any $a \in \mathbb Z$

Give a direct proof of the fact that $a^2-5a+6$ is even for any $a \in \mathbb Z.$ I know this is true because any even number that is squared will be even, is it also true than any even number ...
1
vote
3answers
41 views

Proving quadratic inequalities?

I am trying to prove that $$e^{k+1} ≥ 3 + 3k + k^2$$ with, $$k>2$$ WhatI have done so far: What we are trying to prove is that $$e^n≥1+n+n^2$$ is a true statement. Since $n=3$ holds, this is ...
1
vote
1answer
64 views

Application of Cauchy Integral

Let $f$ be holomorphic in $\{|z|<R\},$ where $R>1.$ Show: $\begin{align}f(z)= i\text{Im}f(0) +\dfrac{1}{2\pi} \int^{2\pi}_{0} \dfrac{e^{it}+z}{e^{it}-z} \text{Re}f(e^{it})dt, \ \forall |z| ...
1
vote
1answer
192 views

Number of roots of a polynomial over a finite field

For any $g$ in $\mathbb{Z}/p\mathbb{Z}[x]$ prove that the degree of $f = \gcd(x^p - x, g(x))$ is exactly the number of distinct roots of $g$ in $\mathbb{Z}/p\mathbb{Z}$. My main problem is that I ...
1
vote
1answer
179 views

Linear algebra proof regarding matrices

I'd like a hint rather than a full solution. The problem I am considering is the following: $X$ is an $n\times m$ matrix $Y$ is $m\times n$ Show that $(I - XY)^{-1}\cdot X = X\cdot(I - ...
1
vote
0answers
37 views

Prove the von Staudt-Clausen congruence of the Bernoulli numbers

I need to prove that: If $p$ is prime greater than or equal to five, then $pB_{p-1}$ belongs to the p-integers and more over: $$pB_{p-1} \equiv -1 \pmod p$$ Hint:Put $N=p$ in the Faulhaber´s ...
1
vote
1answer
46 views

Intuition and Motivation - Linear Operator $T - \lambda_k I$ ? [Lay P270 Thm 5.1.2]

Let $T$ be a linear operator on a vector space V, and let $\lambda_{1},\ \lambda_{2},\ \ldots,\ \lambda_{k}$ be distinct eigenvalues of T. If $v_{1},\ v_{2},\ \ldots,\ v_{k}$ are eigenvectors of $T$ ...
1
vote
3answers
92 views

Prove that $A \cup B = A$ if and only if $B$ is a subset of $A$

If $A \cup B = A$ then $A$ is a subset of $A$ and $B$ is a subset of $A$. Thus $A \cup B = A$. If $B$ is a subset of $A$ then it follows that $A \cup B$ is a subset of $A$. My solution. It seems ...
1
vote
1answer
79 views

Without Stokes's Theorem - Calculate $\iint_S \operatorname{curl} \mathbf{F} \cdot\; d\mathbf{S}$ for $\mathbf{F} = (-y^3,x^3,z^3)$ - 2012 9C

Question: 2012 9C. Consider the (cutoff) paraboloid defined by $z= x^2 + y^2 , \frac{1}{9} \le z \le 1$. Sketch the surface. Verify Stokes’s Theorem for for $\mathbf{F} = (-y^3,x^3,z^3)$. Herein, I ...
1
vote
3answers
1k views

Prove that the union of two disjoint countable sets is countable

This is a question from my proofs course review list that I have had trouble understanding. I understand the concept of disjoint sets. I'm not sure what they mean by countable. How would one prove ...