For questions about the writing of proofs. But instead of focusing the mathematics behind the proof, these questions ask about the details and implementation of the proof.

learn more… | top users | synonyms

1
vote
2answers
694 views

Prove by induction the predicate (All n, n >= 1, any tree with n vertices has (n-1) edges).

I'm stuck on this problem, posting my progress so far below. I've looked at similar questions here and here, but neither seem to directly prove the predicate by induction, with a base case followed by ...
0
votes
2answers
59 views

How to formally state and prove vacuous truth?

How to show in a proof that a statement is vacuously true because "if $\alpha$ then $\beta$", and also prove $\alpha$ is false, in a formal way? and also particularly, how to structure such proofs? ...
0
votes
2answers
31 views

Help on the Inclusion Exclusion principle and explaining cardinality

I want to prove the inclusion exclusion principle: |A∪B|=|A|+|B|−|A∩B| where A and B are finite sets. However I'm confused about one thing. I've learned that two cardinalities are equal if there is a ...
2
votes
2answers
93 views

Mathematical Induction Proof - Exponent with n in denominator

Use mathematical induction to prove the following: $$\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+...+\frac{n}{2^n}=2-\frac{n+2}{2^n}; n ∈ N $$ I am having trouble figuring out how to solve this with an ...
36
votes
2answers
806 views

A strange integral

While browsing on Integral and Series, I found a strange integral posted by @sos440. His post doesn't have a response for more than a month, so I decide to post it here. I hope he doesn't mind because ...
0
votes
2answers
28 views

Proving a surjection. Clarification

I just want to make sure this is all correct. So my definition of a function $f:A\to B$ being a surjection is: For all $b \in B$, there exists an $a \in A$ such that $f(a) = b$. Now the ...
2
votes
1answer
79 views

Prove that stabilizer subgroups of G are conjugate to each other

Suppose that a group $G$ acts on a set $X$. Show that if $x_1$ and $x_2$ in X are in the same $G$-orbit, then their stabilizer subgroups of $G$ are conjugate to each other. My proof: Assume ...
1
vote
0answers
41 views

Greatest common divisor / euclidean algorithm linear combination proof [duplicate]

Consider integers $m$ and $n$, not both 0. Show that gcd$(m,n)$ is the smallest positive integer that can be written as $am + bn$ for integers $a$ and $b$. I'm confused on what exactly to do--I'm ...
0
votes
3answers
60 views

Prove that in a ring with at least two elements $0\neq 1$. [closed]

Let R be a non-trivial ring then prove $0\neq 1$.
2
votes
0answers
72 views

How to use a very complicated theorem for proving simpler statements without falling into a loop?

There are some too complicated theorems in mathematics which have very complicated proofs in hundreds of pages. There are few mathematicians who are aware of the entire proof of such theorems in full ...
4
votes
0answers
40 views

Another proof question for real analysis

Let $a, b, c \in \mathbb{R}$. Prove if $a + b = a$ then $b = 0$. Suppose that $a + b = a$. Then $a + b - a = a - a = 0 = b$ by the inverses law for addition. By the Identity law for addition it ...
0
votes
2answers
38 views

Recursive definition proof

I'm having trouble proving the following: $a_0 = a_1 = 1$ and $a_n = a_{n-1} + 2a_{n-2}$ for $n \ge 2$. Prove that all the terms $a_n$ are odd integers. It makes sense since an odd number is of the ...
1
vote
1answer
85 views

Proving that the change of parameters is differentiable.

Let $M \subset \Bbb R^3$ be a regular surface, and ${\bf p} \in M$. Let ${\bf x} : U \subset \Bbb R^2 \to M$ and $\overline{{\bf x}}:\overline{U} \subset \Bbb R^2 \to M$ be parametrizations at ${\bf ...
-1
votes
1answer
34 views

Trouble conceptualizing discrete math problem

I'm studying for discrete math and I'm looking for my professor's test problems and their solutions. There is one in particular I am having trouble conceptualizing, maybe someone could help me out. ...
-1
votes
1answer
26 views

How to prove that if $T(n)=\max_{1\le q \le n-1}(T(q)+T(n-q))+\Theta(n)$ then $T(n)=O(n^2)$

I have this recursion relation: $T(n)=\max_{1\le q \le n-1}(T(q)+T(n-q))+\Theta(n)$. How do I show that: $T(n)=O(n^2)$ Thank you!! (P.S. I hope it's OK to ask it, but I'm looking for the simple ...
3
votes
4answers
248 views

Reference textbook about proof techniques

I am looking for some good recommended reference textbooks about proof techniques. Someone told me "G. Polya - How to solve it" is kind of standard, but quite old. I am looking for a book that ...
0
votes
1answer
23 views

How to solve $T(n)=\frac2n\sum_{i=1}^{n-1}T(i)+\Theta(n)$

I need to solve this Recursion Relation:$$T(n)=\frac2n\sum_{i=1}^{n-1}T(i)+\Theta(n)$$ Do you have any idea how? (I try to find another way instead induction). (We should get: $T(n)=\Theta(n\log n)$) ...
-1
votes
1answer
25 views

big $\Theta$ question dealing with $\log_2{n}$ and $\log_{10}{n}$

Show that $\log_{10}{n} = \Theta(log_2{n})$. I know that I have to show that 1) $\log_{10}{n} = O(\log_2{n})$ show: $\log_{10}{n} \le C * \log_2{n}$ and 2) $\log_2{n} = O(\log_{10}{n})$ show: ...
-1
votes
1answer
84 views

Show that if complex matrices A and B are both hermitian, then ABA is also hermitian.

i have never done a linear algebra proof, although i've written many others. please help me with this one.... "Show that if complex matrices A and B are both hermitian, then ABA is also hermitian." ...
0
votes
1answer
23 views

Big oh / big theta proof for the following

Find a number $a$ with $s(n) = \Theta(a^n)$ for $s(n) = (\log_2{10})^{(n-3)}$. I'm not quite sure how to proceed. I was having problems with another problem trying to figure out what it means to ...
4
votes
1answer
101 views

Let $G$ denote an arbitrary group. Prove: The center of any group $G$ is a normal subgroup of $G$

Let $G$ denote an arbitrary group. Prove: The center of any group $G$ is a normal subgroup of $G$ Let $G$ be a group and $C$ the center, i.e., for any $a \in C$ and any $x \in G$, $xa=ax$. So, ...
0
votes
3answers
61 views

Proving $f\colon S \to S$; $f(x) = 1/x$ is bijective

Hey I'm trying to figure out this proof. I don't know if anyone could help but I would really appreciate it! Let $S = \mathbb{R} \setminus \{0\}$. Prove that the function $f\colon S \to S$; $f(x) = ...
0
votes
6answers
76 views

Proving $f:\mathbb N \to \mathbb N; f(n) = n+1$ is not surjective.

Prove that the function $$f:\mathbb N \to \mathbb N; f(n) = n+1$$ is not bijective. So I know that we can prove it is injective because we can suppose or let $n_1$ and $n_2$ are natural numbers with ...
2
votes
2answers
230 views

Proof of FOIL Modern Algebra

I am trying to work through Birkhoff's A Survey of Modern Algebra independently, but am having difficulty getting off the ground with the proofs based on laws, rules, etc. I come from mostly soft ...
0
votes
1answer
33 views

Big oh proof for a(n) using big oh hierarcy

So I'm given the following big-oh hierarchy (each sequence is big-oh of any seqeuence to its right.) $1$, $\log_2{n}$, ... , $\sqrt[4]{n}$, $\sqrt[3]{n}$, $\sqrt{n}$, $n\log_2{n}$, $n\sqrt{n}$, ...
0
votes
1answer
35 views

Proving big oh for a function

Find a $C$ and $k$ such that $\sqrt{n^2 - 1}$ = $O(n^k)$. My professor has stated that there are two different $k$'s. One from the problem statement and one from the definition of big-oh. I know that ...
0
votes
1answer
48 views

By proposition 3.21 is ether acute, right or obtuse

Let A, B, C be points on a line with A ∗ B ∗ C. Let D be a point not on that line such that angle ABD is obtuse. Show that angle CBD is acute. Do NOT use the Measurement Theorem. (Hint: By ...
0
votes
1answer
24 views

How to prove this thing from Graph Theory?

How to prove that if we have two DAGs (Directed Acyclic Graph) D1 , D2 and if D1+ = D2+ then (D1)= (D2). D+ means that in this graph there is a positive length path. Example: D grapth may have point A ...
0
votes
2answers
25 views

If $f\,\colon (0,\infty)\to (0,\infty)$ and $f'(x)>0$ then $\displaystyle\lim_{x\to\infty}f(x)\neq 0$ [closed]

I used this in an exercise because it seemed obvious but I am not sure if it needs a proof and if yes, how would I prove it. So how do I prove that if $f\,\colon (0,\infty)\to (0,\infty)$ and $f$ is ...
1
vote
2answers
75 views

elementary properties of closure

Let X be arbitrary subset of R, then $$X\subset \overline X$$ proof by contradiction: let $x \in X$ and suppose X not a subset of its closure then for every $y\in X$, $|x-y|> \epsilon $ where ...
0
votes
1answer
28 views

Ordered Pair Proof

Below are two relations on $R.$ For each one, determine (with proof) whether or not it is an equivalence relation. If it is an equivalence relation, describe the partition it induces (i.e., describe ...
1
vote
1answer
68 views

Where is the error in this proof :

Prove that: $$\frac {2\Gamma'(2z)}{\Gamma(2z)}-\frac {\Gamma'(z)}{\Gamma(z)}-\frac {\Gamma \prime(z+\frac{1}{2})}{\Gamma(z+\frac{1}{2})} =2 \log 2$$ But I obtain this equal zero. My proof: From ...
1
vote
2answers
111 views

Proving Konig-Egervary Theorem from Ford-Fulkerson

I've been going over a proof for Konig-Egervary Theorem from Ford Fulkerson, and I just don't see it. In fact, it just seems false. So I'm not sure what I'm missing. Note: the Konig-Egervary Thm says: ...
1
vote
1answer
37 views

Is the function one-to-one?

Is the function $f: \mathbb R+ \to\mathbb R \\$ defined as $f(x) = \sqrt{x} + x + 2$ one-to-one? I'm pretty sure the function is one to one but when I try to solve $f(x) = f(y)$ to $x = y$ I get ...
2
votes
2answers
38 views

Proving that $f$ is a bijection.

Here is the question: Suppose $f:X\longrightarrow Y$ and $g:Y\longrightarrow X$ satisfy $$\forall x\in X.(g\circ f)(x)=x,\,\forall y\in Y.(f\circ g)(y)=y$$ Prove that $f$ is a bijection, with ...
1
vote
0answers
30 views

Riemann-Stieltjes Integrals with $n$ discontinuities (Proof Review)

First of all is the proof legitimate? If so, then are there other methods to achieve the same result that are neater than mine? Let $\alpha : [a,b] \to \mathbb{R}$ be a step function with ...
2
votes
1answer
54 views

Question about $\frac {\Gamma'(z+1)}{\Gamma(z+1)}$

If $\psi (z)= \log\Gamma(z+1)$ Prove that : $$\psi(n)+\gamma=1+\frac{1}{2}+\cdots+\frac{1}{n}$$ My Proof : $$\psi (z)= \frac {\Gamma'(z+1)}{\Gamma(z+1)}=-\frac{1}{z+1}-\gamma + \sum_{n=1}^\infty ...
0
votes
2answers
30 views

Prove that a certain sequence of partial sums (involving integrals) converge.

I have to prove the following: Define $\gamma_{n}= 1+1/2+1/3+...+1/n-\int_{1}^{n}\frac{1}{t}dt$.Prove that $\{\gamma_{n}\}$ converge. I need your help because I don't know how to involve the algebra ...
8
votes
2answers
110 views

Let $G$ be a group, and $H$ a subgroup of $G$. Let $a, b \in G$. Prove $Ha=Hb$ iff $ab^{-1} \in H$.

Let $G$ be a group, and $H$ a subgroup of $G$. Let $a, b \in G$. Prove $Ha=Hb$ iff $ab^{-1} \in H$. $\rightarrow$ If $Ha=Hb$, then $h_1a=h_2b$ for some $h_1, h_2 \in H$. So, $ab^{-1} = ...
0
votes
4answers
110 views

Proof that $ 3 > (1+\frac{1}{n})^n \geq 2$

I am studying computer science in first term, and i got a task that i was not able to solve for a long time now. I have to prove that $ 3 > (1+\frac{1}{n})^n>=2$ for every $n \in ...
1
vote
5answers
110 views

Writing clear proofs involving multiple theorems and conditions

Suppose the problem is that given $A$ and $C$ holds, prove $D$ holds. Some theorems that we can use are: $A \to B$ $(B,C) \to D$ I feel what I said may be unclear: Because $A$ holds ...
1
vote
1answer
45 views

Question on series $\frac {\Gamma'(z)}{\Gamma(z)}$

Prove that: $$\frac {2\Gamma'(2z)}{\Gamma(2z)}-\frac {\Gamma'(z)}{\Gamma(z)}-\frac {\Gamma \prime(z+\frac{1}{2})}{\Gamma(z+\frac{1}{2})} =2 \log 2$$ But I obtain this equal zero: $$\frac ...
2
votes
3answers
94 views

Validity of this proof that any continuous function with domain and range in [0,1] must have a fixed point.

The following proof was given in a solutions manual to a question asking to prove that a continuous function with domain and range in $[0,1]$ must have a fixed point: Consider the function $F(x) = ...
0
votes
3answers
35 views

The subspace $S ⊆ \mathbb{R}^n$ has linearly independent vectors $u_1,…u_k$. Show that any basis for $S$ must have at least $k$ vectors.

Let $S ⊆ \mathbb{R}^n$ be a subspace. Say that $u_1,.....u_k ∈ S$ are linearly independent vectors. Show that any basis for S must have at least k vectors. "Say that $u_1,.....u_k ∈ S$ are linearly ...
1
vote
0answers
34 views

How to prove that a function f(x) is O(g(x)), using the definition (finding C and k)

We say that $f(x)$ is $O(g(x))$ if $$(∃C ∈ \mathbb(R)❘)(∃k ∈ \mathbb(R)❘)(∀x ∈ \mathbb(R)❘)$$ $$(x ≥ k → |f(x)| ≤ C · |g(x)|)$$ In English: We can find $C$ and $k$ so that, once we get past the “small ...
0
votes
1answer
28 views

Need help on a example about proof on functions and sets

I need some help to prove the problem below: Suppose $g$ is a function from $X$ to $Y$ and $f$ is a function from $Y$ to $Z$. $A$ and $B$ are subsets of $X$. Prove that if $A$ is a subset of $B$ then ...
1
vote
2answers
106 views

Prove: Use the triangle inequality to prove that for all $x, y, | |x| − |y| | ≤ |x − y|$ [duplicate]

Prove: Use the triangle inequality to prove that for all $x, y, | |x| − |y| | ≤ |x − y|$ Proof: If $x ≥ 0$ and $y ≥ 0$, then both sides of the inequality are the same. Also if $x ≤ 0$ ...
0
votes
1answer
124 views

Define a relation ~ on ℕ by a~b if ab is a perfect square

So, for this problem: a. Prove that ~ is an equivalence relation on ℝ². (I'm not sure if this is a typo on my professor's part since we are defining a relation on ℕ.) b. Describe the equivalence ...
1
vote
3answers
54 views

Supremum of the product of sets

Let $A, B$ be subsets of positive real numbers that are bounded above, and let $A\cdot B=\{ a b : a\in A, b\in B\}$. Show that $$ \sup (A\cdot B) = \sup A \sup B. $$ Proof: This is obvious. It is ...
1
vote
1answer
61 views

Define a relation ~ on ℝ² by (x,y)~(w,z) if x+y=w+z

So, it comes in two parts: a. Prove that ~ is an equivalence relation on ℝ². b. Give a geometric description of the partition of ℝ² formed by the equivalence classes. For a, I have to prove that ~ ...